酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2007年6月12日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2007/index.html

アルゴリズムとデータ構造基礎 オブジェクト指向の概念とJava言語 計算量の概念とO記法 オブジェクト指向 = Object Oriented Java言語のOO的なところの概説 計算量の概念とO記法 空間計算量と時間計算量 O記法

オブジェクト指向(OO)の概念 オブジェクトを基本にとらえようとする考え オブジェクト間はメッセージパッシング 従来の考えとちょっと違う オブジェクトの中身をいぢるのはオブジェクト自身 メソッドが内蔵されている 従来の考えとちょっと違う メソッドがオブジェクトに内蔵されてるとか クラスが継承できるとか いろいろありますね…

オブジェクトとクラス オブジェクト＝もの クラスとは？ メソッドとは？ 実体のあるものすべてオブジェクト 設計図のようなもの 型のようなものだけど型ではない メソッドを含むこともできる メソッドとは？ オブジェクトへの操作を定義したもの オブジェクトへメッセージが送られたとき使われる

この講義の受講生だけでも９０人いたりするわけで… 簡単な例 クラス: 人間 この講義の受講生だけでも９０人いたりするわけで… 財布＋お金 お金の使途 　教科書　 学習方法 Aさん 財布＋お金 お金の使途 　教科書　 学習方法 Bさん 財布＋お金 お金の使途 　教科書　 学習方法 Zzさん ・・・

OOの概念とJava言語 オブジェクトはクラスのインスタンス メッセージを渡すこと＝関数を呼ぶこと 継承、インターフェース 例えば、newすればインスタンスは生成できる メッセージを渡すこと＝関数を呼ぶこと 渡したいメッセージは引数 受け取りたいメッセージは戻り値 継承、インターフェース

継承(inheritance) 基底クラスの構成要素をそのままに、拡張する仕組み。 Javaではextendsにより継承 継承の結果できたクラス＝派生クラス class baseClass { void methodBase(){ // 何らかの処理１ } class inheritedClass extends baseClass { void methodInherited(){ // 何らかの処理２

静的束縛と動的束縛 オーバーライド 隠蔽 動的束縛 基底クラスで定義されるメソッドを派生クラスで再定義すること 基底クラスのstaticメソッドを派生クラスのstaticメソッドでオーバーライドすること 隠蔽は静的束縛が適用される 動的束縛 クラス構成要素を呼び出す際に決定 オブジェクト変数に代入されたオブジェクトにより呼ばれる構成要素が決まる

継承とオーバーライド class baseClass { // 基底クラス void methodA(int i){ // 派生クラスによりオーバーライドされる int x = i * 1000; System.out.println(x); } void methodB(int i){ // 派生クラスに継承される int x = i + 1000; class inheritedClass extends baseClass { // 派生クラス void methodA(int i){ // オーバーライドします int x = i * 10; System.out.println(x); } public static void main(String[ ] args) { inheritedClass objectInherited = new inheritedClass( ); objectInherited.methodA(10); // 100 を表示 objectInherited.methodB(10); // 1010 を表示

静的束縛 class baseClass { // 基底クラス static void methodA(int i){ // クラスメソッド int x = i * 1000; // プログラムとともに存在 System.out.println(x); } static void methodB(int i){ // クラスメソッド int x = i + 1000; class inheritedClass extends baseClass { // 派生クラス int x = i * 10; // プログラムとともに存在 System.out.println(x); } public static void main(String[ ] args) { baseClass certainObject = new inheritedClass( ); certainObject.methodA(10); // 10000を表示 certainObject.methodB(10); // 1010を表示

動的束縛 class baseClass { // 基底クラス void methodA(int i){ // インスタンスメソッド int x = i * 1000; // 　　newしたときに生成 System.out.println(x); } void methodB(int i){ // インスタンスメソッド int x = i + 1000; class inheritedClass extends baseClass { // 派生クラス int x = i * 10; // 　　newしたときに生成 System.out.println(x); } public static void main(String[ ] args) { baseClass certainObject = new inheritedClass( ); certainObject.methodA(10); // 100を表示 certainObject.methodB(10); // 1010を表示

計算量の概念（7ページ 1.2節） アルゴリズムの性能を示す指標 大きな問題が少ない計算量で解ければ優秀 時間計算量 空間計算量 計算量の概念（7ページ　1.2節） アルゴリズムの性能を示す指標 時間計算量 (文字通り)計算に要する時間 空間計算量 どれくらいの作業領域を必要とするかを表す 大きな問題が少ない計算量で解ければ優秀 漸近的に表現したものがO記法 計算量を定式化したとき、計算量に最も大きな影響を及ぼす項をとりだしたもの。

O記法 漸近的な振る舞いを表す 項の形で大きく２つに分けられる（問題:n） 定数項は無視 係数は１ 一般には最も影響力の強い項のみで表す 指数関数　　 kn

O(n)

O(n2)

O(en)

O(n log n)

演習課題 アルゴリズムとデータ構造の概念を述べよ。 オブジェクト指向の概念を述べよ。 アルゴリズム＋データ構造＝プログラム　は不可 オブジェクト指向の概念を述べよ。 O(n), O(n2), O(2n), O（n log n)を性能の良い順に並べよ。 計算量が指数関数となるときの問題点を挙げよ