アルゴリズム
院試の解答の目次へ 東京大学の大学院・情報理工学系研究科で,創造情報学専攻の院試対策まとめ。修士の試験問題と解答へのリンク。とくに専門科目。 創造情報学の過去問と解答(年度別) 2011年の過去問と解答: 試験問題 http://i-web.i.u-tokyo.ac.jp/edu…
講義ノートの目次へ 情報科学で,形式言語とオートマトンの講義ノートPDF。 コンパイラやチューリングマシンによる,機械的な言語処理を実現するための理論だ。「正規言語」や「正規文法」といったモデル化を行なう。 ここで形式言語の処理を学ぶ前に,チュ…
講義ノートの目次へ アルゴリズムの計算量理論の講義ノートPDF。チューリングマシンやオートマトン,ラムダ計算などを使って,アルゴリズムの複雑さを判定する。 例えば,処理の複雑さを「P」と「NP」のクラスに分類したり(=計算複雑性),ある処理が決し…
講義ノートの目次へ CGやゲーム開発にも役立つ計算・幾何学(けいさん・きかがく)の教科書。点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。 プログラミングにすごく役立つ。複雑な図形どうしの関係を,三角形や木構造を使ってシン…
講義ノートの目次へ グラフ理論・組み合わせ最適化の講義ノート。ネットワーク(経路系)のアルゴリズムも含む。 大学の情報科学では,「離散数学」という分野だ。以下に,「グラフ理論」と「組み合わせ最適化」の入門段階の要点を並べてみる。 最大フロー問…
講義ノートの目次へ 情報科学の一分野である「情報理論」(Information Theory)の講義ノート。勉強しやすいものを集めた。 情報理論のテキストには,暗号に重点をおいた物と,符号理論(Coding Theory)から始める物の2タイプが存在する。さらに言えば,符…
講義ノートの目次へ ゲーム理論の講義ノート。有名な「囚人のジレンマ」から始まり,かけひきの絡む複雑な状況下で,ベストな意思決定をするための理論。 応用分野がたくさんあり,「戦略」や「判断」が関係するものは全てゲーム理論を活用。例えば,ライバ…
講義ノートの目次へ 情報科学という道具で言語学を切り開くと,「自然言語の処理」に行きつく。人間が自然に話している言語を,数理的にモデル化し,コンピュータで解析する,という内容だ。 大学で教えるこの「自然言語処理」の授業の,オンライン講義資料…
講義ノートの目次へ ラムダ計算は,コンピュータ・サイエンスの重要な1分野。 「λ」を使って各種の関数を記述し,λどうしの計算方法を習得すれば・・・ HaskellやF#などの関数型言語を習得するために役立つ。 プログラミングにおいて,関数についての理解を…