シラバス照会

<< 最終更新日:2024年03月25日 >>
基本情報
科目種別 専門教育科目 授業番号 L0258
学期 後期 曜日
科目 アルゴリズム解析(EECS) 時限 3限
担当教員 酒井 和哉 単位数 2
科目ナンバリング
※2018年度以降入学生対象

担当教員一覧

教員 所属
酒井 和哉 電子情報システム工学科

詳細情報
授業方針・テーマ 計算量の考え方について理解することを目的とする。コンピュータで処理される様々な問題をその処理に要する時間やメモリ量に基づいて分類する方法を説明する。
習得できる知識・能力や授業の
目的・到達目標
・アルゴリズムを計算量に基づいてクラス分け又はそれを証明することができる。(専門分野の知識・理解、論理的思考能力)
・アルゴリズムの設計並びに漸近的解析ができる。(専門分野の知識・理解、アルゴリズム設計能力・解析能力、論理的思考能力)
・アルゴリズムの数学的性質について証明することができる。(専門分野の知識・理解、論理的思考能力)
授業計画・内容
授業方法
第1回  計算理論
第2回  複雑さの測定
第3回  クラスP
第4回  クラスNP
第5回  NP 完全性
第6回  他の NP 完全問題
第7回  領域の複雑さ
第8回  クラス PSPACE
第9回  PSPACE完全性
第10回 クラス L とクラス NL
第11回 NL完全性
第12回 階層定理
第13回 相対化
第14回 回路の複雑さ
第15回 ランダム化アルゴリズムとオラクル、まとめ
授業外学習 複数回の演習問題を課す。宿題を出した場合、次回の授業までに解答を用意しておくこと。
テキスト・参考書等 教科書
・Michael Sipster,計算理論の基礎 [原著第3版] 3.複雑さの理論. 共立出版(2023)

参考書
・Cormen他,「アルゴリズムイントロダクション第3版 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム」,近代科学社(2012)
成績評価方法 期末試験60%、小テスト複数回40%、平常点(授業態度や積極性の状況等)により加点・減点する。
試験については記述式の問題を課し、専門知識を理解した上で論理的な説明ができるか確認する。(アルゴリズムの基本的な知識・理解、アルゴリズム設計能力及び解析能力、論理的思考)
小テストについては選択式の問題を課し、専門知識を理解した上で適切にアルゴリズムの解析ができるか確認する。(アルゴリズムの基本的な知識・理解、アルゴリズム解析能力)
質問受付方法
(オフィスアワー等)
オフィスアワーについては、原則として毎週火曜日13時30分〜14時30分、毎週水曜日12時10分〜12時40分とする。これ以外の時間帯に担当教員に会いたい場合は、事前にメールでアポイントメントを取ること。また質問は Kibaco 又はメールにて受け付ける。
特記事項
(他の授業科目との関連性)
関連科目:
データ構造とアルゴリズムI,データ構造とアルゴリズムII,データ構造とアルゴリズム演習,離散数学,計算理論,暗号理論
備考