シラバス情報
|
教員名 ： 立川 智章
|
科目授業名称（和文） Name of the subject/class (in Japanese)
計算理論及び演習
科目授業名称（英文） Name of the subject/class (in English)
Lectures and Exercises on Theory ofComputation
授業コード Class code
994625K
科目番号 Course number
46CSALC201
教員名
青木 健、立川 智章
Instructor
TATSUKAWA Tomoaki, AOKI Takeru
開講年度学期
2024年度後期
Year/Semester
2024 2nd Semester
曜日時限
水曜3限、水曜4限
Class hours
Thursday 3rd and 4th Period
開講学科・専攻 Department
工学部 情報工学科
Department of Information and Computer Technology, Faculty of Engineering 単位数 Course credit
3.0単位
授業の方法 Teaching method
講義/演習
Lecture/Seminar 外国語のみの科目（使用言語） Course in only foreign languages (languages)
-
授業の主な実施形態 Main class format
① [対面]対面授業/ [On-site] On-site class
概要 Description
計算機（ハードウェア、ソフトウェア）、およびそれらの応用に関する基本的な数学的性質を学習する。プログラミング言語を設計する上で重要なオートマトンと言語理論、それ以外にも計算量のクラスの概要などを系統的に習得することを目的とする。理解を深めるために講義と共に演習を行う。
目的 Objectives
本講義は演習とセットであり、単に講義として理解するにとどまらず、演習を通じて「計算機の数学」についてより深く理解する。
本学科のカリキュラム・ポリシーに定める「専門基礎科目」であり、ディプロマ・ポリシーに定める「自然・人間・社会に係る幅広い教養を修得し、情報工学分野に限らず横断的にものごとを俯瞰する能力」を養う。 到達目標 Outcomes
・正規言語や文脈自由言語に代表される形式言語とそれらに関連する有限オートマトン、プッシュダウンオートマトンなどについて説明できる
・計算機の計算モデルおよびとその計算可能性について説明できる ・アルゴリズムの実行時間やリソースの使用量などで測定される計算の難しさや、P、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/ 履修上の注意 Course notes prerequisites
特になし
アクティブ・ラーニング科目 Teaching type（Active Learning）
-
-
準備学習・復習 Preparation and review
「専門的基礎知識」を身につけるための授業であるから，その趣旨を生かすためには，常に関連する分野への興味を持ち，積極的に周辺知識を増やして行くことが望まれる．講義内容は毎週復習しておくこと．毎回教科書を使って講義・演習を進める．
成績評価方法 Performance grading policy
毎回の演習と期末試験により総合的に評価する．
学修成果の評価 Evaluation of academic achievement
・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 教科書 Textbooks/Readings
教科書の使用有無（有=Y , 無=N） Textbook used(Y for yes, N for no)
Y
書誌情報 Bibliographic information
-
MyKiTSのURL（教科書販売サイト） URL for MyKiTS(textbook sales site)
教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
https://mirai.kinokuniya.co.jp/tokyorika/ It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store). https://mirai.kinokuniya.co.jp/tokyorika/ 参考書・その他資料 Reference and other materials
Michael Sipser 著「計算理論の基礎 原著第3版 1.オートマトンと言語」(共立出版)
Michael Sipser 著「計算理論の基礎 原著第3版 2.計算可能性の理論」(共立出版) Michael Sipser 著「計算理論の基礎 原著第3版 3.複雑さの理論」(共立出版) 授業計画 Class plan
1. ガイダンス＋イントロダクション
講義内容の概略説明と学習の進め方に関する注意を受け、何をどのような目的で学ぶかを理解する． また、受講な数学的基礎を復習し、以後の講義に備える． ■形式言語 2. 有限オートマトン（１） 3. 有限オートマトン（２） 4. 正規表現（１） 5. 正規表現（２） 6. 文脈自由言語（１） 7. 文脈自由言語（２） 8. プッシュダウンオートマトン 正規言語、文脈自由言語とその計算モデルについて理解する． 9. 中間試験 ここまでの授業内容に関する到達度の確認を行う． ■計算可能性理論 10. 計算可能性理論（１） 11. 計算可能性理論（２） 12. 計算可能性理論（３） チューリング機械について理解する． ■計算複雑性理論 13. 計算複雑性理論（１） 14. 計算複雑性理論（２） Big-Oなどの時間計算量、N、NPなどの複雑性クラスについて理解する． 15. 達成度評価試験 授業内容に関する到達度の確認を行う． 授業担当者の実務経験 Work experience of the instructor of the class
-
教育用ソフトウェア Educational software
-
-
備考 Remarks
特になし
授業でのBYOD PCの利用有無 Whether or not students may use BYOD PCs in class
-
授業での仮想PCの利用有無 Whether or not students may use a virtual PC in class
-
|
