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

対象：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/12 （水）講義の概要
• 第2回. 4/19 （水）アルゴリズムと計算量
• 第3回. 4/26（水）基本的なデータ構造：配列とリスト，スタック，待ち行列，木
• ---- 5/3（水）祝日（憲法記念日）
• 第4回. 5/10 （水）基本的なデータ構造: 優先度付き待ち行列，ヒープ 五十嵐先生の作成された課題（ヒープ） ,
• 第5回. 5/17 （水）集合の表現法： 2分探索木
• 第6回. 5/24（水） 平衡木，2-3木
• 第7回. 5/31 （水）集合の表現法： ハッシュ, 集合群
• 第8回. 6/2 （金）ソート：バブルソート, クイックソート 五十嵐先生の作成された課題（クイックソート） ,
• 第9回. 6/7 （水） ソート：マージソート，ヒープソート
• 第10回. 6/14 （水）特別回：祝 RESASアプリコンテスト最優秀賞： 開発者が語る！ （場所は 330記念交流会館コンベンションホール）
  • 案内（pdf）
  • ひなたGIS， サンプルコード ， ol3.html
  • JavaScript入門 ドットインストール，ノンプログラマのためのJavaScriptはじめの一歩
  • 「ひなたGIS×ビッグデータWEEK in 宮崎」（6/24土, 25日）
• 第11回. 6/21 （水） ソート：バケットソート, 基数ソート，有向グラフ
• 第12回. 6/28 （水） 文字列の検索：KMPアルゴリズム
  • Cloud9 ： 演習室とほぼ同じ環境をクラウド上で実現． Cloud9 アカウント作成メモ
  • github 最低限の使用メモ
    • ファイルをダウンロードするときは，Raw を押して生ファイルの url を取得しておく．
    • hmm201.c，gp301png
• 第13回. 7/5 （水） 文字列の検索：BMアルゴリズム
• 第14回. 7/12 （水） 設計法（分割統治法，動的計画法）
  • 自主勉強用： ch1, ch2, ch3, ch4, ch7, ch8
• --- 7/14（金） 16:40〜 A-116 「2時間でアプリ公開！ゼロからのプログラミングRails講座」
• 第15回. 7/19 （水） 定期試験
• 第16回. 8/2 （水） 返却・解説．総まとめ

教科書・参考書籍

• 教科書：データ構造とアルゴリズム（五十嵐 健夫 著，2007, 数理工学社） サポート情報
• 参考書： アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3) （石畑 清 著，1989, 岩波書店）
  
• 参考書：魔法のCプログラミング演習書 （倉光君郎著，2017，コロナ社）
  
• ドットインストール: python, C,

成績の評価基準

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

• 伊達のHPへ