CPUのハードウェア設計ができるようになる。
CPLD,FPGAの設計ができるようになる。
新しい回路を設計する勇気が出る。
組合せ回路
順序回路
演算回路
浮動小数点
テスト設計
アナログ回路、電源、EMI、ESD
レポート、テスト
ASICの論理回路設計
月刊 トランジスタ技術誌
アナログウェア
Computer Architecture, Sixth Edition
第１回講義は１０月１日月曜日の予定。
基本的なアルゴリズムとデータ構造について説明する
効率のよいアルゴリズムの設計法と解析について
具体的なアルゴリズムを通じて学ぶ
アルゴリズムと計算量、基本的なデータ構造、集合の表現、ソート、有向グラフ、無向グラフ、文字列の検索、設計法
出席および試験
データ構造とアルゴリズム
数理工学社
月刊 トランジスタ技術誌
アナログウェア
Computer Architecture, Sixth Edition
第１回講義は９月２５日火曜日の予定。
http://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/index.html
コンピュータの基礎的なハードウエア、ソフトウエアの構造と動作について講義する
(1) はじめに
(2) データ形式、計算機の内部構成
(3) 計算機の命令、計算機の動作、アセンブリ言語、基本の命令
(4) アドレッシングモード、その他の命令
(5) 机上の計算機、呼び出し規約
(6) CPU命令実行の様子, I/O、割り込み
(7) CPUの内部動作、記憶階層、キャッシュ
(8) 中間試験
(9) オペレーティングシステム、仮想記憶
(10) システムコール、プロセスとスレッド
(11) プロセス管理、実行ファイル形式、プロセス間通信
(12) ファイルシステム, I/O
(13) ネットワーキング、 セキュリティ
出席と試験による
指定しない
パターソン＆ヘネシー コンピュータの構成と設計 5版（上下） 日経BP
馬場敬信 コンピュータアーキテクチャ 4版 オーム社
Silberschatz, Galvin, and Gange オペレーティングシステムの概念 7版 共立出版
http://www.cp.is.s.u-tokyo.ac.jp
情報科学の基礎となるべきプログラミング技術を習得し、計算機の仕組みやアルゴリズムの理解を深めることを目標とする。
(1) C言語入門: C言語の基本的な制御構造とデータ構造(文字列・配列・構造体・ポインタ)を習得する。
(2) Scheme入門: 関数型のリスト処理言語であるSchemeについて学ぶ。Schemeを通じて関数型プログラミングの基礎を学習する。
(3) アルゴリズムとデータ構造演習: 講義「アルゴリズムとデータ構造」で学ぶソーティング、ハッシング、経路探索などのアルゴリズムをC言語及びSchemeで実装する。
(4) 計算機システム演習: 講義「計算機システム」に関連して、アセンブリについての演習を行う。
下は標準的な授業予定であるが、実習形式の授業であるため、受講者によって進行状況が異なる。
第1週から第4週: C言語入門
第5週から第7週: Scheme入門
第8週から第10週: アルゴリズムとデータ構造演習
第11週以降: 計算機システム演習
出席およびレポートによる。
柴田望洋著「明解C言語 入門編」（C言語既習者を除く）
その他は授業中に指定する。
授業中に推薦する。
関連ホームページは、授業中に発表する。
第１回講義は９月２５日火曜日の予定。
情報科学の基礎となる数学のうち，集合，関係，束，情報理論，代数系（群，環，体），およびその情報的応⽤（符号，暗号，乱数等）を扱う．
- 集合，束(9/28)
- 関係(10/5)
- 群(10/12)
- 環(10/19)
- ユークリッド環，整数(10/26)
- 多項式(11/2)
- 体(11/9)
- 情報量(11/16)
- 情報源符号化(11/30)
- 通信路符号化(12/7)
- 線形符号(12/14)
- 巡回符号(12/21)
暗号，乱数(適宜)
試験(1/11)
⽇程により内容を調整する場合がある。
試験およびレポートによる
平林隆一「工学基礎 代数系とその応用」数理工学社
横尾英俊「情報理論の基礎」共立出版
國廣昇 「工学教程 代数学」丸善出版
特になし
正則言語、文脈自由言語、及びオートマトンについての基本的な概念と定理を理解する。
正則言語については、有限オートマトンと正則表現の関係、正則言語の性質、状態数最小有限オートマトン、順序機械、関連するアルゴリズム、および形式検証への応用可能性について学ぶ。
文脈自由文法とそれに関連する概念について学ぶ。そして、文脈自由言語の性質、Pumping Lemma (uvwxy定理）、Ogdenの定理、プッシュダウン・オートマトン、及び関連するアルゴリズムについて理解する。
1 基本的定義と記法
1.1 関係と部分関数
1.2 記号列，アルファベット，言語
2 有限オートマトンと正則言語
2.1 有限オートマトン序章：「ある離れ小島で」
2.2 有限オートマトンの定義
2.3 非決定性有限オートマトンと決定性有限オートマトンの等価性
2.4 ε動作付非決定性有限オートマトン
2.5 正則言語のPumping Lemma
2.6 正則表現
2.7 有限オートマトンと正則表現
2.8 正則言語の性質
2.9 ブール行列による有限オートマトンの表現
2.10 最小オートマトン
2.10.1 Myhill-Nerode の定理
2.10.2 状態数の最小化
2.11 順序機械
2.12 有限オートマトンについてのアルゴリズム
３．文脈自由文法
3.1 定義と例
3.1.1 導出木
3.2 文法の簡素化
3.2.1 無駄な変数の除去
3.2.2 A → εの形の生成規則
3.2.3 A → B の形の生成規則
3.3 Chomsky 標準形
3.4 文脈自由言語の性質
3.4.1 Pumping Lemma
3.4.2 Ogdenの定理
3.5 文脈自由文法の所属性判定問題
3.6 有限オートマトンと正則文法
４．Turing 機械
4.1 定義
4.2 Turing 機械による関数の計算
4.3 Turing 機械の変種
4.3.1 非決定性Turing 機械
4.3.2 マルチテープTuring 機械
4.3.3 両方向に無限の長さをもつテープ
4.3.4 オフラインTuring 機械
4.3.5 多次元テープTuring 機械
4.3.6 その他の計算のモデル
4.4 Church のテーゼ
4.5 帰納的可算集合と帰納的集合
4.6 決定不能な問題
期末試験による．レポート（ほぼ毎回，出席確認を兼ねる）も加味する．
講義のなかで配布する．
●John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, (2nd Edition),
Addison-Wesley Pub Co, 2000; ISBN: 0201441241.
●M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Publishing Company, 1978.
●有川節夫，宮野悟，「オートマトンと計算可能性」（第１章，２章，３章），培風館，1986.
●宮野悟，「並列アルゴリズム」（第１章），近代科学社，1994.
講義開始は 2018/9/28 （金）を予定．