シラバス詳細

タイトル「2022年度」、カテゴリ「理工学部」

和文・英文ボタンを押すことで、和文↔英文の切り替えができます。

和文英文

医学部のシラバスはこちらから。

医学系研究科博士課程のシラバスはこちらから。

科目情報

コースナンバリング	2-548i-238
科目名	データ構造とアルゴリズム
開講学期	前期
開講時期	１クォータ
曜日・校時	火４
単位数	2
授業担当教員	上田　俊、奥村　浩

講義情報

学士力番号

2. (2) プロフェッショナルとして課題を発見し解決する能力

曜／限追記

火曜日・4限

講義形式

講義・演習

講義概要

【授業概要】
プログラムの作成能力を高めるには，データ構造とそれを操作するアルゴリズムに関する知識が重要である．本講義では，データ構造とアルゴリズムに関する基本知識，およびアルゴリズムの計算量について説明する. 適宜，アルゴリズムを Python を用いて実装できるよう，演習を行う．

【カリキュラムにおけるこの科目の位置づけ】
本講義は「情報基礎概論」および「コンピュータプログラミング」の理解を前提とする．さらに、本講義は「プログラミング概論I・II・III」「プログラミング演習I・II・III」，「ゲーム理論と最適化手法」をはじめとした知能情報システム工学コースおよび情報ネットワークコースで開講している多くの専門科目 (講義，演習，実験) を理解するために必要不可欠な科目である．

開講意図

基本的なデータ構造とアルゴリズムについて，その概念，考え方，効率を理解し，応用する能力を育成する．

到達目標

1. 基本的なデータ構造とアルゴリズム理解し，Python プログラムとして実装できるようになる．
2. 適切なデータ構造とアルゴリズムを選択して，プログラムを作成できるようになる．

授業計画

回	内容	授業以外の学習本科目は、単位数×45時間の学修が必要な内容で構成されています。授業として実施する学修の他に、授業の内容を深めるために以下の事前・事後学修が必要です。
1	イントロダクション	正整数n部分和問題の実装
2	挿入ソート	挿入ソートアルゴリズムの実装
3	マージソート	マージソートアルゴリズムの実装
4	関数の増加	実行時間比較プログラムの実装
5	クイックソート	クイックソートアルゴリズムの実装
6	ソートの下界	中間レポートの作成
7	ナップサック問題	ナップサック問題の全探索アルゴリズムの実装
8	巡回セールスマン問題	巡回セールスマン問題の全探索アルゴリズムの実装
9	貪欲法	巡回セールスマン問題の貪欲アルゴリズムの実装
10	バックトラッキング法	巡回セールスマン問題のバックトラッキング法の実装
11	動的計画法	ナップサック問題の動的計画アルゴリズムの実装
12	数理計画問題	ナップサック問題の数理計画問題の実装
13	分枝限定法	ナップサック問題の分枝限定アルゴリズムの実装
14	計算複雑性理論	期末レポートの作成
15	NP完全問題	期末レポートの作成

成績評価の方法と基準

各回におけるプログラミング課題 (計12回) 計24点
中間レポート 38点
最終レポート 38点

プログラミング課題は Python による実装コードと実行結果で評価する．
中間レポート・最終レポートは，上記に加え，実装したアルゴリズムや得られた実行結果に関する考察で評価する．

開示する試験問題等

各回におけるプログラミング課題の Python コードは出題より2週間後に公開する．
中間・最終レポートの Python コードは出題より2週間後に公開する．各模範レポートは出題より4週間後に公開する．

開示方法

講義資料とともに，講義Webページで公開する．

教科書

資料名		版
著者名	発行所名・発行者名	出版年
備考（巻冊：上下等）		ISBN
Pythonで体験してわかるアルゴリズムとデータ構造
西澤弘毅, 森田光著	近代科学社	2018
		9784764905702

参考図書

資料名		版
著者名	発行所名・発行者名	出版年
備考（巻冊：上下等）		ISBN
アルゴリズムイントロダクション		第3版, 総合版
T. コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳	近代科学社	2013
		9784764904088

オフィスアワー

オフィスアワー: 水曜2限
また水曜4.5限にAV講義室に常駐する．

アクティブラーニング導入状況

アクティブラーニング導入状況
カテゴリー4	カテゴリー3	カテゴリー2	カテゴリー1	カテゴリー0
学生が自ら主体となって、学習の方向性を定め、問題解決に導くための時間です。PROBLEM BASED LEARNING	グループや個人で行った能動的学習の成果を、教室内外で発表し、その評価を受けたり、質問に対応したりすることにより、学修した内容を深化させるための時間です。OUTPUT	学生自らが自由に発言し、グループやペアでの協働活動により課題に取り組み、何らかの帰結に到達するための能動的学習の時間です。INTERACTION	学生からの自由な発言機会はないものの、授業時間中に得られた知識や技能を自ら運用して、問題を解いたり、課題に取り組んだり、授業の振り返りをしたりする能動的学習を行う時間です。ACTION	基本的に学生は着席のまま、講義を聞き、ノートをとり、知識や技能を習得に努める時間です。INPUT
0	0	5	20	75