授業の主題
|
|
|
|
アルゴリズムの評価方法，基本的な問題のアルゴリズムの理解，ならびにアルゴリズム設計の一般的な技法が本授業の主題である．
|
| |
|
|
学修目標（到達目標）
|
|
|
|
プログラムを作成して計算を行うためには計算手順が必要であり，これはアルゴリズムと呼ばれる．アルゴリズムに求められるのは，正しい答えを速く計算することである．この正しさと速さを評価する方法を学ぶ．また，基本的なデータ構造ならびにアルゴリズムを学び，それらの性能を理解する．
|
| |
|
|
|
|
|
|
授業概要
|
|
|
第1回: アルゴリズムの評価: 正当性，時間と領域，多項式時間と指数時間
第2回: 計算量と漸近評価: RAM，時間計算量，O，o, Omega, omega, Theta
第3回: データ構造(1): 配列，ポインタ，スタック，キュー，連結リスト
第4回: データ構造(2): 2分探索木
第5回: データ構造(3): ハッシュ
第6回: ソート(1): マージソート，ヒープソート
第7回: ソート(2): クイックソート
第8回: ソート(3): 時間計算量の下界，期末試験
|
| |
|
|
評価方法と割合
|
|
評価方法
|
|
|
次項の項目及び割合で総合評価し、次のとおり判定する。
「Ｓ（達成度90％～100％）」、「Ａ（同80％～90％未満）」、
「Ｂ（同70％～80％未満）」、「Ｃ（同60％～70％未満）」を合格とし、
「不可（同60％未満）」を不合格とする。（標準評価方法）
|
| |
|
|
|
|
|
|
授業時間外の学修に関する指示
|
|
予習に関する指示
|
|
|
|
次回の講義内容について配布プリントを読んでくること．
|
| |
|
予習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
復習に関する指示
|
|
|
|
講義のあった当日に再度配布プリント・ノートにて復習すること．
|
| |
|
復習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
教科書・参考書
|
|
参考書
|
|
|
|
|
4-627-70251-5
|
|
上野修一, 高橋篤司共著
|
|
森北出版
|
2005
|
|
|
|
4-563-00791-9
|
|
A.V.エイホ, J.E.ホップクロフト, J.D.ウルマン著 ; 大野義夫訳
|
|
培風館
|
1987
|
|
|
|
978-4-7649-0408-8
|
|
T. コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳
|
|
近代科学社
|
2013
|
|
|
|
|
|
|
オフィスアワー等（学生からの質問への対応方法等）
|
|
|
|
電子メールで受け付ける．
|
| |
|
|
履修条件
|
|
|
|
電子情報通信学類(43001)とフロンティア工学類(42151)の学生の履修を優先する．その他の学類の学生の履修は事前に担当教員に許可を得ること．
|
| |
|
|
|
|
|
|
その他履修上の注意事項や学習上の助言
|
|
|
|
配布プリントは，教科書というよりはノートであり，必ずしもこれだけを読んで学べるようには書かれていない．授業内容と併せて初めて役に立つものであるので，この点を十分意識して授業に臨まれたい．
|
| |
|
|
|
|
|
|
|
|
|