コンピュータサイエンス第二 (2022年度)

曜日・時限 クラス名 担当教員 クラス別ホームページ
月曜1, 2 1a(CS2) 熊澤 努 T2SCHOLA参照
月曜1, 2 1b(CS2) Defago Xavier  
月曜3, 4 2a(CS2) 脇田 建 T2SCHOLA参照
月曜3, 4 2b(CS2) Defago Xavier  
月曜3, 4 EN(CS2) Bonnet Francois Refer to T2SCHOLA
水曜1, 2 3a(CS2) 永藤 直行 T2SCHOLA参照
水曜1, 2 3b(CS2) 仲道 嘉夫  
水曜3, 4 4a(CS2) 南出 靖彦 T2SCHOLA参照
水曜3, 4 4b(CS2) 永藤 直行 T2SCHOLA参照
木曜1, 2 5a(CS2) 河野 友亮 リンク
木曜1, 2 5b(CS2) 伊知地 宏 リンク
木曜3, 4 6a(CS2) 大村 英史 リンク
木曜3, 4 6b(CS2) 伊知地 宏 リンク

【注意】コンピュータサイエンス第一(3Q)と同第二(4Q)でクラスを変わる場合には、プログラミング環境が変わることがあるので注意すること。


クラス1a(CS2)(担当:熊澤)

3a(CS2) 担当: 熊澤努

本講義ではアルゴリズムの基本を中心に学ぶ.

【再帰】
再帰はコンピュータサイエンスを理解するうえで欠かせない技法である.授業ではやさしい例を通じて再帰の考え方を習得する.
【アルゴリズム入門】
最大公約数の計算を題材として,アルゴリズムについて学ぶ.再帰の使い方やアルゴリズムの効率を解析する計算量理論も具体的に学習する.
【ソートアルゴリズム・探索アルゴリズム】
ソートアルゴリズムはデータを並び替えるアルゴリズムである.数多くのアルゴリズムが知られている中で,授業では代表的なものを紹介する.また,多数のデータから特定のデータを探す探索アルゴリズムも学ぶ.
【グラフ探索】
コンピュータサイエンスでよく扱われるグラフを用いた探索問題とその解き方を理解する.
【機械学習の基本】
近年注目を集めている機械学習の考え方を知る.例として,データをグループ化するクラスタリングを取り上げる.

クラス1b(CS2), 2b(CS2) (担当:Defago)

キーワード
再帰,ソートアルゴリズム,アルゴリズム,計算量,インタプリタ・コンパ イラ,抽象構文木,最短経路問題
【再帰】
例えば,べき乗 \(n!\) の計算を,\(n! = n \times (n − 1)!, 0! = 1\) と定義出来る.このように,演算 ! の機能を ! 自体を使って書くことを再帰という.再帰は,アルゴリズムやプログラムを作る際にとても強力な道具となるので,再帰を理解し,使えるようになる事を目指す.
【ソートアルゴリズム】
ばらばらに並んだデータを大きさの順に整列させる問題をソートという.これに対す るアルゴリズムは非常にたくさん知られているが,この授業では特に挿入ソート,マージソート,クイックソートなどを扱う.これらに関してゲームで遊んだりプログラム実験をしたり数学的な解析をしたりして多角的に理解することを目標とする.
【インタプリタ・コンパイラ工房】
インタプリタとコンパイラの違いを理解するために,Python 言語で単純なプログラミング言語を実行できるインタプリタ,そしてそのコンパイラを順番に作る.その際にスタックと抽象構文木のデータ構造も学ぶ.
【グラフと最短経路問題】
計算の活用には良いアルゴリズムが不可欠である.最短経路問題に対するアルゴリズムの設計を題材に,アルゴリズムの効率の良し悪しの違い,それを 解析し議論する方法について学ぶ.

クラス 2a(CS2) (担当:脇田)

