ソフトウェア基礎理論

更新: 2001.06.24

まえがき

離散数学やソフトウェア基礎論理学に関するページです。東大工学部の講義「ソフトウェア基礎理論」の内容とリンクしています。たくさんあるプログラミング言語の、根底の部分についてです。ソフトウェア設計やさんはこういう論理学についての知識を身につけておくと、きっと役に立つと思います。

わかりにくい / 間違っている等のご指摘がありましたら、hossy.ee99@popup.orgまでメールか、掲示板でご報告をお願いします m(__)m

内容

0. はじめに 1. 集合論 1.1 記号の説明
1.2 集合の濃度の話 1.3 素朴集合論と破綻 1.4 関係(relation)
1.5 同値関係 1.6 順序関係 1.7 ハッセ図
1.8 束 1.9 束の性質 1.10 距離空間
1.11 群と環 2. 命題論理 2.1 ブール代数
2.2 ブール代数の他の表現 2.3 ブール束 2.4 演繹体系
2.5 シーケントと計算規則 2.6 シーケントの証明法 3. 述語論理
3.1 命題論理との違い 3.2 論理式の意味づけ 3.3 シーケントへの変換
3.4 シーケント計算規則2 3.5 シーケント証明法2 4. 有限オートマトン
4.1 オートマトンとは 4.2 言語との関係 4.3 FA と受理
4.4 状態遷移図 4.5 正規表現 4.6 出力を持つFA
4.7 NFA 4.8 FAの限界 5. 計算性能の可能性
5.1 文脈自由文法 CFG 5.2 PDA 5.3 TM
5.4 TMの単純化 5.5 帰納的関数論 5.6 TM の限界

演習問題

東大工学部電気系3年生冬学期の講義「ソフトウェア基礎理論」の試験問題です。全て解答付きです。

問題キーワード更新日
1996年度 試験問題 二項関係、シーケンス形式、有限オートマトン 2001.01.26
1997年度 試験問題 一階述語論理式、擬順序、正規表現 2001.01.29
1998年度 試験問題 等価な論理式、ハッセ線図、下界、極大元 2001.02.03
1999年度 試験問題 順序関係、束、距離、正規表現、Church の仮説 2001.02.03
2000年度 試験問題 ハッセ図、距離、一階述語論理 2001.06.24
練習問題 PDA、Greibachの標準形、CFG 2001.01.27

圧縮ファイル

圧縮ファイルのダウンロード (2001.06.24 版)

ここに載せている全ファイルを LHA (lzh) 圧縮したものです。他によくわからないファイルも一緒に入っていますが、実害はありません。解凍後、‘index.html’を開いてください。

言い訳

HTML で一般的に使用できるフォントの制約上、 (記号) は表示できず、代わりに不等号‘<>’等で代用しています。そのほかにも、記号が足りず(∈ の否定とか)、怪しい書き方をしている物が結構あります。これはどうしようもないので許してください。

謝辞

ソフトウェア基礎理論の講義をされた 近山先生、1999年度ソフトウェア基礎理論シケタイの吉原先輩には、大変お世話になりました。この場を借りて大感謝いたします m(__)m

更新履歴

リンク

どちらも私が管理しています。

タイトル簡易紹介
ee - 東大電気系学科 東大電電3年のクラスサイトです
このページはこちらの企画で立ち上がっています
hossy online - 図書館 お気軽プログラミング講座中心の個人サイトです

細山 直樹 (Hosoyama Naoki)
http://hey.to/hossy/
hossy.ee99@popup.org