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

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

概要

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

目標

授業計画

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

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

ソースコード集（ java, C，五十嵐健夫先生作）

• 第1回. 4/13 （水）講義の概要
• 第2回. 4/20 （水）アルゴリズムと計算量
• 第3回. 4/27（水）基本的なデータ構造：配列とリスト，スタック，待ち行列，木
• ---- 5/4（水）祝日（みどりの日）
• 第4回. 5/11 （水）基本的なデータ構造: 優先度付き待ち行列，ヒープ 五十嵐先生の作成された課題（ヒープ） ,
• 第5回. 5/18 （水）集合の表現法： 2分探索木
• 第6回. 5/25 （水） 平衡木，2-3木
• 第7回. 6/1 （水）集合の表現法： ハッシュ, 集合群
• 第8回. 6/8 （水）ソート：バブルソート, クイックソート 五十嵐先生の作成された課題（クイックソート） ,
• 第9回. 6/15 （水） ソート：マージソート，ヒープソート
• 第10回. 6/22 （水） ソート：バケットソート, 基数ソート，有向グラフ
• 第11回. 6/29（水） 有向グラフ（ダイクストラ，フロイド，探索，強連結）， 無向グラフ（最小木，プリム，クラスカル，関節点）
• 第12回. 7/6 （水） 文字列の検索：KMPアルゴリズム
• 第13回. 7/13 （水） 文字列の検索：BMアルゴリズム
• 第14回. 7/20 （水） 設計法（分割統治法，動的計画法）
  • 自主勉強用： ch1, ch2, ch3, ch4, ch5, ch6, ch7, ch8
• 第15回. 7/27 （水） 定期試験
• 第16回. 8/3 （水） 返却・解説．総まとめ

教科書・参考書籍

• 教科書：データ構造とアルゴリズム（五十嵐 健夫 著，2007, 数理工学社） サポート情報
• 参考書： アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3) （石畑 清 著，1989, 岩波書店）
  
• 参考書： 初めてのコンピュータサイエンス （J. Campbell ほか著，長尾訳，2010，オライリー・ジャパン）
  
• ドットインストール: python, C,

成績の評価基準

定期試験(70%)と小テスト(30%) により判定する．再試験はおこなわない．

• 伊達のHPへ