授業アンケート 2023 後期
情報工学演習(2EI) 84.3 ポイントと高い評価であった。プログラミングコンテストを用いた演習内容の発表では、こちらが想定してた難易度の高い問題について説明したものが少なく、来年度は制約などを設けたいと思った。 情 […]
関数ポインタ
関数ポインタとコールバック関数 JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワー […]
参照カウンタの問題とガベージコレクタ
前回の授業では、共有のあるデータ構造では、データの解放などで問題が発生することを示し、その解決法として参照カウンタ法などを紹介した。今日は、参照カウンタ法の問題を示した上で、ガベージコレクタなどの説明を行う。 共有のある […]
チェイン法と共有のあるデータの問題
前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか？ ハッシュ法を簡単なイメージで説明 […]
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできない […]
コンパイラと正規表現とBNF記法
コンパイラと言語処理系 2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。 高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。そ […]
2分木による構文木とデータベースとB木
コンパイラの処理の流れ 構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。 Cコンパイラのソース ↓ プリプロセッサ (#defin […]
意思決定木と演算子
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。 意思決定木 意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹 […]
AVL木と2分ヒープ
2分探索木へのデータ追加と不均一な木の成長 先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。 しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]