アルゴリズムとデータ構造II

授業目的

「アルゴリズムとデータ構造I」に引き続いて、文字照合アルゴリズム、整列アルゴリズム、グラフのアルゴリズムなど基本的なアルゴリズムおよびアルゴリズムの設計手法について教授する．

授業概要

文字照合アルゴリズムにおいては、単純なアルゴリズム、KMPアルゴリズム、BMアルゴリズムおよびサークルアルゴリズムを紹介する。グラフのアルゴリズムについては、グラフの表現、グラフの探索、最短経路について解説する。整列アルゴリズムにおいては、まず、整列の基本原理を紹介する。そして、選択による整列（単純法、ヒープソート）、挿入による整列（単純法、シェルソート）、交換による整列（バブルソート、コームソート、クイックソート）およびマージによる整列（マージソート、自然マージソート）に関するそれぞれのアルゴリズムについて解説する。さらに、比較によらない整列方法についても紹介する。アルゴリズムの設計手法については、分割統治法、貪欲法、バックトラック法と動的計画法について解説する。