科目名 Course Title	データ構造とアルゴリズム［24C5007］ Data Structures and Algorithms
授業言語 Language	Japanese
科目区分・科目種	情報科学科	クラス	情報科学科
コンピテンシー	○問題解決力	ｶﾗｰｺｰﾄﾞ
単位数	2.0単位	履修年次	1年

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

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

授業の形態
講義，演習

教科書・参考文献
参考書：石畑清著「アルゴリズムとデータ構造」（岩波講座、ソフトウェア科学３）1989 年（ISBN: 9784000103435）。 https://www.iwanami.co.jp/book/b475655.html

ＡＬＨ区分
ＡＬＨを実施しない

アクティブラーニングの技法
復習テスト

評価方法・評価割合
期末試験=65% 程度。中間試験、期末試験の採点により成績をつける。配分は問題の難易度により変化する。，中間試験=35% 程度。中間試験、期末試験の採点により成績をつける。配分は問題の難易度により変化する。

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

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

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

学生へのメッセージ
データ構造とアルゴリズムは、情報科学の基礎科目の中でも中核となる重要な科目です。ここで学ぶ概念はどのようなプログラミングをする上でもかかせないものです。基本的な考え方から、それを使ったプログラミングまで、しっかりと確実に習得するよう心がけて下さい。

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