| 曜日・時限 | クラス名 | 担当教員 |
|---|---|---|
| 月曜1, 2 | 1a(CS2) | 上里 友弥 |
| 月曜1, 2 | 1b(CS2) | Defago Xavier |
| 月曜3, 4 | 2a(CS2) | 坂本 龍一 |
| 月曜3, 4 | 2b(CS2) | Defago Xavier |
| 月曜3, 4 | EN(CS2) | Bonnet Francois |
| 水曜1, 2 | 3a(CS2) | 山田 聖 |
| 水曜1, 2 | 3b(CS2) | 仲道 嘉夫 |
| 水曜3, 4 | 4a(CS2) | 脇田 建 |
| 水曜3, 4 | 4b(CS2) | 永藤 直行 |
| 木曜1, 2 | 5a(CS2) | 河野 友亮 |
| 木曜1, 2 | 5b(CS2) | 奥村 圭司 |
| 木曜3, 4 | 6a(CS2) | 大村 英史 |
| 木曜3, 4 | 6b(CS2) | 奥村 圭司 |
【注意】コンピュータサイエンス第一(3Q)と同第二(4Q)でクラスを変わる場合には、プログラミング環境が変わることがあるので注意すること。
クラス1a(CS2)（担当：上里）
- 再帰
- プログラミングには再帰という重要かつ広範な考え方がある。ここではその側面の一つ「大きな問題を直接は解かずに、小さく簡単な問題に分割し、それぞれを解く」という発想について、具体的な問題を解くことで習熟し、使えるようになることを目指す。
- ソート問題とアルゴリズム
- プログラミングでも、一つの問題に対して複数の解き方がありうる。そのような具体例として現実的にも重要な、データを何らかの順序で整列（ソート）する問題と、様々な解法（アルゴリズム）を学ぶ。また、それぞれのアルゴリズムには異なる特性があることも理解する。
- 実数の表現
- 必要なデータを、自分の目的に合わせてプログラム上で最適な形で表現することは重要である。実数（≒ 無限数列）はその良い例であり、代表的な「浮動小数点表現」について学ぶ。これは実数を有限桁で近似する方法で、計算機にとって都合が良い一方で「誤差」が避けられない。そうした誤差がどう生じるかやその影響などを、具体的な計算を通して学ぶ。
- 計算可能性と計算量
- ソート問題のように「計算可能な ≒ プログラムを書いて解ける」問題もある。それでは「計算不可能」なほど難しい問題もあるだろうか？ こうした計算可能性の分野を学ぶ。また、計算可能な問題の中にも、難易度と呼べるもの（計算複雑さ）がある。そうした難易度についても、具体的な問題を通して探っていく。
クラス1b(CS2), 2b(CS2) （担当：Defago）
- キーワード
- 再帰，ソートアルゴリズム，アルゴリズム，計算量，インタプリタ・コンパイラ，抽象構文木，最短経路問題
- 【再帰】
- 例えば，階乗 \(n!\) の計算を，\(n! = n \times (n − 1)!, 0! = 1\) と定義出来る．このように，演算 ! の機能を ! 自体を使って書くことを再帰という．再帰は，アルゴリズムやプログラムを作る際にとても強力な道具となるので，再帰を理解し，使えるようになる事を目指す．
- 【ソートアルゴリズム】
- ばらばらに並んだデータを大きさの順に整列させる問題をソートという．これに対す るアルゴリズムは非常にたくさん知られているが，この授業では特に挿入ソート，マージソート，クイックソートなどを扱う．これらに関してゲームで遊んだりプログラム実験をしたり数学的な解析をしたりして多角的に理解することを目標とする．
- 【インタプリタ・コンパイラ工房】
- インタプリタとコンパイラの違いを理解するために，Python 言語で単純なプログラミング言語を実行できるインタプリタ，そしてそのコンパイラを順番に作る．その際にスタックと抽象構文木のデータ構造も学ぶ．
- 【グラフと最短経路問題】
- 計算の活用には良いアルゴリズムが不可欠である．最短経路問題に対するアルゴリズムの設計を題材に，アルゴリズムの効率の良し悪しの違い，それを 解析し議論する方法について学ぶ．
クラス2a(CS2)（担当：坂本）
- 【再帰】
- 再帰はあるプログラムの中から自分自身を呼び出すものである。本講義では再帰の仕組みについて学ぶ。
- 【ソートアルゴリズム】
- ソートは多数のデータをあるルールに従って整列させるアルゴリズムである。本講義ではいくつかのソートアルゴリズムについて学び、アルゴリズムによる計算量の違いについて学ぶ。
- 【計算機における数値表現】
- 計算機では音声などの連続量を表現できないため、離散化し計算機で扱いやすい表現に変換する。本講義では離散化や浮動小数点といった計算機内部で連続値や数値を表現するための方法について学ぶ。
- 【仮想マシン】
- 仮想マシンはソフトウェアの実行環境を仮想的に再現するプログラムであり、身の回りの様々な場所で用いられている。本講義ではWebブラウザ内で動作するPython向け仮想マシンを用いて、仮想マシンの特徴や性能について学ぶ。
クラス3a(CS2) （担当：山田）
- 【再帰】
- 再帰アルゴリズムは，自分自身を呼び出す関数を用いて計算を行うアルゴリズムである．再帰アルゴリズムを理解し，扱えるようになることを目標とする．
- 【ソート】
- ソートとは，データを一定の規則に従って並べ替える処理である．いくつかのソートアルゴリズムとその計算量を理解し，ソートアルゴリズムに限らず，様々なアルゴリズムの効率を評価する方法も学ぶことを目標とする．
- 【グラフ上の最短経路問題】
- グラフとは，頂点と辺からなるデータ構造であり，ネットワーク構造を表現するために用いられる．グラフ上の問題の一つである最短経路問題について，それを計算するためのアルゴリズムと実装，およびその効率化についてを学ぶことを目標とする．
- 【コンパイラとインタプリタ】
- プログラムをコンピュータ上で実行するための方法には，コンパイラを用いる方法とインタプリタを用いる方法がある． 簡単なプログラミング言語を定義し，その言語で書かれたプログラムをPythonへ変換するコンパイラと同プログラムを実行するインタプリタを作成し，それらの仕組みを理解することを目標とする．
クラス3b(CS2)（担当：仲道）
- 【プログラミングテクニック】
- 各種問題に対し，再帰，データ構造，各種アルゴリズム等適切な手法を活用することで，簡単に目的を実現できるプログラムを作れることを学ぶ。また，計算と思えない，迷路探索等もコンピュータで扱えることを理解する。
- 【計算誤差】
- 10 進小数のほとんどが 2 進数に変換すると，無限小数（循環小数）になる。コンピュータ内部で扱う数の表現方法と、計算のアルゴリズムによって大きな誤差が出ることがある。それらの原因を理解することを通して，誤差の少ない計算方法を考える。
- 【計算量と工夫】
- 計算量 \(O\) （オーダー）の考え方を体験するために、ソートアルゴリズム \(O(n^2)\), \(O(N \log N)\) のプログラムを走らせ体験する。また，NP 問題である部分和問題を テーマにその計算量を知ると共に，計算量を減らす方法を考える。
- 【計算可能性】
- コンピュータサイエンスの典型的な問題である停止性判定問題を通して，プログラムではない、論理的な考え方に触れる。
クラス 4a(CS2) （担当：脇田）
- キーワード
- 再帰，ソートアルゴリズム，コンピュータでの数の扱い，計算量と計算可能性の理論。
- 【再帰】
- アルゴリズム設計の強力な基本技である再帰について理解して使えるようになることを目標にする。
- 【ソートアルゴリズム】
- ばらばらに並んだデータを大きさの順に整列させる問題をソートという。さまざまなソートアルゴリズムの比較を通して、アルゴリズムごとの特性とともに、アルゴリズムの性能について数学的に論じる方法について学ぶことができる。アルゴリズムとプログラミングについて多面的な理解を目標とする。
- 【コンピュータでの数の扱い】
- コンピュータで数（特に実数）の計算をすると変な誤差が入ることがある。その原因を理解することを目標とする。
- 【計算量，計算可能性の理論】
- 問題をコンピュータで解くのにどれだけの時間がかかるか，あるいはどんなに時間をかけても解けないのか，といったことを数学的に研究する分野をかいまみることを目標とする。
- 【プログラミング環境】
- Google Colaboratory を用いる。
クラス4b(CS2)（担当：永藤）
- 【再帰】
- 再帰的定義はアルゴリズムを設計する上で強力な道具となる．これを演習で実感することを目標とする．また，再帰と繰り返し文の関係についても考察する．
- 【良いアルゴリズム，悪いアルゴリズム】
- 計算資源を浪費せずに計算を行う方法について学ぶ．良いアルゴリズムとはどんなものかと解析方法について理解することを目標とする．
クラス5a(CS2)（担当：河野）
- 【アルゴリズム】
- アルゴリズムとは、一言で言えば「計算方法」の事である。ひとつの計算をするにしても、様々な計算方法が考えられ、プログラムとして実装する場合もそれが反映される。そこで、たくさんのアルゴリズムの基本となる概念の一部、再帰、ソート、といったもの等を扱う。同じ計算をするプログラムの中にも色々な意味で良いアルゴリズムや、様々な性質を持つアルゴリズムが考えられるが、再帰やソートといった概念に関連した、良いアルゴリズムとはどういったものかということの一部も扱う。
- 【確率や数字の扱い】
- コンピューターで確率や数値を扱う場合、様々な制限や誤差が生じる。 そのため特殊な計算方法が必要になる場合があり、それらの基本を扱う。
- 【計算量、計算可能性理論】
- コンピューターで計算できる事や、ある計算をするときの効率には理論上限界があり、どのような限界があるのかを学ぶ。これらはコンピューターの性能等によらない理論的な枠組みで議論される。
- 【グラフ上の問題】
- グラフとは、集合と集合間の様々な関係で構成される構造体であり、科学上の様々な場面で現れる。計算機科学では、グラフ上の数々の問題が扱われており、それらの問題の特徴、アルゴリズムの検証等を行う。
- 【量子情報科学】
- 量子コンピュータではいわゆる通常用いられるコンピュータとは根本的に違う概念が用いられる。そのような量子コンピュータの基本的な部分をほんの少しだけ学習する。
クラス5b(CS2), 6b(CS2)（担当：奥村）
- 【再帰】
- 関数が直接または間接的に自分自身を呼び出すことを指す再帰について、階乗などの例を通して学ぶ。
- 【ソートアルゴリズム】
- データの並び替え(ソート)を例として、いくつかのアルゴリズムについての考えを学ぶ。また、計算量の視点からアルゴリズムを評価する。
- 【数値計算と誤差】
- コンピュータ上での数値表現と丸め誤差、桁落ち・情報落ちなどについて学ぶ。
- 【常微分方程式の数値解法】
- 常微分方程式の数値解法について、離散化の基本的な考えとアルゴリズムを学ぶ。
- 【プログラミング環境】
- Anaconda/JupyterLab環境でPythonをあつかう。原則として、演習室Mac(教育用電子計算機システム)に導入されているものを利用する。ただし各自の責任において、同等の環境を構築した持ち込みデバイス(BYOD)や、Google Colaboratoryを利用してもよい。
クラス6a(CS2)（担当：大村）
- 【再帰】
- 「この文は嘘である」のように，ある記述が自身を参照して言うことを「再帰」という．コンピュータサイエンスにおいてもこの考えは重要である．私たちの日常にある再帰をとおして理解し，プログラミング技術として使いこなすことを目的とする．
- 【アルゴリズム概要】
- アルゴリズムとは問題を解決するための計算の手順のことを言う．紀元前三世紀に考えられた最大公約数を求めるアルゴリズムを題材に，アルゴリズムとプログラムについて学習する．
- 【ソートアルゴリズム】
- データを並び替えるアルゴリズムをソートアルゴリズムという．いくつかのソートアルゴリズムを学習し，アルゴリズムの違いについて理解することを目的とする．
- 【データ構造と探索】
- 複数のデータを効率よく抽出するためには，データを整理して格納しておく必要がある．この格納方法をデータ構造という．データ構造と探索の整理方法について学習する．