コンピュータIIIB（Javaアルゴリズム）第1回

1.1 教員の紹介

名前

小西 善二郎（こにし ぜんじろう）

肩書き

東京女子大学文理学部非常勤講師

連絡先

konishi@cis.twcu.ac.jp

1.2 シラバス

1.2.1 授業の目標・概要

本講義では、Java言語を用いて基本的なアルゴリズムを学ぶ。 再帰、リスト、木などの概念を理解し、整列プログラムを作成することが目標となる。 また、オブジェクト指向プログラミングについても触れる。 Java言語の基礎知識を仮定する。

1.2.2 授業のスケジュール

1. ガイダンス
2. Java言語の復習
3. 再帰（再帰の考え方）
4. 再帰（クイックソート）
5. リスト（リストの操作）
6. リスト（併合整列）
7. 木（木の操作）
8. 木（ヒープソート）
9. オブジェクト（オブジェクトの考え方）
10. オブジェクト（継承（1））
11. オブジェクト（継承（2））
12. より高度な話題

1.2.3 教材（テキスト）

1.2.4 教材（参考書等）

授業内容に応じて参考資料を紹介する。

1.2.5 成績評価の方法と基準

原則として毎回レポート課題を出す。 最後の授業では筆記試験を行う。 レポートの採点結果と試験の得点を総合して成績を決定する。

1.2.6 履修者への要望

レポートはすべて提出すること。

1.2.7 教室外の学習方法

レポート課題に取り組むこと。

1.3 履修者の抽選

コンピュータの台数の関係により、履修希望者が80名を越えた場合は抽選を行います。

1.4 授業の内容

この授業は、Javaの入門程度は理解している人を対象にしています。 プログラミングは初めてという人は履修しないでください。 Javaは知らないがCは知っているという人なら履修しても大丈夫です。

授業のテーマは次の3点です。

• アルゴリズム
• データ構造
• オブジェクト指向プログラミング

整列とは、与えられた数の列を小さい順に並べ替えることです。 整列は、基本的なデータ処理であると同時に、工夫次第では高速処理が可能になります。 この授業では、代表的な整列アルゴリズムと、そこで使われるデータ構造について学びます。

オブジェクト指向プログラミングとは、データ構造を中心にしてプログラムを構成するというプログラミングのことです。 最近のプログラミング言語は、多くはオブジェクト指向の考え方を取り入れています。 この授業では、オブジェクト指向プログラミングの入門的な内容について説明します。

1.5 授業の準備

1.5.1 システムの更新

2007年9月に、情報処理センターのシステムが更新されました。 Mac OS Xであることは変わりませんが、一部のアプリケーションがバージョン・アップしています。

この授業に関係するアプリケーションは次のようなものです。

「 ターミナル 」は、Mac OS Xに付属しているターミナル・ソフトウェアです。 この授業では、「ターミナル」を用いてプログラムを実行します。

Jedit は、アートマン21が開発したテキスト・エディタです。 この授業では、Jeditを用いてプログラムを編集します。

今日は、これらのアプリケーションの使い方を覚えながら、授業の準備をします。

1.5.2 授業用フォルダの作成

この授業では、演習でいくつかのプログラムを作成します。 すでに自分でプログラムを保存している学生もいると思いますので、授業用のフォルダを作り、そこに演習で作ったファイルを置くことにします。

もし、「フォルダ」という言葉を聞いたことがなければ、これを「ディレクトリ」と読み替えてください。 この授業では、フォルダとディレクトリは同義語です。

はじめに、「ターミナル」を起動します。 「ターミナル」を起動するには次のようにします。

1. DockのFinderアイコンをクリックします。
2. サイド・バーの「アプリケーション」をクリックします。
3. アイコン「TWCU」をダブル・クリックします。
4. アイコン「term」をダブル・クリックします。
5. アイコン「Shift_JIS.term」をダブル・クリックします。

次に、授業用のフォルダを作成します。 この作業は一度行えばよいものです。 「ターミナル」で次のように入力してください。

b04a001@AsiaA1:~% mkdir comp3b
b04a001@AsiaA1:~%

1.5.3 Jeditの使い方

続いて、Jeditを起動します。 Jeditを起動するには次のようにします。

1. DockのFinderアイコンをクリックします。
2. サイド・バーの「アプリケーション」をクリックします。
3. アイコン「Jedit X Folder」をダブル・クリックします。
4. アイコン「Jedit X」をダブル・クリックします。

今日は、次のプログラムを実行します。 このプログラムは、"Good afternoon!"と出力するものです。

/*  1*/ class GoodAfternoon {
/*  2*/     public static void main (String[] args) {
/*  3*/         System.out.println("Good afternoon!");
/*  4*/     }
/*  5*/ }

プログラムをファイルに保存するには、次のようにします。

1. プログラムをマウスでドラッグして選択し、メニュー・バーで「編集」→「コピー」とクリックします。
2. Jeditのウィンドウをクリックし、メニュー・バーで「編集」→「ペースト」とクリックします。
3. メニュー・バーで「ファイル」→「別名で保存」とクリックします。
4. 右側の三角ボタンを数回クリックし、ウィンドウを広げます。
5. ホーム・アイコンをクリックし、アイコン「comp3b」をクリックします。
6. 「名前」欄に「 GoodAfternoon.java 」と入力します。
7. エンコーディングを「日本語（Windows, DOS）」、改行タイプを「Unix（LF）」とし、「保存」ボタンをクリックします。

1.5.4 Javaの使い方

プログラムを実行するには、「ターミナル」で次のように入力します。

b04a001@AsiaA1:~% cd comp3b
b04a001@AsiaA1:~/comp3b% javac GoodAfternoon.java
b04a001@AsiaA1:~/comp3b% java GoodAfternoon
Good afternoon!
b04a001@AsiaA1:~/comp3b%

確かに出力されました。

1.6 アンケート1

履修者の予備知識を確認するため、アンケートを行います。 以下の質問に答え、回答をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@cis.twcu.ac.jpなど）とし、メールの宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（9月28日）を明記してください。

1. 100以下の素数（25個）をすべて求めるプログラムが書けるかどうか答えてください。 ここで、素数とは1と自分以外に約数を持たない数のことです。 2, 3, 5などが素数です。 プログラミングの方針はいくつか考えられます。 例えば、2 * 2, 2 * 3, 3 * 3, ... のように掛け算を次々と実行し、それらの計算結果は素数でないという方針ですと、次のようになります。 まず、添字が2から100までの配列要素に1を格納します。

   a[2] = 1; a[3] = 1; ...; a[100] = 1;

   次に、添字が2の倍数である配列要素に0を格納します。

   a[2 * 2] = 0; a[2 * 3] = 0; ...; a[2 * 50] = 0;

   続いて、添字が3の倍数である配列要素に0を格納します。

   a[3 * 2] = 0; a[3 * 3] = 0; ...; a[3 * 33] = 0;

   さらに、添字が4の倍数である配列要素に0を格納します。

   a[4 * 2] = 0; a[4 * 3] = 0; ...; a[4 * 25] = 0;

   この作業を、添字が50の倍数の場合まで行います。 最後に、値が1である配列要素の添字をすべて出力します。
2. 授業内容に関して、何か希望がありましたら答えてください。

1.7 参考文献

• R. Sedgewick: Algorithms in C, Addison-Wesley, 1990. 野下浩平（他訳）『アルゴリズムC』近代科学社、1996.
• 長尾真（他編集）『岩波情報科学辞典』岩波書店、1990.
• The Java Language Specification, http://java.sun.com/docs/books/jls/