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

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

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

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

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

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