データ構造とプログラミング（第１回）大岩元ＴＡ: 武田林太郎ＳＡ: 明石敬教科書 • Robert Lafore 著岩谷宏訳 Java で学ぶアルゴリズムとデータ構造ソフトバンク１９９９年日本のIT人材不足の実態先端 ← 初級 Innovators Early Adopters Early Majority Late majority Laggards 技術レベル先端的研究者高度人材ソフトウェア開発技術者基本情報技術者初級シスアド米国 2.5% 13.5% 34% 34% 16% 日本 0.5% 2.5% 20% 45% 32% 図1 IT人材資源日米比１．２．３．４．５．先端的研究社層が、1桁以上薄い上級技術者（高度人材）も１桁少ない Early Majority（旧１種レベル）も少ない Late majority（旧２種レベル）は人口比に近い情報技術の素人（初級シスアド）は似たり寄ったり表１米国と比較した日本の技術者の現状インド人、中国人IT技術者 • 日本人技術者は年収3-400万円のプログラマーしかいない • インド人、中国人のIT技術者を雇ってみたら、彼らの方が有能で、給料は1/5以下 • 外国人技術者確保が現在の至上命令に • 日本人は仕様を作れない • 外国人は仕様通りしか作れない • 日本語教育が問題 – 岩崎式日本語教育(MISJ)なら400時間の教育で十分可能 ACMプログラミングコンテスト • 過去4回国内予選の優勝校は日本以外 • 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)