データ構造とアルゴリズム[22C5007]

科目名
Course Title
データ構造とアルゴリズム[22C5007]
Data Structures and Algorithms
授業言語
Language
Japanese
科目区分・科目種 情報科学科 クラス 情報科学科
CCBM キャリアデザイン  
単位数 2.0単位 履修年次 1

担当教員 淺井 健一
学期 後期
曜日・時限・教室
木曜 3 4 理学部2号館507室

受講条件・その他注意
C 言語によるある程度のプログラミングができることを仮定する。

授業の形態
講義,演習,対面授業のみ,実施方法検討中

教科書・参考文献
参考書:石畑清著「アルゴリズムとデータ構造」(岩波講座、ソフトウェア科学3)

ALH区分
通常授業として実施(11・12限等)

評価方法・評価割合
期末試験=基本的に中間試験、期末試験の採点により成績をつける,中間試験=基本的に中間試験、期末試験の採点により成績をつける,小論文(レポート)=授業内容理解のため、簡単なレポート問題をほぼ毎回、出題する。

主題と目標
本講義では、配列、リスト、木構造といった基本的なデータ構造と、それを使った各種の探索アルゴリズム、整列アルゴリズム等を学習する。また、アルゴリズムにおいて重要となる正当性、停止性、計算量について学習する。

授業計画
第1回
アルゴリズムと計算量についての概要
第2回
線形探索アルゴリズムとその正当性
第3回
線形探索アルゴリズムの計算量、番兵による効率化
第4回
2分探索アルゴリズムとその正当性、計算量
第5回
整列アルゴリズム(選択法)の正当性、計算量
第6回
整列アルゴリズム(挿入法)の正当性、計算量
第7回
整列アルゴリズム(シェルソート)の正当性、計算量
第8回
ボトムアップアルゴリズムのまとめ
第9回
再帰を使った整列アルゴリズム(挿入法)
第10回
高速な整列アルゴリズム(クイックソート)の正当性
第11回
高速な整列アルゴリズム(クイックソート)の計算量
第12回
動的なデータ構造(リスト)
第13回
動的なデータ構造(木構造)と木を使った探索アルゴリズム、計算量
第14回
平衡木と平衡木を使った探索アルゴリズム、計算量
第15回
ハッシュを使った探索アルゴリズム

時間外学習
授業内容の理解度をチェックする簡単なプログラミング課題を各自、時間外に行う。ALH は行わず 15 回、授業を行う。

学生へのメッセージ
データ構造とアルゴリズムは、情報科学の基礎科目の中でも中核となる重要な科目です。ここで学ぶ概念はどのようなプログラミングをする上でもかかせないものです。基本的な考え方から、それを使ったプログラミングまで、しっかりと確実に習得するよう心がけて下さい。
 今年度は、基本的にオンラインで授業を行う。大学が指定する回と初回は対面の授業とオンラインの授業を併用する。いずれも対面の授業に出るのは必須とはしない。

学生の問い合わせ先
直接またはメールで教員まで。