ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできない […]
データベースとB木
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを […]
ドメイン名とDNS
ドメイン名とDNS インターネットでの通信では、IPプロトコルでコンピュータを指定するが、IPアドレスは無機質で覚えるのが大変であり、コンピュータに名前をつけて利用する。この際に、コンピュータの所属などが分かるようにした […]
データべースの設計と正規形
テスト問題の返却および解答の説明を行い、その後、データベースの設計において、重要な正規形についての説明の導入。 正規形 データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正 […]
トランスポート層・TCPとUDP
前回の授業でブロードキャストなどの説明をしたことを踏まえ、DHCP について改めて説明 DHCP 前回の IP では、異なるサブネットを繋ぐ役割としての Internet Protocol (IP) について説明をした。 […]
木構造の探索・深さ優先探索・幅優先探索
深さ優先探索(前順) 以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。 しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を […]
2分木による構文木
コンパイラの処理の流れ 構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。 Cコンパイラのソース ↓ プリプロセッサ (#defin […]
ERモデル
データベースの設計 リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。 例えば、学生の成績データが以下のような1つのテーブルで構成されるデータだった場合、 ID name grade sub […]
専攻科実験・コンパイラと関数電卓プログラム作成
コンパイラの技術と関数電卓プログラム(1) 再帰下降パーサによる構文解析(LL法)による電卓プログラム作成 補助資料：コンパイラの技術と関数電卓プログラム(1-2) 課題 複数桁の数字が使えること。 式中に空白が使える […]
2分木の応用(意思決定木と演算子)
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。 意思決定木 意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹 […]