共有のあるデータの取扱い
これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数に […]
文字列のハッシュ関数
文字列のハッシュ値 ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普 […]
データベースの物理設計
データベース後半課題 データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。 情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研 […]
プログラムの処理時間の測り方
今回の課題レポートでは、テスト素点が良くレポート提出でも加点が少ないと思われる人でも、まじめに取り組んだレポート提出が多かった。この中で、興味深いレポートで、2分探索木の検索が偏っていたらO(N),バランスが良ければO( […]
ハッシュ衝突の対策
前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか？ ハッシュ法を簡単なイメージで説明 […]
データベースの設計と正規形
データベースの設計において、重要な正規形についての説明 正規形 データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。 […]
ハッシュ法(導入)
前半は中間試験の返却と解説を行う。後半は次のテーマのハッシュ法の導入話。 ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスがで […]