計算機科学概論 -Introduction to Computer Science-
| 担当教員・研究室 | 配当年次 | 学期 | 種別 | 単位数 | 授業形態 | 開講年度 | ナンバリングコード | |||
|---|---|---|---|---|---|---|---|---|---|---|
|
3・4年 | 後期 | 選択 | 2 単位 |
|
2021 | SSI330 |
| アクティブラーニング |
|---|
| いいえ |
| 授業概要 |
|---|
| コンピュータサイエンスはとかく，単に生活に便利な技術を提供するためという低級な学問のように思われがちである。然し，それは，コンピュータが発明される以前の１９３０年代から３０年間位隆盛を誇り，一つの学問体系に発展した。その成果は深遠でかつ人類のうちたてた一つの知的金字塔であるといってよいだろう。ここでは，それらの脈々たる（狭義の）計算機科学の結果を概観し，“計算”や“情報処理”，それらの深さを体感するのが目的である。
計算機科学の内容に対してシステム情報学科の学生として恥ずかしくない計算機科学の知識を身に付け，それらに対してある程度理解することが目標である。代数学及び離散数学の基礎を踏まえて講義は進むが，計算機科学のテクニックの詳細を修得することまでは要求しないつもりである。学問としての理論計算機科学の一般常識が身に付けばと考える。遠隔授業を予定している。 |
| 授業における学修の到達目標 |
|---|
| この講義では，実際に様々なオートマトンの理論的設計や，計算量などの計算ができるようになるということを到達点とはしません．オートマトンと形式言語の関係の理解，計算量の考え方，Turing機械の停止問題、P vs.NP問題などの計算機科学の深遠な難問などについて、広く浅い知識の修得と、計算機科学の考え方の理解が目的となる．従って筆記試験はしない． |
授業計画
| 回数 | 授業、事前・事後学習 | 時間 | |
|---|---|---|---|
| 1 | 事前学習 | シラバスを熟読する | 2.0 |
| 授業 | .計算機科学の意義と概要 | ||
| 事後学習 | 講義内容を整理しレポート作成する．演習問題を復習する | 2.0 | |
| 2 | 事前学習 | 正規表現 | 2.0 |
| 授業 | 正規表現 | ||
| 事後学習 | 講義内容を整理しレポート作成する．演習問題を復習する | 2.0 | |
| 3 | 事前学習 | オートマトンとはどんなものかinternetで検索，調査してくる | 2.0 |
| 授業 | 有限オートマトン | ||
| 事後学習 | 講義内容を整理しレポート作成する．演習問題を復習する | 2.0 | |
| 4 | 事前学習 | 形式言語とはどんなものかinternetで検索，調査してくる | 2.0 |
| 授業 | 文脈自由言語 | ||
| 事後学習 | 講義内容を整理しレポート作成する．演習問題を復習する | 2.0 | |
| 5 | 事前学習 | プッシュダウンオートマトンとはどんなものかinternetで検索，調査してくる | 2.0 |
| 授業 | プッシュダウンオートマトン | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 6 | 事前学習 | 文脈依存言語，線形高速オートマトンについてinternetで検索，調査してくる | 2.0 |
| 授業 | チョムスキー階層 | ||
| 事後学習 | 講義内容を整理しレポート作成する．演習問題を復習する | 2.0 | |
| 7 | 事前学習 | ゼロ型文法についてinternetで検索，調査してくる | 2.0 |
| 授業 | 句構成文法 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 8 | 事前学習 | チューリングの業績について調査してくる | 2.0 |
| 授業 | チューリングマシンと万能チューリングマシン | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 9 | 事前学習 | 計算可能とはどういうことか考えてくる | 2.0 |
| 授業 | 計算可能関数と帰納的可算言語 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 10 | 事前学習 | コンピュータはどのような問題でも解きうるのか、そうではないかも知れないか考えてくる | 2.0 |
| 授業 | Turing 機械の停止問題 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 11 | 事前学習 | 計算とはそもそも何であるのか考えてくる | 2.0 |
| 授業 | チャーチ・チューリングの提唱 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 12 | 事前学習 | コンピュータはどのような処理が得意であり，どのような処理が不得意であるのか各自考えてくる | 2.0 |
| 授業 | 計算量の理論の基礎 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 13 | 事前学習 | 四則計算や今までに習った計算で，どのような計算がコンピュータにとって困難そうか自分なりに考えてくる | 2.0 |
| 授業 | 計算量の理論の具体例 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 14 | 事前学習 | クレイ数学研究所のミレニアム問題について調べてくる | 2.0 |
| 授業 | P&NP完全問題など | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 15 | 事前学習 | D-wave,Google,IBMの量子コンピュータの記事についてInternetで調べてくる | 2.0 |
| 授業 | 量子情報科学入門 | ||
| 事後学習 | 講義内容を整理しレポート作成する。演習問題を復習する | 2.0 | |
| 成績評価の方法およびその基準 |
|---|
| 次項の項目及び割合で標準評価基準に基づき総合評価する。
□試験： 0 % □小テスト： 0 % ■レポート：50 % ■演習課題： 50 % □その他[ ] |
| 課題(試験やレポート等)に対するフィードバック方法 |
|---|
| レポートのフィードバックは，主に授業中にコメントする． |
| 教科書 |
|---|
| なし |
| 参考書・Webサイト |
|---|
| なし |
| 単位習得が望ましい科目 |
|---|
| 情報科学基礎，情報理論，離散数学Ｉ |
| 備考 |
|---|
| なし |
| 担当教員の実務経験 |
|---|
| 実務経験なし |