algorithm c

アルゴリズム c (演習付)

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用] ユーザ名とパスワードを利用して下さい。

[授業内容]

「アルゴリズムa」や「アルゴリズムb」に続いて、さらに発展した「アルゴリズム」と「データ構造」について学習します。

探索やグラフに関する代表的なアルゴリズムを学びます。バックトラックや動的計画法などについても解説します。

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

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

[cygwin について]

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

[授業日程]

講義: 火曜3限 @5206
演習: 火曜4限 @S205

04.16 --- バックトラック法, 分岐限定法
04.23 --- ダイクストラ法 , Priority First Search
04.30 --- A* , Javaについて補足説明 , Bellman-Ford
05.07 --- A*の応用: 8パズル
05.14 --- 動的計画法: ナップザック
05.21 --- 動的計画法: 編集距離
05.28 --- 最大流
06.04 --- 巡回セールスマン問題
06.11 (補講日) 授業無し
06.18 --- 筆記試験

[参考]

Minimum Spanning Tree 問題

出席状況:

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

課題提出状況

[注意] 課題提出Web へのアクセスは、 Google Drive の passwd.txt に[Web用]として書かれているパスワードを使って下さい。大学にVPNを張るのはできるだけ避けて下さい。

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

参考書

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

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

http://ynitta.com/class/algoC/