科目名[英文名]
アルゴリズム論   [Algorithms]
区分	工学部専門科目等	選択必修		単位数	2
対象学科等		対象年次	2～4	開講時期	後学期
授業形態	後学期	時間割番号	022817
責任教員 [ローマ字表記]
金子 敬一   [KANEKO Keiichi]
所属	工学部	研究室		メールアドレス

概要

本講義では，代表的なアルゴリズムを紹介するとともに，アルゴリズムの良さを評価したり，良いアルゴリズムを作ったりするための指針となる手法について論ずる．

到達基準

プログラムを作成する前段階で、手順のあらましと計算時間の見積ができるようになること。

授業内容

第1回 　第1章　データと計算量 　1.1 データの表現 　1.2 再帰呼出し 　1.3 算法と計算量 第2〜3回 　第2章　探索 　2.1 2分木 　2.2 バランス木 　2.3 ヒープ 　2.4 ハッシュ法 第4〜5回 　第3章　整列 　3.1 整列と順序 　3.2 バブルソート 　3.3 挿入ソート 　3.4 マージソート 　3.5 ヒープソート 　3.6 クイックソート 第6，7回 　中間試験と解説 第8〜10回 　第4章　グラフとネットワーク 　4.1 用語の定義 　4.2 グラフの探索 　4.3 強連結性分 　4.4 ダイクストラ法 　4.5 ワーシャル・フロイド法 　4.6 最大流問題 第11回 　第5章　文字列照合 　5.1 単純法 　5.2 KMP法 第12回 　第6章　NP完全問題と近似算法 　6.1 NP完全問題 　6.2 近似算法 第13回 　最近のトピック 第14，15回 　期末試験と解説

履修条件・関連項目

計算機プログラミングの能力は必須．数理計画論を併せて履修することが望ましい．

テキスト・教科書

なし

参考書

「アルゴリズム」，「データ構造」というキーワードを含む書物．「計算の理論」などの書物も参考になる．

成績評価の方法

中間試験と期末試験等を総合して成績をつける．

教員から一言

計算機プログラミングが好きであることが必須条件である．特に，機械語プログラミングの能力は重要である．アルゴリズムに関する書物は，近年，多数出版されているが，玉石混交である．良書を選ぶのも学問のうちである．パズルが好きな人に適した科目である．

キーワード

アルゴリズム，データ構造，計算複雑度，グラフ，計算幾何学

オフィスアワー

随時．電子メールによる質問を歓迎します．k1kaneko@cc.tuat.ac.jp

備考１

備考２

参照ホームページ

開講言語

日本語

語学学習科目

更新日付

2018/03/08 15:02:17