データ構造とプログラミング （第１回） 大岩　元 ＴＡ:　武田林太郎 ＳＡ:　明石　敬

教科書 Robert Lafore 著　岩谷　宏訳 　Java で学ぶ　アルゴリズムとデータ構造 　ソフトバンク　１９９９年　

日本のIT人材不足の実態 １． 先端的研究社層が、1桁以上薄い ２． 上級技術者（高度人材）も１桁少ない 先端　←　初級 Innovators Early Adopters Early Majority Late majority Laggards 技術レベル 先端的研究者 高度人材 ソフトウェア 開発技術者 基本情報 技術者 初級シスアド 米国 2.5% 13.5% 34% 16% 日本 0.5% 20% 45% 32% 図1　IT人材資源日米比 １．　先端的研究社層が、1桁以上薄い ２．　上級技術者（高度人材）も１桁少ない ３．　 Early Majority（旧１種レベル）も少ない ４．　 Late majority（旧２種レベル）は人口比に近い ５．　情報技術の素人（初級シスアド）は似たり寄ったり 表１　米国と比較した日本の技術者の現状

インド人、中国人IT技術者 日本人技術者は年収3-400万円のプログラマーしかいない 外国人技術者確保が現在の至上命令に 日本人は仕様を作れない 外国人は仕様通りしか作れない 日本語教育が問題 岩崎式日本語教育(MISJ)なら400時間の教育で十分可能

ACMプログラミングコンテスト 過去4回国内予選の優勝校は日本以外 2001年函館予選 2001年世界大会(ハワイ) 1位 復旦大 2位 東大 3位東工大 2001年世界大会(ハワイ) 1位 上海交通大 2位 マサチューセッツ工科大 3位 ウォータールー大 ……… 18位 東大

ソフト技術者の問題 いい加減な仕事でも、コンピュータでやれば役に立つ 役に立つソフトだからと金を払う人がいる かせげるからプロだと思うソフト技術者 仕事をたのむ人がしっかりする必要がある

Computer Science Body Of Knowledge(CC2001) DS. Discrete Structures (43 core hours) PF. Programming Fundamentals (38 core hours) AL. Algorithms and Complexity (31 core hours) PL. Programming Languages (21 core hours) AR. Architecture and Organization (36 core hours) OS. Operating Systems (18 core hours) NC. Net-Centric Computing (15 core hours) HC. Human-Computer Interaction (8 core hours) GV. Graphics and Visual Computing (3 core hours) IS. Intelligent Systems (10 core hours) IM. Information Management (10 core hours) SE. Software Engineering (31 core hours) SP. Social and Professional Issues (16 core hours)

大学における情報分野の アクレディテーション(JABEE) 理論・問題分析・設計ができる アルゴリズムとデータ構造 コンピュータシステムの構成 情報ネットワーク ソフトウェアの設計 プログラミング言語の諸概念 プログラミング能力 離散数学と確率・統計

ストック(体系化された知識とその応用力) 学習におけるストックとフロー ストック(体系化された知識とその応用力) フロー(取り込んだ知識) 知識 時間

情報処理能力のブーター 身体軸 タッチタイピング 論理軸 プログラミング 感性軸 図解力(発想力)

データ構造とアルゴリズムの重要性 現実世界をうまくモデル化できる 現実世界のデータを記録したり表せる プログラムをより速く実行できる アルゴリズムの選択がまずいと１秒の計算が何時間もかかる 抽象的な表現を実感できるようになる

インデクスカードの実現（例） データをどのように表現するか 枚数が数万枚になっても大丈夫か 新しいカードの挿入や不要カードの削除はどう（能率的に）実現できるか カードの探索は高速にできるか

データ構造の利害得失（例） 配列の利点 順序配列の利点 リストの利点 配列の欠点 順序配列の欠点 リストの欠点 挿入が高速 インデクスで高速アクセス 順序配列の利点 探索はより高速 リストの利点 挿入と削除は速い 配列の欠点 探索と削除が遅い 順序配列の欠点 挿入と削除は遅い リストの欠点 探索が遅い

用語 データベース レコード フィールド キー 単なるデータの集まり データベースを構成するデータ単位 レコードの構成要素 探索のためのフィールド

手続き型言語の問題点 課題を機能に分けて構成する データの管理が global と local の２つしかない 実世界を構成する仕方は、プログラマーの頭の中にしかなくて、プログラムに書き出されていない

オブジェクト 変数（フィールド）と関数（メソッド）をまとめて現実をモデル化する Global Data は使わない オブジェクトが他のオブジェクトの関数を呼ぶ（メーセージを送る）ことでプログラムが進行する

クラス オブジェクトの仕様書 オブジェクトはクラスを実体化(instantiate)したもの(instance) コンストラクタというメソッドがオブジェクトを生成する時に初期化を行なう public と private の宣言でアクセスを制御する 継承(inheritance)と多形性(polymorphism)

演習問題 Private変数に外部からアクセスすると、どのようなエラーが起こるか(p.14) 等値演算子 == と　equals() の違いを説明する例題を作れ(pp.19-20) array.java の内容を整数から文字列に変更せよ(pp.35-36)