講師ブログ（～2021.3.25） - 電気通信大学プログラミング教室（対面）／ｕｅｃプログラミング教室（オンライン）

計算複雑性理論の神　R・スターンズ氏

計算複雑性理論は、コンピュータ科学の計算理論の一分野。スターンズさんはその分野の基盤を作る論文「On the Computational Complexity of Algorithms」をユリス・ハルトマニスさんと共同 …

▼ミルナーさんのコンピュータとの最初の出会いは、ケンブリッジ大学でウィクルス先生が中心になって制作したEDSACだった。EDSACが初めて動いたのは1949年。学生のミルナーさんがEDSACと対面したのが56年。EDSA …

▼計算理論の発展に貢献した人物。チューリング賞の受賞理由のキーワードは、ネットワーク・フロー、組み合わせ最適化問題、効果的なアルゴリズム、NP完全など。コンピュータが動く大元は数学だということがわかる。 ▼現在、カリフォ …

▼フロイドさんがチューリング賞を受賞した理由は次である。「ソフトウェア開発において効果的で信頼性の高い方法論を示し、それが広い影響を及ぼしたこと。コンピュータ科学に次の重要な分野を追加したこと：解析理論、プログラミング言 …

▼スコットさんの博士論文の指導教員はプリンストン大学のA・チャーチ先生。チューリングさんの指導教員も同じチャーチ先生。違うのは時期。チューリングさんが博士号を取ったのは1938年。スコットさんは1958年。ということは、 …

1960年代、ラビンさんが30代のころコンピュータを使う計算分野は数学界に認知されておらず業績も評価されない時代だった。しかしラビンさんたちコンピュータを念頭に置いた計算理論家たちは研究を重ね、現代の情報化社会で必要不可 …