ソフトウェア科学１ （ソフトウェア科学１）

Software Science 1

9914718

14ISINS301

関川　浩

Hiroshi Sekigawa

2026年度後期

2026年度

②Second semester

月曜2限

Monday 2nd Period

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

2.00単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

コンピュータによる計算の原理を数学的なモデルを⽤いて説明する．
(1) 計算するとはどういうことなのか．
(2) どのような計算が可能なのか（計算可能性），計算にかかる⼿間（計算量）をどのように計るのか．
前半は(1)を扱う．具体的には，形式⾔語および簡単な計算機のモデルとしてオートマトンを紹介し，両者の関係について説明する．
後半は(2)を扱う．具体的には，帰納的関数，および，Turing機械（現在のコンピュータのモデル）による計算可能性の理論を説明した後，NP完全性に焦点をあてて計算量理論を紹介する．
担当教員が企業の研究員のときに，どのように計算量理論を利⽤したか，などについても⾔及する予定である．

本科目は本学科のカリキュラム・ポリシーに定める「数学を中心とする基礎教育と，応用領域を基盤とする最先端の多様な専門教育」のうちの専門教育に該当する科目の一つであり，ディプロマ・ポリシーに定める「数学を中心とする基礎知識を習得し、数学の応用領域を体系的かつ統合的に理解できる能力」の一部を身につけること，具体的には，コンピュータによる計算の原理を説明できること，NP完全性について説明できることが⽬的である．

(1) コンピュータによる計算の原理を説明できること．
(2) NP完全性について説明できること．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

とくになし．

ディベート・ディスカッション　Debate/Discussion／プレゼンテーション　Presentation／反転授業　Flipped classroom

-

毎回，授業前に講義資料を1時間程度予習し，授業後，講義内容を2時間程度復習すること．

到達度評価50%，レポート30%，演習20%の割合で評価する．レポートの提出および演習で少なくとも1問解いて他の履修学生に説明することを必須とし，⼀⽅でも⽋けた場合は科目全体の成績を「-」とする．
• 到達度評価は授業全体の範囲から基本的な問題を出題する．
• レポートは前半が終了する第6回終了後，到達目標(1)に関する基本的な問題を出題する．解説は到達度評価前にLETUSに掲載する．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://gomykits.kinokuniya.co.jp/tokyorika/

講義資料を毎回LETUSに掲載する。

すべての履修学⽣に対して半数回以上の対⾯受講を求める．

第1回：オリエンテーション，正規表現
この授業の概要および正規表現というシステムについて理解する．

第2回：有限オートマトン
簡単な計算機のモデルである有限オートマトンについて理解する．

第3回：正規表現と有限オートマトンの関係
正規表現と有限オートマトンは⾔語の表現能⼒が等しいことを理解する．
また，正規表現（有限オートマトン）の能⼒の限界についても理解する．

第4回： ⽂脈⾃由⽂法
正規表現，有限オートマトンよりも表現能⼒の⾼い⽂脈⾃由⽂法について理解する．

第5回：プッシュダウンオートマトン
有限オートマトンの拡張であるプッシュダウンオートマトンについて理解する．

第6回：文脈自由文法とプッシュダウンオートマトンの関係
⽂脈⾃由⽂法とプッシュダウンオートマトンは⾔語の表現能⼒が等しいことを理解する．
また，文脈自由文法（プッシュダウンオートマトン）の能⼒の限界についても理解する．

第7回：演習
演習を通して第1〜6回の理解を深める．

第8回：帰納的関数
原始帰納的関数，帰納的関数，部分帰納的関数について理解する．

第9回：Turing機械と計算可能な関数(1)
Turing機械および計算可能な関数を理解する．
帰納的関数は計算可能であることを理解する．

第10回：Turing機械と計算可能な関数(2)
計算可能な関数は帰納的であることを理解する．
万能Turing機械をおよび Church の提唱を理解する．

第11回：帰納的に可算な集合と決定問題
帰納的に可算な集合，述語について理解する．
決定問題について理解する．

第12回：計算量理論の基本概念
計算の⼿間を計る計算量理論の基本概念について理解する．

第13回：NP完全性
計算量クラス，とくにNPについて理解する．
SATがNP完全であることを理解する．

第14回：NP完全問題の例
NP完全問題のいくつかの例を理解する．

第15回：到達度の確認と解説
本科目の授業内容に関する到達度の確認と解説を⾏う．

情報通信関係企業の研究員の勤務実績を活かし講義する．

Mathematica

Python

N

N