キーワード
再帰,ソートアルゴリズム,コンピュータでの数の扱い,計算量と計算可能性の理論。
【再帰】
アルゴリズム設計の強力な基本技である再帰について理解して使えるようになることを目標にする。
【ソートアルゴリズム】
ばらばらに並んだデータを大きさの順に整列させる問題をソートという。さまざまなソートアルゴリズムの比較を通して、アルゴリズムごとの特性とともに、アルゴリズムの性能について数学的に論じる方法について学ぶことができる。アルゴリズムとプログラミングについて多面的な理解を目標とする。
【コンピュータでの数の扱い】
コンピュータで数(特に実数)の計算をすると変な誤差が入ることがある。その原因を理解することを目標とする。
【計算量,計算可能性の理論】
問題をコンピュータで解くのにどれだけの時間がかかるか,あるいはどんなに時間をかけても解けないのか,といったことを数学的に研究する分野をかいまみることを目標とする。
【プログラミング環境】
Google Colaboratory を用いる。

クラス3b(CS2)(担当:仲道)

【プログラミングテクニック】
各種問題に対し,再帰,データ構造,各種アルゴリズム等適切な手法を活用することで,簡単に目的を実現できるプログラムを作れることを学ぶ。また,計算と思えない,迷路探索等もコンピュータで扱えることを理解する。
【計算誤差】
10 進小数のほとんどが 2 進数に変換すると,無限小数(循環小数)になる。コンピュータ内部で扱う数の表現方法と、計算のアルゴリズムによって大きな誤差が出ることがある。それらの原因を理解することを通して,誤差の少ない計算方法を考える。
【計算量と工夫】
計算量 \(O\) (オーダー)の考え方を体験するために、ソートアルゴリズム \(O(n^2)\), \(O(N \log N)\) のプログラムを走らせ体験する。また,NP 問題である部分和問題を テーマにその計算量を知ると共に,計算量を減らす方法を考える。
【計算可能性】
コンピュータサイエンスの典型的な問題である停止性判定問題を通して,プログラムではない、論理的な考え方に触れる。

クラス3a(CS2), 4b(CS2)(担当:永藤)

【再帰】
再帰的定義はアルゴリズムを設計する上で強力な道具となる.これを演習で実感することを目標とする.また,再帰と繰り返し文の関係についても考察する.
【良いアルゴリズム,悪いアルゴリズム】
計算資源を浪費せずに計算を行う方法について学ぶ.良いアルゴリズムとはどんなものかと解析方法について理解することを目標とする.

クラス4a(CS2)(担当:南出)

キーワード
再帰,ソートアルゴリズム,コンピュータでの数の扱い,計算量と計算可能性の理論。
【再帰】
再帰とはアルゴリズム設計の強力な基本技である。ここでは再帰を理解して使えるようになることを目標にする。
【ソートアルゴリズム】
ばらばらに並んだデータを大きさの順に整列させる問題をソートという。これに対するアルゴリズムは非常にたくさん知られているが,この授業では特にバブルソート,挿入ソート,マージソート,クイックソートを扱う。これらに関してゲームで遊んだりプログラム実験をしたり数学的な解析をしたりして,多角的に理解することを目標とする。
【コンピュータでの数の扱い】
コンピュータで数(特に実数)の計算をすると変な誤差が入ることがある。たとえば900円の商品が消費税(8%)込みで973円となってしまったりする。その原因を理解することを目標とする。
【計算量,計算可能性の理論】
問題をコンピュータで解くのにどれだけの時間がかかるか,あるいはどんなに時間をかけても解けないのか,といったことを数学的に研究する分野を紹介する。

クラス5a(CS2)(担当:河野)

