ソートとは ソートとは，複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の2つがあります。 昇順：小さいものから大きなものへ 降順：大きなものから小さなものへ   並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所（文字列）による並べ替えが行われます。 ソートアルゴリズム ソートの処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。 ソートを行うアルゴリズムの例として次のものが挙げられます。 基本形 基本交換法：バブルソート 基本選択法：直接選択法 基本挿入法 応用形 改良交換法：クイックソート 改良選択法：ヒープソート 改良挿入法：シェルソート バブルソート バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がと遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある） バブルソートサンプル final int NUMBER_OF_RANDOM_DATA = 500; final String DATA_FILE_NAME = “RandomData.txt”; final int DIAMITER = 5; ArrayList nums = new ArrayList(); int i = 0; // ソート回数。drawする度にカウントアップ void setup(){ //ランダムなデータの読み込み loadData(); //ディスプレイウインドウの設定 size(500,500); […]

再帰とは 再帰（Recursion）とは，再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは，自分自身の定義の中に，自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。 階乗 整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。 n! = n × (n-1) × (n-2) × … × 2 × 1 この式を再帰的定義に書き換えると，次のようになります。 n! = n × (n-1)! (ただし，0!=1) 次の階乗のsketch、Factorial.pdeは10の階乗を行う例 繰り返し構文を使ったメソッド　factorial_for 再帰するメソッド　factorial_recursive // 繰り返し構文を用いたメソッド long factorial_for(long i){ if(i < 0){ println(“Error! Invarid input.<using for>”); return -1; } else { long result = 1; for (int j = 1; j <= […]

キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。 キュー キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける) コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。 データを追加する操作をエンキュー(enqueue)。データを取り出す操作をデキュー(dequeue)という。 スタック スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。 積ん読 (本を重ねて積んでいくと上からしか取れない) コンピューターで割込みやサブルーチンを支援するために極めて有用である     スタックにデータを入れる操作をプッシュ(push)という。スタックからデータを取り出す操作をポップ(pop)という。 キューとスタックの実装 オブジェクトの後入れ先出し（LIFO）スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し（FIFO）を表す待ち行列（キュー）は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。 一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。 import java.util.*; String[] item = {“Apple”, “Banana”, “Cocoa”}; Queue q = new LinkedList(); Stack s = new Stack(); for(String i: item) […]

サーチ（Search）とは，複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。 サーチのアルゴリズムには，ランダムなデータを取り扱えるものと，ソート済みのデータを取り扱うものとがあります。 リストサーチ（list search） データのリスト構造とはA, B, C, ……のように，データが次々と連続している構造のことを言います。代表例は配列です。 そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを，ここではリストサーチと呼びます。 探索のアルゴリズム 線形探索 二分探索 ハッシュ法 線形探索 線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。 目的の要素であるという判定は比較によって行います。 アルゴリズム分析 リストの先頭から要素を取り出す 取り出した要素の値と探したい要素の値を比較する 一致すれば探索完了 一致しなければ 1. へ戻り次の要素を取り出す かなりシンプルで理解し易いアルゴリズムです。 サンプルコード 線形探索のアルゴリズムを実装したsketchは次のとおりです。 線形探索のsketch。LinearSearch.pde // 線形探索 Linear Search // 番兵無し No Sentinel final int NUMBER_OF_RANDOM_DATA = 500; final String DATA_FILE_NAME = “RandomData.txt”; final int DIAMITER = 5; final int SEARCHING_VALUE = […]

