Skip to content

Instantly share code, notes, and snippets.

@kaisugi
Last active September 8, 2018 11:02
Show Gist options
  • Save kaisugi/adc6f2c78e97978815cbe4ca73c7edc2 to your computer and use it in GitHub Desktop.
Save kaisugi/adc6f2c78e97978815cbe4ca73c7edc2 to your computer and use it in GitHub Desktop.

月4 ハードウェア構成法 駒場5号館 511教室

授業の目標、概要

CPUのハードウェア設計ができるようになる。
CPLD,FPGAの設計ができるようになる。
新しい回路を設計する勇気が出る。

授業計画

組合せ回路
順序回路
演算回路
浮動小数点
テスト設計
アナログ回路、電源、EMI、ESD

成績評価方法

レポート、テスト

教科書

ASICの論理回路設計

参考書

月刊 トランジスタ技術誌
アナログウェア
Computer Architecture, Sixth Edition

その他

第1回講義は10月1日月曜日の予定。

火3 アルゴリズムとデータ構造 21KOMCEE East K011

授業の目標、概要

基本的なアルゴリズムとデータ構造について説明する
効率のよいアルゴリズムの設計法と解析について
具体的なアルゴリズムを通じて学ぶ

授業計画

アルゴリズムと計算量、基本的なデータ構造、集合の表現、ソート、有向グラフ、無向グラフ、文字列の検索、設計法

成績評価方法

出席および試験

教科書

データ構造とアルゴリズム
数理工学社

参考書

月刊 トランジスタ技術誌
アナログウェア
Computer Architecture, Sixth Edition

その他

第1回講義は9月25日火曜日の予定。

http://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/index.html

火4 計算機システム 駒場12号館 1213教室

授業の目標、概要

コンピュータの基礎的なハードウエア、ソフトウエアの構造と動作について講義する

授業計画

(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

火5, 金5 情報科学基礎実験 情報教育棟 E41教室

授業の目標、概要

情報科学の基礎となるべきプログラミング技術を習得し、計算機の仕組みやアルゴリズムの理解を深めることを目標とする。

(1) C言語入門: C言語の基本的な制御構造とデータ構造(文字列・配列・構造体・ポインタ)を習得する。
(2) Scheme入門: 関数型のリスト処理言語であるSchemeについて学ぶ。Schemeを通じて関数型プログラミングの基礎を学習する。
(3) アルゴリズムとデータ構造演習: 講義「アルゴリズムとデータ構造」で学ぶソーティング、ハッシング、経路探索などのアルゴリズムをC言語及びSchemeで実装する。
(4) 計算機システム演習: 講義「計算機システム」に関連して、アセンブリについての演習を行う。

授業計画

下は標準的な授業予定であるが、実習形式の授業であるため、受講者によって進行状況が異なる。

第1週から第4週: C言語入門
第5週から第7週: Scheme入門
第8週から第10週: アルゴリズムとデータ構造演習
第11週以降: 計算機システム演習

成績評価方法

出席およびレポートによる。

教科書

柴田望洋著「明解C言語 入門編」(C言語既習者を除く)

その他は授業中に指定する。

参考書

授業中に推薦する。

その他

関連ホームページは、授業中に発表する。

第1回講義は9月25日火曜日の予定。

金3 情報数学 駒場11号館 1108教室

授業の目標、概要

情報科学の基礎となる数学のうち,集合,関係,束,情報理論,代数系(群,環,体),およびその情報的応⽤(符号,暗号,乱数等)を扱う.

授業計画

  1. 集合,束(9/28)
  2. 関係(10/5)
  3. 群(10/12)
  4. 環(10/19)
  5. ユークリッド環,整数(10/26)
  6. 多項式(11/2)
  7. 体(11/9)
  8. 情報量(11/16)
  9. 情報源符号化(11/30)
  10. 通信路符号化(12/7)
  11. 線形符号(12/14)
  12. 巡回符号(12/21)
    暗号,乱数(適宜)
    試験(1/11)
    ⽇程により内容を調整する場合がある。

成績評価方法

試験およびレポートによる

教科書

平林隆一「工学基礎 代数系とその応用」数理工学社
横尾英俊「情報理論の基礎」共立出版
國廣昇 「工学教程 代数学」丸善出版

参考書

特になし

金4 形式言語理論 駒場5号館 511教室

授業の目標、概要

正則言語、文脈自由言語、及びオートマトンについての基本的な概念と定理を理解する。
正則言語については、有限オートマトンと正則表現の関係、正則言語の性質、状態数最小有限オートマトン、順序機械、関連するアルゴリズム、および形式検証への応用可能性について学ぶ。
文脈自由文法とそれに関連する概念について学ぶ。そして、文脈自由言語の性質、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.文脈自由文法
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 有限オートマトンと正則文法

4.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.
●有川節夫,宮野悟,「オートマトンと計算可能性」(第1章,2章,3章),培風館,1986.
●宮野悟,「並列アルゴリズム」(第1章),近代科学社,1994.

その他

講義開始は 2018/9/28 (金)を予定.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment