計算機数学(情報理工学科)・電子計算機概論I(数学科)・講義内容と予定

秋学期・金曜3時限・3-321教室3-221教室に変更

本講義は、理工学部情報理工学科「計算機数学」・ 理工学部数学科「電子計算機概論I」の合併講義であるが、 数学科の「計算機数学I・II」とは別の講義である。

上智大学の学部シラバス内の本授業のページ [計算機数学 |電子計算機概論I ]

期末試験のお知らせ

レポート提出について

お知らせ

授業時のプロジェクタ資料を掲載する予定です。 各授業日の項から見て下さい。 但し、各授業中の前回の復習部分を含んでいるので、内容に重複があります。 印刷時には必要なページだけ印刷するなどして下さい。

講義概要

「計算」とは何か、「計算できるか／できないか」というような問いに対して、 数学では、「計算機が行なうこと」を「計算」と考え、 計算機が行なえることを「計算モデル」として定式化することによって 「計算」を定義し、明確に答えることを可能にしてきた。 本講義では、必要なら計算の実現に関する話題から始めて、 代表的な計算モデルを取り上げながら、 計算の理論・アルゴリズムの概念・計算量の理論の初歩を紹介し、 計算の可能性・効率について論ずると共に、 具体的な例として幾つかの基礎的な数理アルゴリズムについて触れる。

講義計画

計算機におけるデータの取扱いや計算の原理について軽く説明した後、 計算の理論の入門として、計算モデルによる「計算」の定式化・ 計算可能性の理論・計算量の理論の初歩を紹介し、 幾つかの基礎的な数理アルゴリズムについても触れる。

主な参考書

講義内容

9/30

配ったプリント [page 0(pdf,15KB) |アンケート(数学科向け)(pdf,6KB) |アンケート(情報理工学科向け)(pdf,6KB) ] ・プロジェクタ資料 [9/30授業時(pdf,81KB) |9/30印刷用(pdf,60KB) ]

本授業の概要・予定。半期の講義内容全般の概観・予告。

10/07

配ったプリント [演習(1)(pdf,7KB) ] ・プロジェクタ資料 [10/07授業時(pdf,82KB) |10/07印刷用(pdf,71KB) ]

計算機における数の表し方。二進表示と十六進表示。 負の数(符号付き整数)の"2の補数表示"。 基本的な演算(加減乗・bit shift)。桁溢れについて。

論理回路。

10/14

配ったプリント [演習(2)(pdf,16KB) ]・ プロジェクタ資料 [10/14授業時(pdf,80KB) |10/14印刷用(pdf,66KB) ]

論理回路とは。基本的な論理ゲート。Boole関数。 論理和標準形・論理積標準形。 組合せ回路による演算の実装。半加算器・全加算器。

  1. 全加算器(full adder)を、NOT, OR, AND を用いて構成せよ。
  2. 全加算器(full adder)を部品として用いて、 二進4桁の符号付き整数値2つの加算を行なう組合せ回路を構成せよ。 但し、桁溢れの発生を判定し、桁溢れが生じた場合はoverflow flagを立てよ。

10/21

プロジェクタ資料 [10/21授業時(pdf,120KB) |10/21印刷用(pdf,117KB) ]

順序回路による状態の保持と入出力。フリップフロップ。カウンタ。

10/28(見做し月曜日)

見做し月曜日のため、本授業なし。

11/04

配ったプリント [演習(3)(pdf,13KB) ] ・プロジェクタ資料 [11/04授業時(pdf,55KB) |11/04印刷用(pdf,42KB) ]

計算の理論入門まで。コンピュータが行なっていることの定式化。 有限オートマトン。

11/11

プロジェクタ資料 [11/11授業時(pdf,61KB) |11/11印刷用(pdf,56KB) ]

計算の理論入門まで。有限オートマトン。 語・言語の演算。正規言語・正規表現。非決定性有限オートマトン。

11/18

プロジェクタ資料 [11/18授業時(pdf,66KB) |11/18印刷用(pdf,65KB) ]

計算の理論入門まで。有限オートマトンと正規言語・正規表現。 非決定性有限オートマトン。 有限オートマトンによる計算可能性。

11/25

配ったプリント [page 1(論理回路・演習問題)(pdf,23KB) |page 2(論理回路の例)(pdf,39KB) |page 3(オートマトン)(pdf,24KB) ] ・プロジェクタ資料 [11/25授業時(pdf,43KB) |11/25印刷用(pdf,36KB) ]

計算の理論入門まで。有限オートマトンによる計算可能性。 プッシュダウンオートマトン。生成文法。

12/02

配ったプリント [演習(4)(pdf,7KB) ] ・プロジェクタ資料 [12/02授業時(pdf,79KB) |12/02印刷用(pdf,66KB) ]

計算の理論入門まで。 生成文法・文脈自由言語とプッシュダウンオートマトン。 スタックマシンの例: 逆ポーランド記法。

12/09

プロジェクタ資料 [12/09授業時(pdf,95KB) |12/09印刷用(pdf,89KB) ]

計算の理論入門まで。 スタックマシンの例: PostScript。 生成文法・文脈自由言語とプッシュダウンオートマトン。 チューリング機械。計算可能性。Church-Turingの提唱。

12/16

配ったプリント [page 4,5(計算モデル・言語)(pdf,34KB) ] ・プロジェクタ資料 [12/16授業時(pdf,55KB) |12/16印刷用(pdf,42KB) ]

計算の理論入門まで。計算可能性。 万能チューリング機械。対角線論法。

01/06

プロジェクタ資料 [01/06授業時(pdf,46KB) |01/06印刷用(pdf,33KB) ]

計算量の理論入門まで。計算量とは。LandauのO-記法。 多項式時間・指数時間。例: 互除法。

01/13

配ったプリント [page 6(pdf,24KB) ] ・プロジェクタ資料 [01/13授業時(pdf,61KB) |01/13印刷用(pdf,48KB) ]

計算量の理論入門まで。色々な数理アルゴリズムの計算量。 例: 素数判定・素因数分解・並べ替えなど。

01/20

プロジェクタ資料 [01/20授業時(pdf,48KB) |01/20印刷用(pdf,39KB) ]

計算量の理論入門まで。非決定性計算量。 "P=NP" 問題。NP完全性。

01/27

期末試験を行なった。 [期末試験問題(pdf,34KB) ]