データ構造とは データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 配列 配列（はいれつ）は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め，要素を区別します。配列によってまとめられた，一つひとつの変数を要素（ようそ）と呼びます。要素を区別するために添えた数字を添字（そえじ）と呼びます。 配列は大変シンプルで，コレクションクラスに比較すると必要とするメモリ量が少なく，アクセスが高速なことがメリットです。データを単純に格納して，順番に参照する程度の用途であれば，コレクションクラスに比較して配列のほうが有利です。 最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し，配列の添字を明記して要素に値を代入し，添字を指定して要素の値を呼び出します。 String names[] = {“Tim Bray”,        // 0番目の要素 “Brian Kernighan”, // 1番目の要素 “Jon Bentley”,     // 2番目の要素 “Karl Fogel”};     // 3番目の要素 for(int i = 0; i < names.length; ++i){ println(names[i]); }   ランダムな整数データを500個もつデータファイルRandomData.txtを作成 int NUMBER_OF_RANDOM_DATA = 500; int MIN_SIZE_OF_RANDOM_DATA = 1; int MAX_SIZE_OF_RANDOM_DATA = 500; String DATA_FILE_NAME = […]

アルゴリズムとは アルゴリズム（英: algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法（さんぽう）」と訳されることもある。 基本的なアルゴリズム 順次 条件判定と分岐 (if, switch) 繰り返し (while, for)   順次 順次実行構造は，上に書かれた命令が先に実行され，下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。 典型的な順次実行の例として，GSWPよりサンプルコードを引用します。 // Example 03-13 from “Getting Started with Processing” // by Reas & Fry. O’Reilly / Make 2010 size(480, 120); smooth(); strokeWeight(12); strokeJoin(ROUND); // Round the stroke corners rect(40, 25, 70, 70); strokeJoin(BEVEL); // Bevel the stroke corners rect(140, 25, 70, […]

Javaのインストール MacBookでのJavaのインストール方法 http://java.com/ja/download/help/mac_install.xml MacにJavaをインストールするには、次の手順に従います。 jre-7u6-macosx-x64.dmgファイルをダウンロードします。ファイルをダウンロードする前に、使用許諾契約の内容を確認し、同意します。 .dmgファイルをダブルクリックして起動します パッケージ・アイコンをダブルクリックし、インストール・ウィザードを起動します 結果確認 chen-no-MacBook-Air:~ chen$ java -version java version “1.8.0_11” Java(TM) SE Runtime Environment (build 1.8.0_11-b12) Java HotSpot(TM) 64-Bit Server VM (build 25.11-b03, mixed mode)   Windows７でのJavaのインストール方法 http://java.com/ja/download/help/windows_manual_download.xml 手動ダウンロード・ページに移動します 「Windows Online」をクリックします ダウンロードするファイルを実行するか保存するかを尋ねる「ファイルのダウンロード」ダイアログ・ボックスが表示されます インストーラを実行するには、「実行」をクリックします。 ファイルを保存して後でインストールするには、「保存」をクリックします。 保存先として、ローカル・システムのフォルダを選択します。 ヒント: デスクトップなどのように、コンピュータ上のわかりやすい場所にファイルを保存してください。 保存したファイルをダブル・クリックし、インストールを開始します。 インストールが始まります。「Install (インストール)」ボタンをクリックして使用許諾契約の条項に同意し、インストールを続行します。 Javaアプリケーションのサンプル（HelloWorld） Java の　Hello World class Hello { public static void […]

プログラミング言語   コンピュータ上で動くプログラムには様々な目的のために，様々な動きをするものがあります．その動きによって，プログラムの書きやすい書き方が異なります．そのために，これまで様々なプログラム言語が考え出されてきました． プログラム言語の分類 プログラム言語を書き方の種類で分類すると，手続き型言語，関数型言語，論理型言語， オブジェクト指向言語に分けられます． 手続き型言語は，命令文を実行する順に並べます．その順を変えるには繰り返し文や分岐文などの制御構造を利用します．手続き型言語には FORTRAN や COBOL，PASCAL，C などがあります． 関数型言語は，関数を定義することで動作を指示するもので，LISP や ML が代表的な例です． 論理型言語は，形式論理，数理論理に基づいたプログラム言語で，事実を定義することである問題を解決することができます．論理型言語には Prolog などがあります． オブジェクト指向言語は，データとそのデータに対する操作をまとめたオブジェクトの性質を定義することで動作を指示します．オブジェクト指向言語には Smalltalk，C++, Objective-C，Java などがあります． 上記の高水準プログラム言語を実行するためには，アセンブリ言語で書かれたプログラムを実行するためにアセンブラで機械語に変換するように，機械語に変換しなければなりません．この変換作業を行うプログラムを言語処理系と呼びます．代表的な言語処理系にはコンパイラとインタプリタがあります． コンパイラ コンパイラは高水準言語を機械語に変換して出力する言語処理系です．実際にはコンパイラはアセンブラ言語までの変換を行います．その後アセンブラによって機械語への変換を行います．また，アセンブラが作成するのはオブジェクトプログラムと呼ぶもので，実際に実行するためには実行時ライブラリと結合する必要があります．この結合にはリンカを利用します．市販されているプログラム開発環境では，コンパイラ，アセンブラ，リンカを意識することなく利用できるようになっています． インタプリタ インタプリタは高水準プログラム言語で書かれたプログラムを順次解釈しながら実行していきます．コンパイラの場合，実行するときには機械語にすべて変換してから実行するため，実行速度が速くなるメリットがあります．一方，プログラムを作るたびにコンパイラを使って変換しなければならないという面倒もあります． Javaとは ◆Sun が開発したプログラミング言語 Java は、1995年頃に Sun Microsystems 社によって発表されたプログラミング言語です。プログラミング言語には他に BASIC、COBOL、FORTLAN、LISP、C、C++、JavaScript、Perl、PHP、Ruby などがあります。 ◆オブジェクト指向プログラミングが可能 Java は、オブジェクト指向 的なプログラミングが可能な言語です。オブジェクト指向とは継承機能を持つクラスに基づいてインスタンスを生成することで記述性を高める・・・と言っても 説明しきれないので、どこか別の場所で詳しく説明します。オブジェクト指向プログラミング言語には他に、Smalltalk、C++、C# などがあります。 ◆ 中間コードへのコンパイル言語 プログラミング言語は、プログラムを逐次解析しながら実行する インタープリタ型言語 と、あらかじめマシン語コードに変換しておく コンパイル型言語 に大別されます。Java は基本的にはコンパイル型言語ですが、CPU に依存したマシンコードではなく、CPU に依存しない 中間コード にコンパイルするのが特徴です。 […]

授業概要 　ソートとコレクションを中心にアルゴリズムとデータ構造に関する基本を学習する。 Java言語によるプログラミング技術の基本事項を習得する。 特にアルゴリズムとデータ構造の理解を中心に、講義および演習を行う。 授業の到達目標 ・オブジェクト指向言語の概念を理解するとともに、Javaを用いて課題を解決するスキルを身につける。 ・アプリケーションの開発に必要な概念を理解するとともに、Java言語を用いて実用的なWebアプリケーションの開発が行えるようになる。 事前・事後学習の内容 予習としてMyWasedaに掲載するレジュメの事前読了を求めることがあります。各回の予習には90分～120分かかると想定されます。 授業計画 1: 本講義の目的と進め方について説明する。最終的に作成するアプリケーションの実例を説明する。 2: 基本概念を理解する。Javaのインストールからコマンドライン実行の方法を学ぶ。 3: 基本的なアルゴリズムを学ぶ。 4: 基本的なデータ構造を学ぶ。 5: 探索アルゴリズムを学ぶ。 6: スタックとキューを学ぶ。 7: 再帰的アルゴリズムを学ぶ。 8: ソートを理解する。 9: 集合を学ぶ。 10: 文字列探索を学ぶ 11: 線形リストを学ぶ 12: 木構造を学ぶ 13: Webアプリケーション作成に必要な概念を理解する 14: RESTアーキテクチャとJSON オブジェクトを学ぶ 15: Webアプリケーション作成（コーディング・テスト、デバッグ、仕上げ） 教科書 「明解 Javaによるアルゴリズムとデータ構造」 柴田 望洋 (著)ソフトバンククリエイティブ (2007/11/7) 参考文献 「明解Java　入門編」 柴田 望洋 (著)ソフトバンククリエイティブ(2007/8/8) 「Javaによるはじめてのアルゴリズム入門」（河西朝雄著、技術評論社、2001年） 成績評価方法 […]

「明解 Javaによるアルゴリズムとデータ構造」  柴田 望洋 (著)ソフトバンククリエイティブ (2007/11/7) 「明解Java　入門編」  柴田 望洋 (著)ソフトバンククリエイティブ(2007/8/8) http://bohyoh.com/Java/ 「Javaによるはじめてのアルゴリズム入門」（河西朝雄著、技術評論社、2001年） 「標準Javaプログラミングブック」（河西朝雄著、技術評論社、2001年） とほほのJava入門 (http://www.tohoho-web.com/java/index.htm )