平成15年度 創造都市研究科
データ構造とアルゴリズム(1)
2003年4月20日作成
2003年4月 4日9時35分改訂
データ構造とアルゴリズムの歴史 VOD(Windows Media)
- 洋書
- D.E.Knuth,"The Art of Computer Programming: Vol.1 Fundamental Algorithm", Addison-Wesley, 1968, 1973
- D.E.Knuth,"The Art of Computer Programming: Vol.3 Sorting and Searching, Addison-Wesley, 1973
- A.V.Aho, J.E.Hopcroft, J.D.Ullman,"The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974
- A.V.Aho, J.E.Hopcroft, J.D.Ullman,"Data Structures and Algorithms", Addison-Wesley, 1983
- 茨木俊秀,「アルゴリズムとデータ構造」,21世紀を指向した電子・通信・情報カリキュラムシリーズ B-4,昭晃堂,1989
- プログラミングからアプローチ
- 河西朝雄,「Visual Basicによる-はじめてのアルゴリズム入門」,技術
評論社,1999
- R.Lafore(著),(訳),「Javaで学ぶアルゴリズムとデータ構造」,SOFT BANK,1999
情報学、情報科学、計算機科学 VOD(Windows Media)
- 情報学(Informatics)
- Computer Science
- 学会
-
アルゴリズムの設計と解析
- 問題を解く(Operations Research的に) VOD(Windows Media)
- 問題をモデル化(パラメータ抽出)
- モデルを数学的に定式化(数学的な問題になる)
- 問題を解く
- 解をもともとの問題へ(現実的な解を採用する)
- 問題からプログラムへ(データ/アルゴリズム)
- 数学モデル/自然語のアルゴリズム
- 抽象データ型/疑似言語
- データ構造/プログラム
- 抽象データ型(Abstract Data Type: ADT)
- 数学モデルとその操作の集合
- 但し実現方法は問題の対象による(操作の種類やデータの性質等に依存)
- 例
- LIST: MAKENULL, FIRST, NEXT, INSERT
- STACK: MAKENULL, TOP, POP, PUSH, EMPTY
- QUEUE: MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY
- TREE: PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, ROOT, CREATE, MAKENULL
- NETWORK
- SET
- オブジェクト指向言語への入口
- 手続き(操作)とデータ構造の直交性
- データ型、データ構造、抽象データ型 VOD(Windows Media)
- (単純な)データ型: 変数、配列、文字、文字列
- データ構造: 単純なデータ型の組合せ
- データ構造とその操作が一緒になる：オブジェクト
- 抽象データ型ではそこまで踏み込まない
- プログラムの実行時間 VOD(Windows Media)
- 問題(problem)と問題例(instance)
- 実行時間：問題にサイズに対する指標
- 最悪実行時間、平均実行時間
- 計算複雑度：普通は最悪の場合の時間/メモリ
- 時間複雑度(time complexity)
- 空間複雑度(space complexity)
- 難しい問題と易しい問題：難しいの定義は
- 例
- 易しい問題：サーチ、並べ替え
- 難しい問題：巡回セールスパーソン問題、囲碁、将棋
- プログラム言語
- MIX(Knuth)
- Pidgin Algol
- Super Pascal
- C, C++
- Java
- ちょっとオブジェクト指向
- オブジェクト(データとその上で定義された操作群)
- クラスとインスタンス(Apple, An Apple, The Apple)
- 継承(inheritance)
並べ替え
- モデル
- データがすでに揃っている場合
- データが順次来る場合
- 簡単な並べ替え
- Insert Sort
- Selection Sort
- Bubble Sort
- Bucket Sort
- Quick Sort
中野のホームページへ