２分木の課題
前回の２分木へのデータの追加処理の説明を受け、 ２分木の課題時間とした。
課題テーマ
名前と誕生日といった複合データを、２分木に保存し、これらのデータに対して 処理を施すプログラムの作成。 ただし、分岐するときのキーとなるデータに対する検索処理は、 ループで記述できるのに対し、非キーに対する検索処理は再帰呼び出しを を必要とすることから、「検索はキーと非キーの２種類で検索ができること」 とした。
オプション課題として、データは単純に整数として、以下のように ASCIIアートやGUIを用いて、視覚的に2分木表示するプログラム作成も可とする。
58 ／ ＼ 25 80
演習中は、真面目に課題に取り組んでいたようだが、未完成の人も多いようなので、 来週は前半に次の内容(2分木による演算子の処理)を説明し、後半を演習とする予定。
構造体と関数とアロー演算子
前回の授業で、構造体の入れ子などの話をしたので、 構造体のポインタ渡しと、オブジェクト指向について話を行う。 オブジェクト指向については、プログラム記述はテスト範囲とはしないことを伝えておく。
ポインタ渡しによる関数化
構造体の配列に対する処理の例として、入力処理と出力処理を関数化する例を示す。
struct Person {
char name[ 10 ] ;
int age ;
} ;
void input( struct Person* p ) {
scanf( "%s%d" , (*p).name , &( (*p).age ) ) ;
}
void output( struct Person* p ) {
scanf( "%sさんの年齢は%d歳です\n" , (*p).name , (*p).age ) ;
}
void main() {
struct Person data[ 10 ] ;
for( int i = 0 ; i < 10 ; i++ ) {
input( &(data[i]) ) ;
output( &(data[i]) ) ;
}
}
ただし、(*p).name といった記載は、面倒なので、 p->nameといった記載が可能。
このプログラムでは、main内部には、Person内部のデータについての 記載がない。このため、Personというデータの内部を知らなくても、 10件分のデータの入力出力が記述できる。 こういった、データ構造や関数内の処理を知らなくても、プログラム記述が できることを隠蔽化と呼ぶ。 特に、関数を用いることで、関数内部の処理手順を知らなくてもよくなり、 これは「手続きの隠蔽化」と呼ばれる。 また、構造体を用いることで、データ構造の内部を知らなくてもよいことは、 「データの隠蔽化」と呼ばれ、この２つの隠蔽化をうまく使えば、 プログラム作成の分業化ができるようになる。
オブジェクト指向
前述の構造体を用いたプログラムは、オブジェクト指向の考え方の 入口となる。このプログラムは、C++であれば。
class Person {
private:
char name[ 10 ] ;
int age ;
public:
void input() {
scanf( "%s%d" , name , &age ) ;
}
void output() {
printf( "%sさんは%d歳です。\n" , name , age ) ;
}
} ;
void main() {
Person data[ 10 ] ;
for( int i = 0 ; i < 10 ; i++ ) {
data[ i ].input() ;
data[ i ].output() ;
}
}
コンピュータの構成とプログラムが動くしくみ
プログラムが、OSによってRAMに呼び出されて動く仕組みや、高級言語の動くしくみを説明する。
コンピュータの構成
コンピュータの基本的構成部品は、CPU,主記憶,補助記憶,周辺装置。 CPUは、メモリから機械語の命令を読み取り(Fetch)、解析(Decode)、メモリ読み出し(Read)、実行(Execute)、メモリ書き込み(Write)を繰り返す。 メモリは、読み出しだけのROMと、読み書きのRAMから構成されるが、 ROMだけでは自由にプログラムを入れ替えて動かすことができない。
コンピュータは電源が入ると、OSを起動するために、ROMに入っている周辺装置を扱い方のBIOSを使い、 OSを起動させるためのプログラム(ブートローダ)を起動する。ブートローダは最終的にOSを起動させ、 ユーザプログラムの起動を待つ。ユーザのプログラム起動要求により、補助記憶装置から プログラムを主記憶に読み出し、実行を行う。
プログラムが動くしくみ
プログラムといっても、コンパイラ方式、インタプリタ方式などがある。 コンパイラは高級言語で書かれたプログラムを、直接実行可能な機械語に変換しておく。 このため、実行時の速度は速い。しかし、プログラムの実行するには、コンパイル・リンクなどの手間が必要となる。また、元々のプログラムがどういった記述なのか解析は困難。 インタプリタ方式は、高級言語のソースを必要に応じて命令の意味を解析し、その都度実行を行う。 このため、プログラムの試作段階で動作を確認しながら開発を行う際には便利である。 しかし、プログラムを実行する際に、高級言語のソースコードが必要となる。 最近では、バイトコードインタプリタ方式と呼ばれる方式もよく利用される。 高級言語の命令を、実行しやすい機械語に近いシンプルな命令にコンパイルし、実行を行う。
一般的なコンパイラ方式では、プログラムを実行するまでに、
- 高級言語のソースを、コンパイルし中間コードを生成。
- 中間コードと、ライブラリ(一般的な関数の処理の中間コードをまとめたもの)を組み合わせて、機械語を生成(リンク処理)
といった手順をとる。
最近のOSは、マルチユーザ・マルチタスクであるため、ライブラリの機械語は同時に動く他のプログラムでも同じように使われている場合が多い。この時、ライブラリの機械語コードがメモリ上に複数あると、 メモリの無駄や、ライブラリの更新の手間が増える。 このため、最近のOSでは、動的リンクライブラリという方式を使い、ライブラリを共有して用いる。
構造体
後期の中間試験までで、構造体について説明の予定。
構造体がなかったら
構造体がない場合、同じようなデータが複数現れると、 配列にしたりすることになるが、そのバリエーションでは、 単純に配列にするだけでは不十分となる。
#define SIZE 50 char name[ SIZE ][ 20 ] ; int math[ SIZE ] ; int sci[ SIZE ] ; int eng[ SIZE ] ; // 複数の学科 char m_name[ SIZE ][ 20 ] ; int m_math[ SIZE ] ; : int ei_name[ SIZE ][ 20 ] ; int ei_math[ SIZE ] ; :
m_name , ei_name といった名前を使い分ける必要があり、 同じような処理をまとめることが難しい。
構造体を使う
複数の異なるデータを、１つの型としてまとめるものが、 構造体。最近のオブジェクト指向では、構造体の概念を 拡張したものなので、必ず使えるようになっておく必要あり。
struct Student {
char name[ 20 ] ;
int math ;
int sci ;
int eng ;
} ;
struct Student saitoh ;
struct Student data[ 50 ] ;
saitoh.math = 80 ;
strcpy( saitoh.name , "t-saitoh" ) ;
strcpy( data[ 0 ].name , "aoyama" ) ;
data[ 0 ].eng = 90 ;
基本は、構造体変数名.要素名 で参照すれば、普通の変数と同じ。
構造体は入れ子にすることもできる。
struct Birthday {
int year ;
int month ;
int day ;
} ;
struct Person {
char name[ 20 ] ;
int age ;
struct Birthday bday ;
} ;
struct Person saitoh = {
"t-saitoh" , 48 , { 1965 , 2 , 7 }
} ;
このように、データ構造をブロック化することを、データの構造化と呼ぶ。 同じように、if (…) { while(…) { … } } といった、ような 入れ子にすることは、手続きの構造化と呼ばれる。 この2つの構造化を合わせて、構造化プログラミングと呼ぶ。
2分探索木
後期最初の授業ということで、今までの内容の総括っぽい 質問を交えながらの授業。
単純リストでは、中央値の参照がO(N)であるため、 そのままでは２分探索法のような処理はできない。
そこで、データと２つの枝からなるノードを作り、 データより小さい値を要素にもつ枝を左に、 大きいものは右枝に格納し、この状態がどこでも成り立つようにする。この方式は、2分木(2分探索木)と呼ばれる。
struct Tree {
int data ;
struct Tree* left ;
struct Tree* right ;
} ;
struct Tree* tcons( int v ,
struct Tree* l , struct Tree* r ) {
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->data = v ;
n->left = l ;
n->right = r ;
}
return n ;
}
int find( struct Tree* p , int key ) {
while( p != NULL )
if ( p->data == key )
return 1 ;
else if ( p->data < key )
p = p->left ;
else
p = p->right ;
}
return 0 ;
}
void main() {
struct Tree* top =
tcons( 53 ,
tcons( 28 ,
tcons( 14 , NULL , NULL ) ,
tcons( 40 , NULL , NULL ) ) ,
tcons( 80 ,
tcons( 63 , NULL , NULL ) ,
tcons( 91 , NULL , NULL ) ) ) ;
if ( find( top , 80 ) )
printf( "find 80\n" ) ;
}
この方式であれば、m段のピラミッド状の木であれば、データ件数 N = 2m-1となり、 m段が綺麗に充填されていれば、最悪の場合のループ回数がmであることから、 処理速度は、O(log(N))となる。
データの挿入では、NULLが入った末端まで辿り着いて、新しい枝を挿入することから、 挿入場所の決定(O(log N)),枝追加(O(1))の時間であり、配列(O(N))などに比べても高速となる。 ただし、このデータのような data 部が小さい場合には、data 1件につき2本のポインタを 使用することから、メモリの使用効率は良くない。
ヒープ
2分木とおなじ考え方で、配列の添字をうまくつかった方式にヒープがある。 この方式では、前述の2分探索木のデータを、配列に以下のように格納する。
| 添字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| データ | 53 | 28 | 80 | 14 | 40 | 63 | 91 |
この方式を取れば、i番目の要素の左枝は(i*2+1) , 右枝は(i*2+2)といった 簡単な計算で求められる。この方式であれば、ポインタは不要となる。 ただし、新たなデータの挿入処理では、段の上からデータを入れ替えを繰り返すなどの 処理が必要となる。
次回には、このデータを操作するための処理で、再帰呼び出しなどを用いる事例を紹介。
texlive-full でかっ
紀要の原稿の修正で、ファイルを触ったら、 epsファイルの位置がずれるトラブル。
いろいろ試したけど、うまくいかない。 以前は動いていたので、texlive の更新 のトラブルと考え、ひとまず texlive 関連を アンインストールし、stable にて再インストール。
# aptitude remove texlive # aptitude install texlive/stable
すりゃいいんだろうけど、どれ消す、どれ入れるだ、 選択肢を選ぶのが大変なので、一時的に apt-source から testing,unstable を消して インストールを行う。
迷惑メールの日本語…
迷惑メールの日本語が機械翻訳なんだろうけど、 わけわかめ。
データベースのガイダンスと導入話
インターネットの情報量
最初に、インターネットで扱われる情報が増加しているという点で、 世界中の情報量を説明。Googleが推測するインターネットの情報量は、 2010年度では281EB(エクサバイト10^18,kMGTP*E*ZY)で、この時点で 55倍/6年だったらしい。 約2倍/年とすれば、2013年は、2ZB(ゼタバイト)程かな。
ちなみに人間の脳は、大脳皮質だけで16TB、脳全体と遺伝情報も含めると230TB程らしい。
Webシステムとデータベース
データベースが情報共有のために重要な技術であり、 Webシステムの中での使われ方 ということで、 サーチエンジンの話(設立当初のYahooのユーザ登録型)や、 Google に代表されるクローラ・ロボットによるサーチエンジンの説明を行う。 これに伴い、データは巨大化し、大量のユーザを抱える現在、 データ検索を極めて短い時間で返答することの難しさを説明する。
このため、一般的なWebシステムでは、Webサーバを負荷分散目的で大量に配置し、 その後段にスレーブデータベースが待機し、 その後段にさらにマスターデータベースが 並ぶという3段スキーマ構成の説明などを行う。 また、最近のIT産業では、システム構築からサービス開始までを短期間に行うために、 LAMP (Linux+Apache+MySQL+PHP) といった構成が多いことなども紹介。
さらに、普及しているリレーショナルデータベースシステムの名称として、 Oracle, MySQL, PostgreSQL, SQLite, BerkleyDB などを紹介し、 ネットワーク型、ファイル型 の違いやSQLを使うもの使わない物などがあることも紹介。 最近では、巨大なデータベースを分散システム上に作る必要から、NoSQLなどと呼ばれる 手法も使われている。
データベースが無かったら…
C言語レベルの簡単な演習でデータベースっぽいことをする時は、 fscanf+fprintfだろうけど、大量データを永続的に扱いたいのであれば、 全データ読み込み＆全データ出力のプログラムを書くのが簡単。 でも、データ量が増えれば、修正・追加のあった部分だけ書きこむ必要が出てくる。 しかしながら、1行1件のデータであれば1行の長さが変化するとダメ。 こういう場合には、1件のデータ長を固定として、lseek+fwrite+freadを使って ランダムアクセスのプログラムを書くことになる。
しかし、こういうプログラムは1件のデータ長が変化すれば、 プログラムの修正も大変。 さらに、複数の並行処理で書き換えを行えるのであれば、 flockなどを使ったプログラムが 必要となる。
計算機システムガイダンス+歴史
専攻科1年の計算機システムの初回。 生産システム全員+環境システム1名で始まった。
計算機システムの授業などについて、シラバスを使って説明した後、 最初の授業として、コンピュータの歴史などを概説。
計算機の歴史
ENIACに始まり、演算素子の変化から、 第一世代(真空管)、第二世代(半導体)、 第三世代(IC)、第3.5世代(LSI)、第四世代(VLSI)との変遷を説明する。
次に学生自身が縁の深いということで、パソコンの歴史などを説明する。 電卓向けのi4004から、8bitコンピュータi8008が発生し、 パソコンの普及で、i8080(Z80を含む)、MC6800(6502,6809)などが 使われていく。
性能があがり、16bitコンピュータに移行する際には、i8086のIBM-AT機 向けに MS-DOS(Microsoft) が開発される。この際に機械語の命令互換性 を考慮したことから、この後、Intel のプロセッサが広く普及していく。 一方、モトローラの16bitコンピュータ68000は、命令互換性が低く、 売れ行きが伸びないながらも、Apple社のMacintoshに採用され、 GUIの操作性の良さから教育機関などでは普及が進んだ。 MacintoshのGUIの成功は、Microsoft社にも及び、Windows が開発される。
MacintoshやWindowsのGUIが普及すると、複数のアプリケーションを使う ことが当たり前となり、これまでのシングルユーザ・シングルタスクな OSでは不十分となり、マルチユーザ・マルチタスクなOSが必要となった。 これらのOSでは、他のアプリケーションの不具合の影響を受けないために、 メモリ保護機能などが重要となってきた。 GUIのために十分な処理速度とメモリ保護機能などを備える必要から、 32bitコンピュータが出てきた。
32bitコンピュータとして、Intelの80386やモトローラの68030などが 生まれるが、16bit移行時の市場を Intel が握っていた。 このため、WindowsとIntelの影響力が大きいことから、Wintelといった 言葉で揶揄されることも多かった。
32bitコンピュータの普及と共に、Windowsでは、シングルタスク・ シングルユーザのWindows/95などから、マルチタスク・マルチユーザな、 Windows NT/2000/Xp に移行していく。
一方、このWintelの市場の独占には、情報開示とサードパーティによる 競争が大きく影響している。16bitコンピュータでi8086が普及したのは、 IBMがAT機のハードウェアの情報を広く開示し、それにそってAT互換機が 開発され、大量生産による価格競争と性能競争がおこり、安価で高性能 なものが大量に作られたことが原因となっている。
16bitコンピュータが普及する頃には、インターネットの普及も進んだ。 特に、Windows/95 が普及に貢献している。 この一方、OS では、汎用機の高性能なマルチユーザマルチタスク機能の、 Multics を小型コンピュータに移植した unix が生まれている。 これらは、インターネットを支えるサーバなどで広く普及している。
そして、unix は 32bitのi80386で動くようにと、Linux が開発される。 特に、Linuxは、GNUライセンス(無償利用可、改良を加えたら必ず改良物も 公開)であったため、インターネットの普及とともに広く利用されるように なっている。最近では、Android 携帯に Linux が使われている。
科研費に関する講演会
科研費の最近の動向
アメリカのNSF、NIHと比べてまだまだ少ない。
科研費への「基金化」の導入。前倒しや繰越が容易になった。
11月上旬までに調書提出、12月第一段審査、2月第二段審査、3月内定。
審査員は大量の審査を行うので、専門過ぎない説明や図を活用した説明が重要。 新規性や優位性をわかりやすく。 評価は、学術的重要性、妥当性、研究計画方法の妥当性、 独創性革新性、波及効果普遍性、研究遂行能力と研究環境の適切性。
不正使用に関する事例。捏造、改竄、盗用。
研究成果の公開。研究成果報告書、謝辞で科研費を明示。
高専の持ち味を生かして手中に収める科研費
VOS塾形式/グループディスカッションをすることが重要。
# 活力（Vitality）、独創力（Originality）及び世のための奉仕（Services）
科研費は予算申請書。欲しいものにアイデアを出す。
グループディスカッションの方法。5分で理解できる内容か、ワクワクする内容か。 パワポA4×1枚を5分で説明する資料にできるか。
キーワードには専門用語と数字を交えた具体性。 2年目3年目の実験が、目に見えるように。PDF資料で審査されるんだから資料にリンク埋め込みもあり。 自身の実験を踏まえた秘密のような具体性を示す。