情報科学講究１

科目名	情報科学講究１
教員名	齋藤明
単位数	2	学年	3	開講区分	文理学部
科目群	情報科学科
学期	前期	履修区分	必修

授業概要	離散数学とプログラミング
授業のねらい・到達目標	教科書の輪読とプログラム実習を通して、４年次の卒業研究で必要となる力を養う。離散数学の各種の話題を通して、着想を得ること、及び得られた着想を論理の力を通して形にすることができるようになることを目標とする。またプログラム実習を通して、高度なプログラミングの力を身につけることができる。この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法	配布プリントの各章を受講者に割り振り、輪読を行う。また離散数学を題材とするプログラミング実習を行う。本授業の事前・事後学習は，各２時間の学習を目安とする。
履修条件	学科内規による。

授業計画
1	授業のイントロダクションを行う。授業の進め方や資料の読み進め方などを学ぶ。 [事前学習] 講究は遺族説明会時に配付された資料を読んでおく。 [事前学習] 配布プリント8～20ページを読んでおく。
2	授業のイントロダクションを行う。授業の進め方や資料の読み進め方などを学ぶ。 [事前学習] 講究配属説明会時に配付された資料を読んでおく。 [事前学習] 配布プリント8～20ページを読んでおく。
3	色を塗ることによる配置問題へのアプローチを学ぶ。 [事前学習] 配布プリント21～32ページを読んでおく。 [事前学習] 穴が空いた配置への発展問題を解いてみる。
4	１対１対応を使った数え上げ問題へのアプローチを学ぶ。 [事前学習] 配布プリント33～46ページを読んでおく。 [事前学習] トーナメントの個数に関する発展問題を解く。
5	鳩の巣原理を学ぶ。 [事前学習] 配布プリント47～62ページを読んでおく。 [事前学習] 鳩の巣原理を使う問題を１つ自作する。
6	平均を用いた最大値、最小値の評価法を学ぶ。 [事前学習] 配布プリント63～76ページを読んでおく。 [事前学習] 教科書の例題の発展問題を解く。
7	各自が作った鳩の巣原理の問題の品評会を行う。 [事前学習] 自作した問題とその解答を要領よく伝えるための準備をする。 [事前学習] 品評会で得たコメントを吟味する。
8	不等式の粗い評価の方法を学ぶ。 [事前学習] 配布プリント67～90ページを読んでおく。 [事前学習] 対数式の粗い評価に関する問題を解く。
9	ハミルトン閉路問題を通して構造を理解する方法を学ぶ。 [事前学習] 配布プリント91～106ページを読んでおく。 [事前学習] ハミルトン閉路をもたないグラフを組織的に生成する方法を考える。
10	例題を通して思考実験の方法を学ぶ。 [事前学習] 配布プリント107～118ページを読んでおく。 [事前学習] 配置問題に関する教科書の問題を発展させる。
11	オーダーに基づく議論を学習する。 [事前学習] 配布プリント119～134ページを読んでおく。 [事前学習] オーダーの違いが感覚的に分かる例をインターネットなどで探る。
12	着想を証明やアルゴリズムに仕上げる手法を学ぶ。 [事前学習] 配布プリント119～134ページを読んでおく。 [事前学習] Oreの定理を元に、実際に証明を仕上げてみる。
13	英語文献の読み方に関する概要を学ぶ。 [事前学習] 前回講義で新たに配布する英語文献プリントの1～4ページを読んでおく。 [事前学習] Section1.1のExercise 1を解く。
14	グラフ理論に関する基本用語を英語で学ぶ。 [事前学習] 英語文献プリントの5～9ページを読んでおく。 [事前学習] Section1.1のExercise 2～9を解く。
15	部分グラフ、正則グラフの概念を英語で学ぶ。 [事前学習] 英語文献プリントの9～16ページを読んでおく。 [事前学習] Section1.1のExercise 10～12を解く。

その他
教科書	教科書は使用しない。
参考書	使用しない
成績評価の方法及び基準	授業参画度(100%) 授業参画度は、ディスカッションを通して測られる事前準備状況と議論の深度、および発表の質で評価される。
オフィスアワー	毎週金曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールにてアポイントを取ること。電子メールアドレスは授業初回に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合にはそちらを優先する。