【アルゴリズム】
アルゴリズムとは、一言で言えば「計算方法」の事である。ひとつの計算をするにしても、様々な計算方法が考えられ、プログラムとして実装する場合もそれが反映される。そこで、たくさんのアルゴリズムの基本となる概念の一部、再帰、ソート、といったもの等を扱う。同じ計算をするプログラムの中にも色々な意味で良いアルゴリズムや、様々な性質を持つアルゴリズムが考えられるが、再帰やソートといった概念に関連した、良いアルゴリズムとはどういったものかということの一部も扱う。
【数字の扱い】
コンピューターで数値を扱う場合、様々な制限や誤差が生じる。 そのため、様々な処置や特殊な計算方法が必要になる場合があり、それらの基本を扱う。
【計算量、計算可能性理論】
コンピューターで計算できる事や、ある計算をするときの効率には理論上限界があり、どのような限界があるのかを学ぶ。これらはコンピューターの性能等によらない理論的な枠組みで議論される。
【グラフ上の問題】
グラフとは、集合と集合間の様々な関係で構成される構造体であり、科学上の様々な場面で現れる。計算機科学では、グラフ上の数々の問題が扱われており、それらの問題の特徴、アルゴリズムの検証等を行う。

クラス5b(CS2), 6b(CS2)(担当:伊知地)

キーワード
再帰,各種アルゴリズム,計算可能性,コンピュータでの数の表現,数値計算の誤差,計算誤差を少なくするための方法,データサイエンス.
【再帰】
べき乗 n! の計算を, n! = n ×(n-1)!, 0! = 1 と定義出来ます.このように,演算 ! の機能を自分自身 ! を使って書くことを再帰といいます.再帰は,アルゴリズムやプログラムを作る際にとても強力な道具となるので,再帰を理解し,使えるようになる事を目指します.
【計算量】
アルゴリズムの良し悪し,どのくらいの問題解決能力 (計算時間,必要なメモリーの量) を持つのかを評価する方法を学びます.
【各種アルゴリズム】
最大公約数,フィボナッチ数,べき乗,ハノイの塔,ソート (データを規則的な並べ替え) のアルゴリズムを解説し,計算量を求めてアルゴリズムを評価します.
【計算可能性】
計算の難しい問題 (P = NP 問題),計算の限界について紹介します.
【コンピュータでの数の表現】
最近話題になっているデータサイエンス,ディープ・ラーニングでは,数値計算を出来るだけ正確に行うことが必要になります.しかし,コンピュータでは実数を有限桁の2進小数 (0 と1 だけで出来た小数)として表現するため,本当の値とは異なる値になる事がしばしばあります.例えば10進小数の 0.1 に対応する2進小数は無限小数になってしまい,有限桁しか扱えないコンピュータでは10進小数 0.1 を正確に表現する事が出来ず近似値で表現する事を学びます.
【数値計算の誤差】
実数の数値計算を行うと,コンピュータでの数の表現の影響で,本当の値と差の出る事がしばしばあります.これを誤差と呼びますが,計算方法によって誤差が大きくなったり小さくなったりします.誤差が発生する様々な原因を考察し,誤差を出来るだけ小さくする計算方法 (アルゴリズム)について学びます.
【データサイエンスのために】
プログラミング言語 Python の NumPy は数値計算に特化したライブラリで,データサイエンスやディープ・ラーニングのプログラムで良く使われます. NumPy の機能を紹介し,統計計算とグラフの表示について学びます.

クラス6a(CS2)(担当:大村)

【再帰】
「この文は嘘である」のように,ある記述が自身を参照して言うことを「再帰」という.コンピュータサイエンスにおいてもこの考えは重要である.私たちの日常にある再帰をとおして理解し,プログラミング技術として使いこなすことを目的とする.
【アルゴリズム概要】
アルゴリズムとは問題を解決するための計算の手順のことを言う.紀元前三世紀に考えられた最大公約数を求めるアルゴリズムを題材に,アルゴリズムとプログラムについて学習する.
【ソートアルゴリズム】
データを並び替えるアルゴリズムをソートアルゴリズムという.いくつかのソートアルゴリズムを学習し,アルゴリズムの違いについて理解することを目的とする.
【データ構造と探索】
複数のデータを効率よく抽出するためには,データを整理して格納しておく必要がある.この格納方法をデータ構造という.データ構造と探索の整理方法について学習する.