コンピュータは，その万能性により，数学的に明瞭な問題であれば何でも解けると思われがちであるがそうではない．例えば，「与えられたプログラムが暴走せずにきちんと停止するか？」ということを判定することは不可能なのである．本講義では，コンピュータの計算能力の限界を数学的に明らかにする「計算可能性の理論」と「計算複雑性の理論」への導入を行う．このために，実際のコンピュータの数理モデルであるチューリング機械を定義し，これをもとに「解けること」と「解けないこと」を明らかにしていく．最後に，数学における著名な未解決問題であるP対NP問題を定式化し，NP完全性の概念を理解する．本講義は，情報数学の中核分野である計算理論に興味がある諸君に勧める．なお，応用数学3の続編であるため，応用数学３を履修していることが望ましい．また，情報数学3/4との関連も深いため，合わせて履修すると理解が深まる．

良いアルゴリズムとは何か，どのように作るのか，ということを明確に説明する数学理論を学びたい人を対象とした講義である．AIにプログラムを書かせる時代であっても，AIへの的確な指示やプログラムの良し悪しの検証にアルゴリズムの知識は欠かせない．本講義では，情報数学３で学んだことを基礎として，動的計画法・貪欲アルゴリズム・グラフアルゴリズムなどの発展的かつ実践的なアルゴリズム設計法を学ぶ．また，学習したアルゴリズム設計法の具体的な適用例を通じて，アルゴリズム設計に習熟する。本講義は，情報数学3の続編であるため，情報数学3と合わせて履修することを強く勧める．本講義ではプログラミング演習は実施しないが，内容を理解するためにプログラミング経験(特に，配列・ポインタの知識)があることが望ましい．

「情報処理・通信分野の数学的基礎を研究する広大な分野である理論計算機科学の中でも，世界的にホットな話題である「量子コンピュータによる計算」の数学理論(量子計算理論)を扱う．本講義では，「情報数学特論IV-1」で学んだ事項をもとに，より高度な量子アルゴリズムの技法を説明し，量子計算量理論の枠組みにより量子計算能力を数学的に議論する．

本講義は，情報工学・情報科学の「基礎中の基礎」である，形式言語理論及びオートマトン理論を扱う．これらの理論は，計算を数学的に捉えるための諸概念を与え，計算可能性の理論や計算複雑さの理論の玄関口になるばかりでなく，幅広い応用分野の基礎となる．例えば，プログラミング言語の処理系(コンパイラ)，通信プロトコル，制御システムの設計など，情報処理の多くの分野で形式言語やオートマトンの知識は欠かせない．情報数学の中核分野である「計算理論」を志す諸君には，本講義および，その続編である応用数学４の受講を勧める．

同じコンピュータを使っても，良いプログラム（アルゴリズム）では１秒で終わる計算が，悪いプログラムを使うと100年かかっても計算が終わらない場合がある．良いアルゴリズムとは何か，どのように作るのか，ということを明確に説明する数学理論を学びたい人を対象とした講義である．AIにプログラムを書かせる時代であっても，AIへの的確な指示やプログラムの良し悪しの検証にアルゴリズム理論の知識は欠かせない．本講義では，アルゴリズムの設計指針やアルゴリズムの良さを評価するための基本知識を学ぶ．また，データ構造がアルゴリズムの設計へどのように寄与し得るかを理解してもらう．本講義ではプログラミング演習は実施しないが，内容を理解するためにプログラミング経験(特に，配列・ポインタの知識)があることが望ましい．また，情報数学4を受講予定の場合は，本授業の受講をすすめる．

情報処理・通信分野の数学的基礎を研究する広大な分野である理論計算機科学の中でも，世界的にホットな話題である「量子コンピュータによる計算」の数学理論(量子計算理論)を扱う．線形代数と情報数学を基盤として，量子コンピュータのためのアルゴリズム，およびその計算能力の限界について解説する．量子コンピュータによる計算の仕組みを，数学的観点から厳密に学習してみたい人に勧める．

記憶容量が厳しく制限された「弱い」計算モデル（オートマトン）を扱う「応用数学３」に引き続き，「応用数学４」では，実際のコンピュータの基礎概念としての「強い」計算モデルであるチューリング機械を扱い，「計算可能性」という概念を理解する．その過程で，プログラムが暴走せずにきちんと停止するか，という基本的な問題が，実は，コンピュータを使っても判定不可能であることが明らかになる．さらに，応用上重要である「効率的に計算可能」という概念を理解するため，多項式時間に限定されたチューリング機械について議論し，情報数学における著名な未解決問題であるP対NP問題を定式化する．

本講義では，情報数学３で学んだことを基礎として，動的計画法や貪欲アルゴリズムなどの発展的なアルゴリズム設計法を学ぶ．さらに，グラフ探索問題，最短路問題，フロー問題などの重要問題に対する具体的な応用を行う．

「情報数学特論IV-1」で学んだ事項をもとに，より高度な量子アルゴリズムの技法を説明し，量子計算量理論の枠組みにより量子計算能力を数学的に議論する．

計算機科学の基礎をなす，形式言語及びオートマトン理論の講義を行う．形式言語の理論は，応用面での重要性も大きく，例えば，あるプログラミング言語で記述したプログラムが文法的に正しいか否かを判定するパーザー（構文解析）の基礎となっている．オートマトンは，コンピュータの基礎概念であるチューリング機械のミニチュア版として位置付けられ，オートマトンの講義を通じて処理機械の基礎を習得する．最後に，全く異なる概念である形式言語とオートマトンが，実は等価であることを示す．この驚くべき等価性により，言語の表現能力と，その処理系に必要な計算能力の関係が明らかになる．

同じコンピュータを使っても，良いプログラム（アルゴリズム）では１秒で終わる計算が，悪いプログラムを使うと100年かかっても計算が終わらない場合がある．良いアルゴリズムとは何か，どのように作るのか，ということを学びたい人を対象とした講義である．本講義では，アルゴリズムの設計指針やアルゴリズムの良さを評価するための基本知識を学ぶ。

量子コンピュータは，現在のコンピュータの技術革新の延長線上では達成できないレベルの「超」高速な計算性能が期待され，世界中で熾烈な開発競争が行われている．しかし，現在のコンピュータと同様に，高速な計算ができるかどうかは，量子コンピュータの上で動かすソフトウェア（＝量子アルゴリズム）の良し悪しに大きく依存する．本講義では，量子コンピュータ上での計算（量子計算）の数学的基礎を説明し，それをもとにして量子アルゴリズムの基本的技法を紹介する．