後期の中間試験までで、構造体について説明の予定。

構造体がなかったら

構造体がない場合、同じようなデータが複数現れると、 配列にしたりすることになるが、そのバリエーションでは、 単純に配列にするだけでは不十分となる。

#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つの構造化を合わせて、構造化プログラミングと呼ぶ。

後期最初の授業ということで、今までの内容の総括っぽい 質問を交えながらの授業。

単純リストでは、中央値の参照が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 = 2^m-1となり、 m段が綺麗に充填されていれば、最悪の場合のループ回数がmであることから、 処理速度は、O(log(N))となる。

データの挿入では、NULLが入った末端まで辿り着いて、新しい枝を挿入することから、 挿入場所の決定(O(log N)),枝追加(O(1))の時間であり、配列(O(N))などに比べても高速となる。 ただし、このデータのような data 部が小さい場合には、data 1件につき2本のポインタを 使用することから、メモリの使用効率は良くない。

ヒープ

2分木とおなじ考え方で、配列の添字をうまくつかった方式にヒープがある。 この方式では、前述の2分探索木のデータを、配列に以下のように格納する。

この方式を取れば、i番目の要素の左枝は(i*2+1) , 右枝は(i*2+2)といった 簡単な計算で求められる。この方式であれば、ポインタは不要となる。 ただし、新たなデータの挿入処理では、段の上からデータを入れ替えを繰り返すなどの 処理が必要となる。

次回には、このデータを操作するための処理で、再帰呼び出しなどを用いる事例を紹介。

紀要の原稿の修正で、ファイルを触ったら、 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資料で審査されるんだから資料にリンク埋め込みもあり。 自身の実験を踏まえた秘密のような具体性を示す。