algorithm a

アルゴリズム a

Notice for the remote access.

お知らせ

この授業の情報は、Web サイト ( http://ynitta.com/class/ ) と GoogleDrive に置きます。

GoogleDrive には @gm.tsuda.ac.jp のアカウントでアクセスして下さい。当初は@gm.tsuda.ac.jp全員がアクセス可能ですが、ある時点で履修登録者のみに制限します。

pdf形式の資料を配布する際は GoogleDrive 中の pdf/ フォルダに置きます。また、授業中に書き込みを行ったpdf形式のテキストなど、追加の資料は GoogleDrive のhandwritings/ フォルダに置くことがあります。

Web サイト http://ynitta.com/class/ 上の「課題提出Web」などの学内専用ページに学外からアクセスする場合は、 GoogleDrive の passwd.txt に記載されている [Web用] ユーザ名とパスワードを利用して下さい。

algorithm a

[授業内容]

「アルゴリズム」の意味

アルゴリズム ＝ ある問題をコンピュータを用いて効率良く解くうまいやり方、手順。

プログラミングでよく使用される基本的な「アルゴリズム」と「データ構造」について学習します。適切なアルゴリズムとデータ構造を用いて、効率のよいプログラムを作成できるようになることが目標です。

「アルゴリズムa」では、まず、アルゴリズムの性能の基準となる計算量という概念について理解し、次に、基本的なデータ構造について学習します。基本的なデータ構造としては、配列、スタック、連結リスト、木構造などがあります。その後、探索に関する代表的なアルゴリズムをいくつか学習します。

「アルゴリズムa」の学習後、「アルゴリズムb」や「アルゴリズムc」で、整列、バックトラック、動的計画法などの高度なアルゴリズムを学びます。

単なる理論的な説明だけで終わるのではなく、できるだけ実装例(Java 言語で書いたプログラム例)を示す予定です。

[java について]

演習で利用する java 言語処理系は OpenJDK http://jdk.java.net/バージョン11以上を想定しています。

[注意] CPU が Apple M1 (Arm64) の Mac を使っている方は、native対応している Java 処理系を使う方がよいでしょう。
本家 OpenJDK も Azul Zulu (= OpenJDK を Azul がビルドしたバイナリ) も Java 17 (LTS) で Apple M1 (Arm64) Macに対応しています。

それぞれのインストール方法は、以下を参照してください

[エディタについて]

エディタは何をどのように使っても構いません。

ただしVSCode を使用される場合に、package を使用しない Java ファイルを新規に作成するときは次の手順で行うことを(本授業では)強く勧めます。

「ファインダー」を用いて、本授業用のフォルダを作成する。(ここでは ~/Documents/class2024/algoA/ とします)
VSCode を起動する。
画面上のメニューからFile → Open Folder ... → 書類 → class2024 → algoA を選択する。
左のファイルメニューに alogA (= ALGOA) が現れる。

左メニューの algoA (=ALGOA) ファイルから「ファイルを追加」を選んで、ファイルを追加し、名前を*.java を指定する。(たとえば Sample.java)

[cygwin について]

演習では、shellのリダイレクト機能を用いてプログラムにデータを与えることがあります。 Macの場合は標準のshellにその機能がありますが、 Windows の場合は無いので、 cygwin をインストールすることをお勧めします。 cygwinのインストール方法は「 cygwinをゼロからインストールする(ネットワークを便利に使う最小限のパッケージと共に) 」を参考にして下さい。

[授業日程]

講義: 5206
演習: S304ws

09.03 --- 授業説明, アルゴリズムとは、計算量(線形探索を例として), 計算量(二分探索を例として)
09.10 --- 配列
09.17 --- スタック
09.24 --- キュー
10.01 --- 連結リスト, イテレータ
10.08 --- 循環リスト, 双方向リスト
10.15 --- 木構造, 探索(二分探索木), 「課題 9c」の「木にノードを追加する部分」の補足説明
10.22 --- 探索(平衡木), 平衡木資料, 探索(ハッシュ法)
10.29(補講日) ... 授業なし
11.05 --- 筆記試験
11.12(休講日) ... 授業なし

教科書

「javaプログラマのためのアルゴリズムとデータ構造」
近藤嘉雪　著、ソフトバンクパブリッシング、2835円、
ISBN10: 4-7973-6243-X
ISBN13: 978-4797362435

次のURLにある情報も参照して下さい。

http://ynitta.com/class/algoA/

出席状況:

出席簿(数字のみ:小テスト, b:確認テスト, e:演習)
出席簿に関するメモ

課題提出状況

課題提出Web
課題提出に関するメモ

資料

参考書

アルゴリズムに関する本は、たくさん出版されています。プログラミング言語を Java に限定するとなかなか選択肢は少なくなってしまいますが、アルゴリズムそのものを図解・説明している本や、 C (C++) の簡略コードでプログラムを記述している本は大変参考になると思います。いくつか例を挙げておきます。「プログラミングコンテストチャレンジブック [第2版] 」(通称: 蟻本)は名著だと思います。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
米田 優峻 (著)
出版社: 技術評論社 (2021/12/25)
発売日: 2021/12/25
ISBN-10: 4297125218
ISBN-13: 978-4297125219

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
石田 保輝 (著), 宮崎 修一  (著)
出版社: 翔泳社 (2017/6/6)
発売日: 2017/6/6
ISBN-10: 4798149772
ISBN-13: 978-4798149776

新・明解Javaで学ぶアルゴリズムとデータ構造 第2版
柴田 望洋 (著)
出版社: SBクリエイティブ; 第2版 (2020/12/9)
ISBN-10: 4815606005
ISBN-13: 978-4815606008

プログラミングコンテストチャレンジブック [第2版] 
～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
秋葉拓哉, 岩田陽一, 北川宜稔 (著)
出版社: マイナビ; 第2版 (2012/1/28)
ISBN-10: 4839941068
ISBN-13: 978-4839941062

[文字コードに関する注意]

Javaのコンパイル環境と異なるエンコーディングのソースファイルをコンパイルするには javac コマンドのオプションとして -encoding を指定する必要があります。

  javac -encoding  エンコーディング名  javaファイル名

日本語環境でよく使われるエンコーディング名は以下の通りです。

エンコーディング名	説明
utf-8	8bit Unicode Transformation Format
euc-jp	EUC日本語
iso-2022-jp	ISO 2022形式のJIS X 0201, 0208
shift_jis	シフトJIS(MS漢字コード)
windows-31j	日本語Windows

システムの標準ではないエンコーディングのjavaプログラムをコンパイルするとき encoding を指定する必要があります。津田塾大学計算センターのWindows環境で作ったソースファイルをMac上でコンパイルするときは

  % javac -encoding shift_jis  ファイル名.java

津田塾大学計算センターのMac環境で作ったソースファイルをWindows上でコンパイルするときは

  % javac -encoding utf-8  ファイル名.java

と指定して下さい。