宮崎大学 工学部 情報システム工学科 2013年度前期 授業科目：アルゴリズムとデータ構造

単位数：２単位 必修
対象：２年次
日程：水 10:30〜12:00
教室： B-209
担当教員： 伊達 章
研究室番号： 工学部棟 A-333
メール：
ホームページ：http://www.cs.miyazaki-u.ac.jp/~date/lectures/aad/index.html
講義中のコメント投稿先
オフィスアワー： 木曜日 16:30--17:30 （事前連絡して頂ければ随時受け付けます）

学務情報システムのシラバス

概要

コンピュータに何らかの仕事をさせるには，そのための手順を与えなければならない．この手順のことをアルゴリズムとよぶ．普通なら何年もかかるような問題が，上手な手順を使うとあっという間に解決できる場合がある．また，データをコンピュータの内部でどのように表現するか，ということが手順よりも重要になる場合が多い．このデータの表現方法をデータ構造とよぶ．本講義では，効率のよいプログラムを書くための基礎となる，基本的なデータ構造およびアルゴリズムについて学ぶ．

目標

授業計画

あくまで予定であって、変更の可能性があります．

アルゴリズムをプログラミング言語で表現したものがプログラムです．複雑なプログラムでも，使われているアルゴリズムは検索とソート，データ構造の種類は配列やリスト，ツリー，ハッシュテーブルなどに限られています．ここでは，いくつか数少ない優れたデータ構造とアルゴリズムについて学びます．

• 第1回. 4/10 （水）講義の概要
• 第2回. 4/17 （水）アルゴリズムと計算量
• 第3回. 4/24 （水）基本的なデータ構造：配列とリスト，スタック，待ち行列，木
• 第4回. 5/1 （水）基本的なデータ構造: 優先度付き待ち行列，ヒープ
• 5/8（水）は月曜日の時間割
• 第5回. 5/15 （水）集合の表現法： 2分探索木，平衡木，2-3木
• 第6回. 5/22 （水） 集合の表現法： ハッシュ, 集合群
• 第7回. 5/29 （水）ソート：バブルソート, クイックソート
• 第8回. 6/5 （水） ソート：マージソート，ヒープソート
• 第9回. 6/12 （水） ソート：バケットソート, 基数ソート，有向グラフ
• 第10回. 6/19（水） 有向グラフ（ダイクストラ，フロイド，探索，強連結）
• 第11回. 6/26 （水） 無向グラフ（最小木，プリム，クラスカル，関節点）
• 第12回. 7/3 （水） 文字列の検索：KMPアルゴリズム
• 第13回. 7/10 （水） 文字列の検索：BMアルゴリズム
• 第14回. 7/17 （水） 設計法（分割統治法，動的計画法）
• 第15回. 7/24 （水） 定期試験
• 第16回. 7/31 （水） 総まとめ

教科書・参考書籍

• 教科書：データ構造とアルゴリズム（五十嵐 健夫 著，2007, 数理工学社） サポート情報
• 参考書： アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3) （石畑 清 著，1989, 岩波書店）
  
• ドットインストール: python, C,

成績の評価基準

定期試験70% 小テスト 30%

• 伊達のHPへ