アルゴリズム a


[UP]

[お知らせ]

[注意] 2022年度はすべて対面授業となることが予定されています。 しかし、状況はまだ流動的であるため、オンライン授業またはハイブリッド授業に関する記述もこの資料に残っています。

私が担当するオンライン授業全般に関するお知らせはこちら

お知らせ

オンライン授業を受講する場合は、 Zoomに「Googleでサインイン」してから、本授業のZoomミーテイングに参加して下さい。 本授業のZoomミーティングIDは、 オンライン授業ポータルサイト(学生向け) オンライン授業時間割表 に記載されています。

この授業をオンライン受講するのに必要な情報は GoogleDrive に置きます。履修登録者は @gm.tsuda.ac.jp のアカウントでアクセスして下さい。 当初は@gm.tsuda.ac.jp全員がアクセス可能ですが、ある時点で履修登録者のみに制限します

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

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


[授業内容]

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

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

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

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

単なる理論的な説明だけで終わるのではなく、できるだけ 実装例(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に対応しています。

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

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


[授業日程]

講義: 対面授業 Zoomによるオンライン授業
演習: 対面授業 Zoomによるオンライン授業

出席状況:


課題提出状況


教科書


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

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

授業を欠席した場合は、次の授業までに当該分野の本を自分で読破し、 授業内容と同等の知識を独力で身に付けておくことが必要です。


参考書

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


問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
米田 優峻 (著)
出版社: 技術評論社 (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

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