シラバス
| 授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科など | 担当教員 | 教員カナ氏名 | 配当年次 | 単位数 |
|---|---|---|---|---|---|---|---|---|
| 情報数学特別講義第二 | 2024 | 後期 | 火1 | 理工学研究科博士課程前期課程 | 原 正雄 | ハラ マサオ | 1年次配当 | 2 |
科目ナンバー
SG-AN5-1C60
履修条件・関連科目等
授業で使用する言語
日本語
授業で使用する言語（その他の言語）
授業の概要
計算の複雑さについて講義する。計算の複雑さの理論では、計算問題の難しさを形式的に定義し、各々の計算問題が持つ難しさや、あるいは、本質的に難しい計算問題が持つ性質の解明に取り組んでいる。本講義ではこれらの概念を簡単に解説した後、確率的なアルゴリズムの効果などを体感するため、計算代数問題やグラフに関する問題に関するアルゴリズムを作成し、実験することを通じてこれらの理論の理解を深めることを目標とする。なお、プログラミングを学ぶことが目標ではないので計算代数等のアルゴリズムの実現を容易にするためいわゆるプログラミング言語以外にもMathematica等の計算代数システムを利用する。
科目目的
アルゴリズムを実際の問題に応用するためにはアルゴリズムの仕組みを理解するだけでは不十分である。アルゴリズムを理解し、それを実装する一連の過程をプログラミングコンテストの問題などを題材として学修する. さらに、実装したアルゴリズムの時間計算量や記憶領域計算量などを評価することにより計算量の概念を体験的に学ぶことも目的とする。
到達目標
アルゴリズムを作成する際の基本的な考え方とアルゴリズムの解析に関する基礎知識を習得すること
授業計画と内容
準備
第1回 ガイダンス
第2回 アルゴリズムの解析について
分割統治
第3回 分割統治の基本
第4回 マージソート・クイックソート
第5回 多項式の積： Karatsuba法
数理的アルゴリズム
第6回 離散フーリエ変換概説
第7回 Newton 反復と多項式の除算
動的計画法
第8回 動的計画法の基本
第9回 コンテストの問題から
第10回 ナップザック問題
第11回 巡回セールスマン問題
データ構造
第12回 スタックとキュー
第13回 順序キューとヒープソート
第14回 Dijkstra のアルゴリズム
授業時間外の学修の内容
その他
授業時間外の学修の内容（その他の内容等）
毎回、授業の最後に次の時間までに確認しておくべきことを連絡するので、指摘した事柄について整理しておくこと。授業中に関連するプログラミングの問題を挙げるのでそれを用いて復習すること
授業時間外の学修に必要な時間数／週
・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。
成績評価の方法・基準
| 種別 | 割合（％） | 評価基準 |
|---|---|---|
| レポート | 40 | アルゴリズム等に関して授業中に出題した課題をレポートにまとめる。 アルゴリズムを理解して正確に記述できているかどうかが評価の基準となる。 |
| 平常点 | 60 | １．授業中の発言内容を基盤となる知識、応用力を基準に評価する。 ２．アルゴリズムをプログラムに実装する能力を評価する |
成績評価の方法・基準（備考）
課題や試験のフィードバック方法
授業時間内で講評・解説の時間を設ける
課題や試験のフィードバック方法（その他の内容等）
アクティブ・ラーニングの実施内容
ディスカッション、ディベート
アクティブ・ラーニングの実施内容（その他の内容等）
授業におけるICTの活用方法
実施しない
授業におけるICTの活用方法（その他の内容等）
実務経験のある教員による授業
いいえ
【実務経験有の場合】実務経験の内容
【実務経験有の場合】実務経験に関連する授業内容
テキスト・参考文献等
トピックスごとに参考文献や参考になるホームページ等を紹介する