2015 年 10 月 14 日 中村 篤祥 ２０１５年度後期「アルゴリズムとデータ構造」の講義に関して 1. 講義日程 以下の１５回の予定。講義はガイダンスも含めて１４回。１１／２５日の休講分はどこかで補講を行う予定 １０月１４日 （水） ２１日 （水） ２８日 （水） １１月０４日 （水） １１日 （水） １８日 （水） ？日 （？） ２５日 （水） １２月０２日 （水） ０９日 （水） １６日 （水） １月０６日 （水） １３日 （水） ２０日 （水） ２７日 （水） ２月０３日 （水） 第１回 第２回 第３回 第４回 第５回 第６回 第７回 休講 第８回 第９回 第１０回 第１１回 第１２回 第１３回 第１４回 第１５回 ガイダンス アルゴリズムと計算量 基本的なデータ構造 再帰 整列のアルゴリズム（１） 整列のアルゴリズム（２） 探索のためのデータ構造（１） 探索のためのデータ構造（２） 文字列照合アルゴリズム グラフとネットワークのアルゴリズム（１） グラフとネットワークのアルゴリズム（２） グラフトネットワークのアルゴリズム（３） 計算困難な問題を扱うには？ アルゴリズム関連の最近の話題 試験 2. 参考書 教科書は特に指定しないが、茨木先生の本と平田先生の本をベースに授業を組み立てる。 • 茨木俊秀著 「C によるアルゴリズムとデータ構造」 オーム社 ￥2,700+税 コンパクトなのに高度な内容まで触れており役に立つ本 • 平田富夫著 「アルゴリズムとデータ構造」 森北出版 ￥2,200+税 構成がオーソドックスでわかりやすい • コルメン、ライザーソン、リベスト著 「アルゴリズムイントロダクション」１、２巻 近代科学社 ￥4,000+税 MIT の計算機アルゴリズムの教科書として使われている本。非常に詳しい。 • 岩間一雄著 「アルゴリズム・サイエンス：出口からの超入門」 共立出版 ￥2,400+税 アルゴリズム関連の最近の話題をわかりやすく解説した面白い本。 • 渡辺治著 「教養としてのコンピュータ・サイエンス」 サイエンス社 ￥1,550+税 東工大の一般教養科目「コンピュータ・サイエンス入門」の教科書。コンピュータ・サイエンスの心を教える。 3. 評価 期末試験 (70 ％)、毎回行う演習 (30 ％) 4. 講義関連情報 電子掲示版 ホームページ http://prml.main.ist.hokudai.ac.jp/˜atsu/lecture alg.html 5. 質問等 居室： 情エレ棟１０階 10-01 E-mail: [email protected] 6. おまけ [問題]N 君は、処理 A,B を順次行うプログラムを作成する仕事を引き受けた。クライアントは１億件を１０日間で 処理できるプログラムを作成するように要求している。N 君がプログラムを完成させた時には、納品までに１０日 間を切っており、作成したプログラムがこの要件を満たしているか確かめるために十分な時間がなかった。そこで １万件の処理時間を調べたところ 86 秒であり、その 86 秒の内、処理 B にかかった時間が全体の 99.99%であるこ とがわかった。また、処理 B をソースコードをみて分析したところ、処理 B にかかる時間は処理件数に比例する ことがわかった。N 君は１億件でも１０日以内に終ると結論づけてよいか？よくない場合には理由を説明し、どう すれば処理時間の要件を (だいたい) 満していることを確かめられるかを答えよ。(86 × 10000 秒が１０日未満であ ることは正しい)
© Copyright 2024 ExpyDoc
