|
計算機科学 K73 1201 |
|
|
第 3学期 月曜
6時限, 金曜 3時限（2単位） |
対象：主として社会工学類3年生 |
|
担当教員：繁野麻衣子3F 1112 電話853-5232 E-mail maiko@sk.tsukuba.ac.jp Office
hourメールでアポイントを取ること 山本芳嗣 3F 1007 電話853-5001 E-mail yamamoto@sk.tsukuba.ac.jp Office hour メールでアポイントを取ること 後藤順哉 3F 1024 電話853-5549 E-mail jgoto@sk.tsukuba.ac.jp Office hour メールでアポイントを取ること |
|
|
教科書：渡辺治著「教養としてのコンピュータ・サイエンス」サイエンス社(2001). 茨木俊秀著「Cによるアルゴリズムとデータ構造」昭晃堂(1999). 西原清一著「データ構造」オーム社(1993). |
|
|
授業概要・教育目標：コンピュータ・プログラミングの基礎となるデータ構造とアルゴリズム，計算の複雑性について学ぶ． |
|
|
授業計画： |
|
|
第1週 |
アルゴリズムとは？ アルゴリズムの記述 |
|
第2週 |
アルゴリズムの評価，計算量 |
|
第3週 |
文字列照合アルゴリズムの基本 |
|
第4週 |
Rabin-Karp Algorithm, Boyer-Moore Algorithm |
|
第5週 |
String-Matching Automata, Knuth-Morris-Pratt
Algorithm |
|
第6週 |
基本的なデータ構造（1）：リストの実現と基本操作 |
|
第7週 |
基本的なデータ構造（2）：スタックと待ち行列 |
|
第8週 |
整列（1）：バケットソート，選択ソート，挿入ソートなど |
|
第9週 |
整列（2）：ヒープソート，マージソート，クイックソートなど |
|
第10週 |
探索：2分探索木，ハッシュ |
|
成績評価：試験，レポート，出席の総合評価 |
|
備考：1〜3週担当:繁野，3〜5週担当:山本，6〜10週担当:後藤． 山本分のハンドアウトはhttp://www.sk.tsukuba.ac.jp/~yamamoto/からダウンロードして授業に持参すること． 先行要件として，なんでもよいのでプログラミング言語（C, JAVAなど）が使えること． |