Views
Document
Event
File
Folder
Image
Link
News Item
Photo
Photo Album
Topic
Weblog
Wiki Page
データ構造とアルゴリズム
Document Actions
のイントロダクション
はじめに
- と、書かないとはじまらない
- 今年は、ピンチヒッター
- なので、
成績が悪かったら
- 来年、じっくり勉強してもらう
というのは冗談？
- 至らないところがあるかも
- しれませんが、教科書をよく読んで
- 理解するようにしてください。
教科書
- 「データ構造とアルゴリズム」
- （コロナ社）
- 電子情報通信学会大学シリーズ
話は飛びますが
- 私は、なんとなく
- 「ネットワーク」
- が、専門です
計算機とネットワークは
- ソフトが無ければ
- ただの箱
- ただの線
ネットワークのソフト
- 便利にする「データベース」
- 安全にする「暗号」
データベース
- 昨年までピンチヒッターで講義した
- ネットワークのピンチヒッターは
- 片岡先生（菊地研マスター卒）
データベースに必要なもの
- データを入れる・整理する
- 「データ構造」
- 整理する・検索する
- 「アルゴリズム」
アルゴリズム
- 要するに計算方法です
- データの構造（どう入れるか）が変わると
- 当然変わります
要するにプログラミング？
- プログラムにするにはプログラム言語が必要
- アルゴリズムはプログラムにする手前
- 流れ図、擬似プログラム言語 が使われる
これを勉強したら
- プログラムがバンバン書けるようになる？
- というわけでもない
よいプログラムを書くには
- よいプログラムを使ってください
- よいプログラムを読んでください
卒業研究のヒトコマ
- 100x100 の行列の固有値を求めたのですが、遅いんです。
- どれどれ、ここんとこは？
- はい、バブルソートのプログラム組みました
- qsort() 使いましょうね。
よいプログラムは
- ライブラリに入っています。
- man で、qsort, regex, dbm/db を読んでみよう
よいプログラムは
- オープンソースになっています。
- オープンソースカンファレンス
- TOSA orz
土佐オープンソース勉強会
各論のイントロ
- スタックと待ち行列
- スタック -> CPU が持ってる
- 待ち行列 -> たいがいの IO 装置が持ってる
- 再帰ができるのもスタックのおかげ
文字列照合
- grep, regex
- Python ... import re
- 置き換えもできる ... 文字列処理
ユーザ環境を作ってあげたり修正してあげたり
おせっかいができる
木構造
- データベース
楽しい「モーニング娘。」で学ぶデータベースは
昨年で終わり。
グラフ構造
- インターネットそのもの
リンクが生み出すグラフ空間
データ整列
- Python ... sort()
- ライブラリを使えるようになってください。
データ探索
- ２分探索
- ハッシュ
- 木構造 ... B tree, B+ tree
そして、若きプログラマーは
- データベース修行の道へ
- ネットワーク修行も忘れないで。
本日の問題
- 用紙は縦長で使用
- 日付、学生番号、氏名を明記
- あなたは、どんなアルゴリズムに興味がありますか？
又は、どんな問題についてプログラムを書いてみたいですか？
主な回答
- 暗号解読
- Winny
- 巡回サラリーマン問題(GA)
- ソート
- 再帰
