B木の構造とデータベース
2分探索木の考え方を拡張したもので、B木がある。
B木の構造
B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。
B木からデータの検索
データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(N) O(logN) 資料修正注意となる。 (さらに…)
学科WordPressの設定変更
私は、CMSを昔から使っていたし、学科のWordPressサーバも設定していて活用しているけど、学科PRを目的としているWebサーバで、「最近の投稿」の欄は、私の投稿ばかり。
違和感あるし、”Widget Logic”というプラグインを入れて、左側のウィジェットメニューの「最近の投稿」には学科PRとなるような記事だけを表示するように設定を行った。これに加え右側のウィジェットメニューには、自分のカテゴリーの記事を参照している時だけ「自分の最近の投稿」が表示されるように設定する。
固定記事の「斉藤徹」の子ページの時にも、私の「最近の投稿」が表示されてほしいけど、is_page() 判定だと、子ページでは表示されないな…(x_x;
式の構文木と評価
2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。また、これらを用いてコンパイラを作るための知識を解説する。
2項演算と構文木
演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で扱うと都合が良い。
＋ ／ ＼ １ ＊ ／ ＼ ２ ３
演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして…
(さらに…)
専攻科実験・コンパイラと関数電卓プログラム作成
- コンパイラの技術と関数電卓プログラム(1)
- 課題
- 複数桁の数字が使えること。
- 式中に空白が使えること。
- 何らかの演算子を追加すること。
- (例) %,単項演算子のマイナスなど
- 演算子が左結合か右結合か確認すること。
- オプション課題
- 変数が使えること。
(変数名は1文字のA-Zといったもので良い)
- 変数が使えること。
- レポート内容
- コンパイラ技術の概要、課題(1)の説明・ソース・動作検証、考察
- 課題
- コンパイラの技術と関数電卓プログラム(2)
- 課題
- 基本的に、lex+yaccで(1)と同様の課題完成を目指す。
- レポート内容
- lex,yaccの概要、課題(2)の説明・ソース・動作検証、考察
- 課題
sakura.ioでIT人材育成
さくらインターネット様による高専のIT教育支援を受け、sakura.io,Arduino用シールド,IchigoJam が届きました。
これらの機材を使い、電子回路からインターネットへと幅広い開発の経験から、創造的IT人材育成にチャレンジします。
IT教育支援の共同研究(H30年3月まで)として、以下のテーマに取組みます。
- sakura.ioを用いた、低学年でのIoT連携実験
- おなじく、高学年での創造的なシステム構築演習
- さくらのクラウドを用いた、クラウド環境実験
- これらを応用した卒業研究
意志決定木と式を表す木
意志決定木
2分木の応用で最も単純な物として、意志決定木がある。
yes/no の答えを回答すると、最終的に「あなたの性格は✕✕です」と表示するようなヤツ。
struct Tree {
char* q_a ;
struct Tree* yes ;
struct Tree* no ;
} ;
top
＼
あなたは勉強が好き？
／yes ＼no
ものづくりは好き？ 人と話すのが好き？
／yes ＼no ／yes ＼no
技術者タイプ ◯◯◯ 営業タイプ ◯◯◯
専門基礎3-合成抵抗
専門基礎3の電気回路の基礎で、今日は合成抵抗と各場所の電圧・電流について演習。
前半は個別で解いてみる
後半はグループ討議方式
- 問題
- 6つのグループに分かれる。
- 前半３つ後半３つで、
- グループで協力しながら解き、各自で解き方の説明を考える。
- 最初に誰かが解き方を他の人に説明。
(解き方に自信がない場合は別の人に説明してもらう) - その説明より判りやすい説明ができる人はその考え方を説明。
- 最後に前で、その解き方でクラスに説明。
- 他のグループからさらに判りやすい説明の提案があったら前で説明。
自宅レポートでの再提出もOK
なお、授業内で理解度確認の小テスト形式で実施しているが、じっくり時間をかけて問題を解きたい人もいるみたい。このため、解いた内容は授業時間内に集めているけど、自宅で問題をダウンロードして、レポートとして再提出しても良いものとする。
SQLの基礎とデータ定義文
前回のデータベースの説明で、最も中心的な機能のSQLについて説明を行ったが、その続き。
SQLの基礎
データベースでは、記録されているデータの読み書きは、SQLという言語を用いる。 SQLでは、射影・結合・選択を表す処理で構成される。
SELECT S.業者番号 -- 必要とされるデータを抽出する射影 --
FROM S -- 複数のテーブルを組合せる結合 --
WHERE S.優良度 >= 20 ; -- 対象となるデータを選び出す選択 --
// C言語なら
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
if ( S[i].優良度 >= 20 )
printf( "%d¥n" , S[i].業者番号 ) ;
}
Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。
SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;
ここで、SQLの最も便利な機能は、直積による結合処理。2つの表を組み合わせる処理。
PERSON 個人の情報 ((C言語の構造体をイメージ))
id | name | age | work | struct PERSON {
----+---------+-----+--------- | int id ;
101 | tsaitoh | 52 | teacher | char name[10] ;
102 | tomoko | 41 | worker | int age ;
203 | mitsuki | 18 | student | char work[10] ;
| } table_person[3] ;
GRAD 卒業した学校
id | graduate # idは外部キー
----+----------- | struct GRAD {
203 | manyo-jh | int id ;
102 | fukui-nct | char graduate[10] ;
101 | univ-fukui | } table_grad[3] ;
※ ER図的に言うと、実体(PERSON),関係(GRAD) の他に実体(SCHOOL)があるべき
