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

概要

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

到達基準

プログラムを作成する前段階で、手順のあらましと計算時間の見積ができるようになること。履修案内のカリキュラムマップを参照してください。

授業内容

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

履修条件・関連項目

計算機プログラミングの能力は必須。数理計画論を併せて履修することが望ましい。本学の標準時間数に準ずる予習と復習を行うこと。

テキスト・教科書

なし

参考書

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

成績評価の方法

手順のあらましと計算時間の見積ができることを確かめるため，中間試験と期末試験等を総合して成績をつける．なお，オンライン教育における成績評価方法は，すべての出席を前提とし，双方向性を利用した学習意欲，レポートと中間試験（，または課題）および期末試験（，または課題）等を総合的に評価し，本学が定める標準的な学修時間に相当する学修効果が認められる場合に単位を付与する．

教員から一言

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

キーワード

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

オフィスアワー

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

備考１

備考２

参照ホームページ

開講言語

日本語

語学学習科目

更新日付

2022/01/27 10:16:40