科目名[英文名]
アルゴリズム序論   [Introduction to Algorithms]
区分 工学部専門科目等  選択必修   単位数 2 
対象学科等   対象年次 24  開講時期 1学期 
授業形態 1学期  時間割番号 022805
責任教員 [ローマ字表記]
宮代 隆平   [MIYASHIRO Ryuhei]
所属 工学部 研究室   メールアドレス

概要
本講義では、プログラミングで必須となるアルゴリズムの基本を講義する。
特に、アルゴリズムを評価する方法である計算量、基本的な問題に対するアルゴリズム、アルゴリズムを実装する際に必要となるデータ構造の知識を述べる.
アルゴリズムとデータ構造に関連する一通りの基礎知識を習得し、効率の良いプログラムを開発する能力を身につける。
講義に際しては、座学での知識の教授と演習問題ならびに定期試験を実施することで、アルゴリズムに関する知識と理解をより確実なものとする。
到達基準
- プログラミング上の課題が与えられた時,適切なアルゴリズムを選択することができる
- 与えられたアルゴリズムを見て計算量が出せ,適切なデータ構造を選んでプログラミングできる
- 本科目のディプロマ・ポリシーの観点は履修案内のカリキュラムマップを参照してください
授業内容
第1回 アルゴリズムとは何か:アルゴリズム,データ構造,計算量,プログラム
第2回 計算ステップ数:プログラムの実行速度
第3回--第4回 計算量:オーダー記法,アルゴリズムの計算量
第5回 探索と単純なソート:線形探索,二分探索,選択ソート,挿入ソート
第6回 マージソート:マージソート,分割統治法,ソートの計算量の下限
第7回 クイックソート:クイックソートとその計算量,最悪ケースと平均ケース
第8回 空間計算量:メモリの消費
第9回 リスト:基本的なデータ構造とその実装
第10回 ハッシュ:探索の効率化,その実装
第11回 スタックとキュー:スタックとその実装,キューとその実装
第12回 優先度キューとヒープ:優先度キューとその実装,ヒープ,二分ヒープとその実装
第13回 ヒープソート:ヒープソートとその実装
第14回 効率的なプログラムとは
第15回 まとめ
定期試験
履修条件・関連項目
情報工学科/知能情報システム工学科の1年次で開講されるプログラミングの講義および演習で扱う程度のプログラミング能力が必要である。
授業時間30時間に加え、授業で配布する教材や後述する参考書を使って本学の標準時間数に準ずる予習と復習を行うこと。
テキスト・教科書
配布資料を使用する。
参考書
- 新版 C言語によるアルゴリズムとデータ構造
柴田,辻,ソフトバンククリエイティブ,2005.
- プログラミングの宝箱 アルゴリズムとデータ構造
紀平,春日,ソフトバンククリエイティブ,2003.

成績評価の方法
講義中に適宜、演習問題で知識の確認を行う。
学期の中間に行われるレポート課題(33%)および定期試験(67%)により評価する。
教員から一言
今後プログラミングをしていく上での基礎体力となる部分です.
毎回出席して,自分の手で小テストの問題を解いていきましょう.
キーワード
計算量,アルゴリズム,データ構造
オフィスアワー
授業の前後,またはemailで予約を取ること。
備考1
備考2
参照ホームページ
開講言語
日本語
語学学習科目
更新日付
2019/03/13 19:59:07