授業科目名 : アルゴリズムとデータ構造入門

科目コード 91150
配当学年 1年
開講年度・開講期 平成30年度・後期
曜時限 月曜・1時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
授業形態 講義・演習
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・鹿島久嗣

授業の概要・目的

コンピュータのプログラムは具体的な計算の手続きであるアルゴリズムと、これらが処理する情報を適切に管理するデータ構造から構成される。 本講義では、アルゴリズムやデータ構造の基本的な考え方やその具体的な設計法、またコンピュータサイエンスにおける重要な概念について学ぶ。

成績評価の方法・観点及び達成度

中間試験(講義内で指定する)と期末試験による

到達目標

到達目標は以下のとおりである: ・計算機の数理的モデルと、計算量の概念について理解する ・基本的なアルゴリズムと基本的なデータ構造について理解する ・分割統治法や動的計画法を含むアルゴリズムの設計法について理解する ・NP完全・NP困難などの難しい問題のクラスと、これらへの対処法について理解する ・グラフアルゴリズム、近似アルゴリズム、オンラインアルゴリズムなどの基本的事項について理解する

授業計画と内容

項目 回数 内容説明
導入 1 講義の概要
基本アルゴリズム 2.5 ソートや検索などの代表的なアルゴリズムについて学ぶ
基本データ構造 2.5 リスト、スタック、キュー、二分探索木、ヒープ、ハッシュ等の基本的なデータ構造について学ぶ
アルゴリズムの設計法 2 分割統治法、動的計画法などのアルゴリズムの設計法について学ぶ
グラフアルゴリズム 2 グラフや木の定義、深さ・幅優先探索、最短路などの基本的なアルゴリズムについて学ぶ
計算複雑度 3 P、NP、NP完全、NP困難などの計算複雑度の基礎的な概念について学ぶとともに、難しい問題への対処法などを学ぶ
発展的話題 1 近似アルゴリズム・オンラインアルゴリズムなどの発展的な話題について学ぶ
学習到達度の確認 1 期末試験

教科書

講義内で指定する

参考書等

講義内で指定する

履修要件

授業外学習(予習・復習)等

授業URL

その他(オフィスアワー等)

受講生の理解度や進捗状況などに応じて一部省略や追加がありえます