このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
アルゴリズムはコンピュータとは独立に考えられ、進歩してきました。 古くて有名なアルゴリズムには、ユークリッドの互除法やエラトステネスの 篩がありますが、いずれも紀元前3世紀頃に作られました。 数学においては、具体的な存在定理や、構成法などとして扱われてきていま した。 また、ギリシャの三大作図問題と呼ばれる、のちにアルゴリズムが存在しな いことが示されるような問題も、紀元前5世紀頃から考えられてきました。 このようにアルゴリズムは、人間が実施するというモデルで古くから考えら れてきました。
一方、ブール代数を基礎として作られたコンピュータは20世紀になってから 誕生しました。 これは、ゲーデルの不完全性定理における証明のモデルの整理により生まれ た計算のモデルが元となっています。
アルゴリズムの研究は数学の知識が重要であり、特に、アルゴリズムが正常 に動くことを示すには、通常は数学で証明します。
しかし、一方で、コンピュータのプログラムを作成する上で、アルゴリズム の学習は必要です。 特に、一般的な情報処理においては、定形のパターンが多く用いられるため、 特定のアルゴリズムを学ぶことで、プログラミング能力が高まります。
この授業では、基本的なデータ構造である木構造と、それに伴うアルゴリズ ムを学びます。 単純な情報処理はほぼ木構造で解決できます。
オブジェクト指向の有り難味は、大きなプログラムを作るときとか、複数人 でプログラムを作るときに、よく感じることができます。 したがって、大学で学ぶ小さなプログラム演習では、冗長で面倒な面が強調 されて、メリットをつかみ辛いかと思います。 したがって、職業プログラマーを目指すには必須の技術ではありますが、大 学で体得するには、努力が必要です。
また、オブジェクト指向とはプログラミングのスタイルであるとともに、プ ログラミング言語が提供する環境であったりもします。 しかも、この二つは厳密には一致せず、熟練した人が理性的にプログラムを 使用すると効果が高くなります。 扱う人の頭の中には漠然と「オブジェクト」の定義がありますが、実際のプロ グラムではプログラミング言語の特性を駆使していて、「オブジェクト」と いう概念を越えた手法もよく使います。 そのせいか、どうかはわかりませんが、多くのオブジェクト指向の書籍におい て、明確に「オブジェクト」を定義しているものを見たことがありません． 著者も「オブジェクト」を明確に定義することができません。
オブジェクト指向という概念の集まりの中で、もっとも重要だと思うのは カプセル化だと思います。 これは、大雑把に言うと、プログラムを全部読まないための技術です。メソッ ドの名前をわかりやすくし、さらに入力と出力の型のみを公開する代わりに、 メソッドの中身を隠蔽します。 特に、メソッド名のうち set や get というメソッド名は重要です。 これは、値を入れる、出すということで、変数と同じ役割になります。 これを用いると、すべての変数を隠蔽することができます。
この概念をさらに拡張したのがユニットテストです。 テストファーストという、プログラム作成技術があります。 これは、プログラムを作成する際に、メソッドの入出力の例を用いた自動テス トプログラムを先に作り、次にそのテストを通るようにプログラムを作成す る技術です。 プログラムテストの区分法はいくつかありますが、オブジェクト指向の場合、 クラスごとに、単なるメソッド一つずつのテストを行うユニットテストが親 和性が高いです。 Java には JUnit というユニットパッケージが存在しており、特に Eclipse には標準で内蔵されているので、チームにおけるテスト環境の共通化にも寄 与します。
Oracle社がJava言語のライセンスを大幅に変更し、また頻繁なアップデート をするようになりました。 2020年4月現在Java14が出ています。
Java8 までのソースコードと Java9 以降のソースコードは互換性が無く、 java 9以降は文法の変更、大幅な機能の削除や追加が行われています。 動向は、様々な機関でまとめられています。 (例: 内閣官房情報通信技術（ＩＴ）総合戦略室 Java のサポートポリシー変更等に関する技術レポート 2018 年（平成 30）年 5 月 15 日 )
公式には Java8 の商用ライセンスは 2019年1月に切れたことになっていますが、 Java8を使用する環境は2025年までサポートされる予定になっています。
そのため、本講義では半年ごとに変わっていき、半年ごとにライセンスの切 れる最新の Javaではなく、当面使用可能な Java8 を使います。 レポート課題では、Java8 以降で廃止されてしまった、 JavaFX を使用しても 構いません。 また、既に過去の資産と見なされているかも知れませんが、開発環境として Eclipse を使用します。 講義で JavaCC を使用する際に、NetBeans や IntelliJ IDEAより使い勝手 が良いです。
オブジェクト指向プログラミングでは、プログラムはいくつかの部分に分割 されます。 特に Java では、すべてのプログラムはクラスに分割されます。 クラスを作成すると、そのクラスのインスタンス（オブジェクト）を作成し、 そのインスタンスに対してメソッドを呼び出して情報処理を行います。
Java で、クラスライブラリを使用したプログラムは既に習っていると思い ます。クラス A を使用するプログラムは次のような使い方をします。
class Main {
public static void main(String[] arg){
A a = new A();
a.set(2);
System.out.println(a.get(());
}
}
クラスを使う場合、通常は、変数を作成し、 コンストラクタで生成したオ ブジェクトを参照させます。 その後、変数に対して、様々なメソッドを適用して、情報処理を行います。 メソッド名がわかりやすい英語の動詞になっていれば、変数名が主語で、メ ソッド名が動詞、引数が目的語の英語の文章のように読めます。 このように、クラスを使う場合、意図した処理を英語で記述したようなプロ グラムになります。 つまり、巧みな処理ではなく、よく使われる英単語を並べたようなプログラ ムになります。
しかし、アルゴリズムというのは、目的の処理に対して特別な名前がつくほどの複 雑なデータの処理をするものなので、オブジェクト指向の感覚からすればカ プセル化して見えなくすべき部分になります。
したがって、アルゴリズムはクラスを使うときに活用するのではなく、クラ スを作る部分で活用します。 模式的なプログラムを示すと次のようになります。
// ここでの Object はデータ型の代表例
public class A {
private 内部データ宣言
public A(){ // コンストラクタの処理
}
public void set(Object x){ //データの代入
}
public Object get(){ // データの取り出し
// 内部データを処理するアルゴリズム
}
}
なお、引数なしのコンストラクタのみが必要で、何も手続きを必要としない場 合、コンストラクタの定義自体を省略することができます。
あるクラスの性質を引き継いだ子クラスを作ることを継承と言い ます。 直接的にはソフトウェアの再利用、共通化の意味がありますが、プログラミン グ技術としてはさらに深い意味があります。
まずは単純な継承を示します。 親クラス(スーパークラス)Aを継承する子クラスBは次のように定義します。
public class A {
public String get(){
return "A";
}
}
public class B extends A {
}
このように定義すると、クラスBでも get メソッドを使うことができます。 このような使い方では単純にクラスAのプログラムをクラスBで使用するだけ です。
しかし、クラスBで get メソッドを記述すると、大きな広がりが生じます。 次のプログラムを考えます。
public class A {
public String get(){
return "I am A";
}
}
public class B extends A {
@Override
public String get(){
return "I am B";
}
}
この場合、クラスBのオブジェクトでは、クラスAのgetのプログラムは使用 されません。 親クラスと同一のシグネチャのメソッドを子クラスに実装することを オーバーライドすると言います。
さて、オブジェクトの変数型を考えます。 クラスBのオブジェクトを参照する変数はBで宣言しても、実は親クラスの型 でも参照できます。 但し、親クラスの変数でメソッドを参照しても、子クラスのプログラムが使 用されます。
A x = new A();
System.out.println(x.get()); // I am A
B y = new B();
System.out.println(y.get()); // I am B
A z = new B();
System.out.println(z.get()); // I am B
親クラスは必ず継承され、メソッドが必ずオーバーライドされるとします。 すると、親クラスでのメソッドは、シグネチャは必要ですが、プログラムは 必要ありません。 この時、親クラスでメソッドを abstract 宣言をすることで、プログラムを 省略できます。これを抽象メソッドと言います。 但し、一つでも abstract なメソッドを持っているクラスは クラス宣言でも abstract 宣言をしなければなりません。 これを抽象クラスと言います。
public abstract class A {
public abstract String get();
}
public class B extends A {
@Override
public String get(){
return "I am B";
}
}
abstract 宣言したクラスのオブジェクトは作れません。但し、継承目的の コンストラクタを記述することはできます。
Java では、さらに、abstract メソッドのみの抽象クラスを宣言する interface 宣言があります。この場合、継承は extends ではなく、 implements になります。 宣言時に public abstract を省略することができます。
public interface A {
String get();
}
public class B implements A {
@Override
public String get(){
return "I am B";
}
}
著者は、これは型と実装を分離する発明だと思っています。 継承関係を持つようなクラスを作る場合、必ず interface を作成しておくと、 後々、実装の構造を変えたりするとき、クラスを使用しているプログラムの 変更を最小限にすることができます(実装例略)。
複数の子クラスでメソッドをオーバライドすると、オブジェクトのクラスご とに処理を変えることができます。 これをポリモーフィズムと言います。
public interface A {
String get();
}
public class B implements A {
@Override
public String get(){
return "I am B";
}
}
public class C implements A {
@Override
public String get(){
return "I am C";
}
}
このようなクラス定義に対して、B,C のオブジェクトは、それぞれのクラス の振る舞いをします。
A x = new B();
System.out.println(x.get()); // I am B
A y = new C();
System.out.println(y.get()); // I am C
これは、オブジェクトごとの処理をするのに、オブジェクトがどれかを判定 する事無しに手続きを記述することができます。 これはクラスの型を switch 文で判定して処理するようなプログラムを置き 換えることができます。
特定の処理に対して、オブジェクト指向のプログラミングテクニックを使用 して解決する手法をデザインパターンと言います。 Gang of Four と呼ばれる4人がまとめたものが有名です。 ここでは、良く使うデザインパターンを示します。
オブジェクトのコピーを作るために、オブジェクトを引数とするコンストラ クタをコピーコンストラクタと言います。
public class A {
private int x;
public A(){}
public A(A a){
x=a.x;
}
public void set(int x){
this.x = x;
}
public int get(){
return x;
}
}
なお、 Java ではオブジェクトをコピーする方法として、コピーコンストラ タの他に clone メソッドがあります。 用法は java.lang.Object の clone メソッドを参照してください。
GUIのウィンドウなど、常に唯一性を保ちたいオブジェクトを維持したいと きに使います。 但し、グローバル変数のように振る舞うので、最後の手段として取っておく べき手法でしょう。 クラス変数という、オブジェクトインスタンスではなく、クラスに所属する 変数を使います。Java だと static 宣言をします。
public class A {
private static A instance;
private A(){}
public static A getInstance(){
if(instance == null){
instance = new A();
}
return instance;
}
}
テンプレートは共通の親クラスを持つ子クラスにおいて、 親クラスが文字列を返すメソッド中に abstract なメソッドを用い、子クラ スで abstract なメソッドを実装することで、文字列の書式をコントロール するデザインパターンです。
interface Money {}
public abstract class AbstractMoney implements Money{
private double value;
protected AbstractMoney(double value){
this.value = value;
}
protected abstract String prefix();
protected abstract String postfix();
@Override
public String toString(){
return prefix()+value+postfix();
}
}
public class Yen extends AbstractMoney {
public Yen(double value){
super(value);
}
@Override
protected String prefix(){
return "";
}
@Override
protected String postfix(){
return "円";
}
}
public class Dollar extends AbstractMoney {
public Dollar(double value){
super(value);
}
@Override
protected String prefix(){
return "$";
}
@Override
protected String postfix(){
return "";
}
}
オブジェクト指向のプログラミングを行うには クラスの作成を参照してく ださい。
Java の変数の型には大きく分けて、プリミティヴ型と参照型があります。
プリミティヴ型は int, short, long, float, double, char, byte. boolean です。 これらは、変数宣言すると、名前に対応したデータ領域が確保され、データ が保存できるようになります。 0, 1.1, 'a', true などのリテラル（定数）が定義できます。
参照型には配列やオブジェクトなどがあります。 これらは、変数宣言してもデータ領域は確保されません。 別の方法でデータ領域を確保する必要があります。 そして、変数はその位置の情報である参照を格納します。 参照型のオブジェクトは new 演算子で生成される他、clone メソッドやファ クトリメソッドなどでも生成されます。
配列は { } の中括弧でくくった表現のリテラルが使えます。但し、リテラ ルで生成する配列の型が明らかでないときは、new 演算子を使用する構文を 使う必要があります。
int[] x = {1, 2, 3};
Number[] y = new Number[]{new Integer(1), new Double(2.3)};
また、java.lang.String のリテラルとして、 " " でくくった文字列が使え ます。
String x = "abc";
この他に Java8 から java.util.function パッケージ中のクラスのリテラ ルとしてラムダ式が使えるようになりましたが、これは その章 に譲ります。
Java には豊富なクラスメソッドが付属してきてます。この中には通常のプ ログラミングにおいて多用するものもあれば、特定の目的にしか使用しない ものもあります。 また、使用の仕方も、単にインスタンスを生成して、メソッドを呼ぶという 方法の他にも色々あります。
Object クラスはルートクラスとも言い、全てのクラスの親クラスとなるク ラスです。つまり、 extends で親クラスを指定しないクラス宣言では java.lang.Object が親クラスとして指定されていると考えます。
public class A {
}
// これと下記はほぼ等価
public class A extends java.lang.Object {
public A(){
super();
}
}
様々なメソッドが定義されていますが、重要なのは toString と equals で す。この二つだけはよく読んでおく必要があります。 この他、clone と hashCode なども使う機会があるかもしれません。
プリミティヴ型のそれぞれの変数型に対して、それを参照型のオブジェクト として使用するためのクラスが用意されています。 これをラッパークラスと言います。 float, double など通常の型は頭文字を大文字にした java.lang.Float, java.lang.Double などが対応します。int 型だけは java.lang.Integer が 対応します。 ラッパークラスの役割は、基本的には値の格納と取り出しだけです。その他 に、文字列からその基本型の値への変換などもできます。 但し、演算はできませんので、必要な演算はプリミティヴ型に戻してから行 う必要があります。
Integer x = new Integer(1);
Integer y = new Integer(2);
Integer z = new Integer(x.intValue() + y.intValue());
ところが、Java5 から、ラッパークラスとプリミティヴ型を文脈によって自 動変換するオートボクシング、オートアンボクシングという機能が加わりま した。下記のプログラムは上記のプログラムに自動変換されます。 つまり、演算ができるようになったのではなく、暗黙に変換プログラムが追 加されるだけなので、効率が良くなったわけではありません。
Integer x = 1;
Integer y = 2;
Integer z = x + y;
比較には2通りあります。 一つは等価性の検査です。
== 演算子はプリミティヴ型では等しいかどうかを検査しますが、参照型で は等価性ではなく、同一のメモリー領域かの検査になります。
「同じ文字列か？」など、オブジェクトの等価性を調べるには equals メソッドを 使います。 equals メソッドを定義する場合、 hashCode メソッドと整合性を取る必要があります。 つまり、a.equals(b) が true の時、 a.hashCode() と b.hashCode() が等 しい必要があります。
次に、順序を定める場合、 java.lang.Comparable インターフェイスを実装 し、 compareTo メソッドを使用します。 compareTo メソッドのマニュアルにありますが、 equals メソッドと整合性 を取る必要があります。 つまり、 a.compareTo(b) が 0 の時、かつその場合に限って a.equals(b) が true である必要があります。
基本的に代入や関数呼び出しなどにおいて、型は一致しているのが前提です。
プリミティヴ型においては、精度が落ちるような代入においてはエラーが出 ます。 その場合でも、キャストをすれば、丸めなどが行われ適切に代入が行われます。 なお、小数点付きのリテラルは double 型として解釈されます。
int a1 = 1.1; // エラー
int a2 = (int) 1.1; // 切り捨てが行われて 1 が代入される
double b = 1; // 1.0 に自動的に変換される
float c1 = 1.1; // 1.1 は double 型なので精度が落ちると解釈されエラー
float c2 = (float) 1.1; // float 型に変換され代入される
float c3 = 1.1f; //各プリミティヴ型には専用のリテラルの書式がある
親クラス、実装しているインターフェイスの型で宣言した変数から参照でき ます。 従って、ルートクラスである java.lang.Object 型の変数は全てのオブジェ クトを参照できます。 但し、宣言されている型で定義されているメソッドしか呼び出しができませ ん。
Java1.4 までは、オブジェクトの集まりのクラス(java.util.ArrayList な ど)では、要素は java.lang.Object 型で返されました。 そのため、元のクラスにダウンキャストするのが常套手段でし た。但し、ダウンキャストにおける型違いのミスは実行時にしか分からない という問題がありました。 しかし、Java5 から Generics が導入され、ダウンキャストをするとワーニ ングが出るようになりました。
//Java1.4 まで
Integer x = new Integer(1);
List l = new ArrayList();
l.add(x);
Integer y = (Integer) l.get(0); // ダウンキャスト
//Java5以降
Integer x = 1; // オートボクシング
List<Integer> l = new ArrayList<Integer>(); // Generics
l.add(x);
Integer y = l.get(0);
Java5 から導入された Generics では、型変換は行われません。つまり、型 があってなければエラーとなります。 但し、Generics にはワイルドカード指定ができるので、異なる型に対応で きます。
Number x = new Integer(1); //これは Ok
List<Number> ln = new ArrayList<Integer>(); //これはエラー
List<? extends Number> ln2 = new ArrayList<Integer>(); //これはOk
なお、Java8 までは、配列変数の宣言では Generics を指定できますが、 new 演算子で配列を作る際にはできません。 従って、ダウンキャストをする必要があります。 この場合、警告を消すには@SuppressWarnings("unchecked")宣言をする必要があります。
List<Integer>[] la;
la = new List<Integer>[1]; // NG
la = (List<Integer>[]) new List[1]; // Ok ダウンキャストの警告が出る
Java8 では、マルチコアに対応するため、java.util.stream.Stream クラス などを導入しました。 Strem はデータ列に対して関数を適用するためのデータ構造です。 これを実現するために FunctionalInterface という概念が導入されました。 これは、一つだけ abstract なメソッドを持つインターフェイスを指します。 Java8 の型推論は、変数宣言や引数宣言に対して、オブジェクトの型を合わ せるものです。 java.util.function パッケージの中には、様々な引数のタイプに対する FunctionalInterface が定義されています。
ラムダ式