アルゴリズムとプログラミング実践講座
2014年 夏学期 火曜 13:00 -- 14:30 at I-REF 棟 6階 ヒロビー
稲葉真理 with 浅井大史, 手塚宏史
シラバスに書いた概要
計算機で問題を解くためには,問題を解くための手順である「アルゴリズム」を,プログラムという形にして計算機に渡す必要がある．効率よく問題を解くためには,問題に適したアルゴリズムの設計あるいは選択が重要となる．この講義では,プログラムを書くという視点にたち,アルゴリズムの基本概念と応用について,解析よりも実践を重視した講究を行う．
2014年夏学期の計画 （2014年4/8現在）
- 概論 -- 計算機と計算量とアルゴリズム
- 離散構造とモデル化
- インターネットとグラフ構造
- データマイニングとクラスタリング
- メタヒューリスティクス
- ライブラリを使ってみよう
- 7/8 （火） Prof. David Avis @ 京大 ＋ McGill Univ. による講演
Can computers think?
by Prof. David Avis
Abstract:
We will discuss this question by beginning with Alan Turing's historic paper in 1950 that started the field of ariticial intelligence (AI).
This paper includes a test, now called the Turing test, in which a computer tries to convince humans that it is a human rather than a computer.
We will discuss this test and related competitions, including the famous Loebner prize, and claims that Eugene Goostman, a chatbot, passed the test on June 7, 2014.
We will attempt our own Turing test during the last part of the lecture.
講義資料
第12回のレポート提出は、7/27（日）で〆切ます。
第5〜11回のレポート提出は、8/17（日）で〆切ます。
第3回と第4回のレポート提出は、6/22（日）28:00 で〆切ました。
第1回と第2回のレポート提出は、5/18（日）で〆切ました。
レポート課題
レポート用のデータ取得・データ表示用ソフトウェアのための URL
- データ取得
- パーサー
- 日本語用の形態素解析茶筅
- 英語用の構文解析器 Enju (Fast, Accurate, Deep Parser for English)
CS 辻井出身の宮尾先生＠NIIが作った解析器。日本語の説明あり。リクエストを投げたら、Komainu というアドレスからメールが来てダウンロードできる。
- TreeTagger - a language independent part-of-speech tagger
German, English, French, Italian, Dutch, Spanish, Bulgarian, Russian, Portuguese, Galician, Chinese, Swahili, Slovak, Latin, Estonian and old French texts で成功してるとのこと♪
- グラフ可視化関連
- GEPHIグラフ可視化プラットフォーム
かなり「いまどき感」のただようプラットフォーム。import できる（しようと努力している？） format も多い。
- graphvizグラフ可視化ツール
簡単な言語で記述されたグラフを指定された形式に適当にレイアウトして表示。お手軽。Mac だと port で入る。
- igraphネットワーク解析パッケージ
C/C++, python, R から使えるとのこと。
- Tulip Better Visualizatoin Through Research
巨大グラフの可視化がターゲット。クラスターの指定機能など
- Pajek wiki
大規模ネットワークの可視化ソフト。もともとはネットワーク分析用ソフトウェア
UCINETの
データを表示するためのソフト。
適当にクリックしてたら蜘蛛の写真がでてきてどっきり。
「Pajek」 はスロベニア語で「蜘蛛」だそうです。
そういえば、「web」って「蜘蛛の巣」だっけ・・
- graph-tool
python のモジュールだそうです。(自分は 未インストール)
- D3 Data-Driven Documents
最近流行のJavaScriptの動画描画ツール。
Webページとの相性が良いそうです(自分は 未インストール)
- Node Box
5年前くらいに流行った描画ツール。
動画ファイルに落とせるので、プレゼン資料などに埋め込みやすく、使い勝手が良いそうです。(自分は 未インストール)
- SVG の仕様
お遊びで使ってみたので仕様。
- SATsolver 関連
- MiniSAT
- minisat2-070721.zipをダウンロード
- ファイルを解凍
- core/ディレクトリに移動
- $ make
- minisatというファイルが作成される
- $ ./minisat CNFファイル 出力ファイル
- 充足可能な解が存在すれば「出力ファイル」に出力される
MiniSATをMacでコンパイルする場合の対処法
- Glucose
- Glucose 3.0を選択してソースコードをダウンロード
- 解凍
- core/フォルダに移動
- $ make
- $ ./glucose CNFファイル 出力ファイル
- picosat
- " picosat-959.tar.gz"をダウンロード
- 解凍
- ディレクトリに移動
- $ ./configure
- $ make
- $ ./picosat CNFファイル
- Prof. David Avis の講演関連
レポート関連サンプルコード
- 第一回 Makefile の使い方:
サンプル MakefileとCのコードijloop.cとdiagonal.c
（注意）あくまでサンプルで,お手本というわけではないです．コメント何も入ってないし．
- 第一回 Ruby のコードのサンプル hash.rbとarray.rb
（注意）日本語で大量にコメントが入ってるので,コードが違うなら,たとえば nkfコマンドかけてください．動作はいろいろ謎が多い．詳しい人教えてください．
- 第二回 gnuplot で出力してみるサンプル Makefileと
test.shとplot.gpと
gettime.hとgettime.hと
ijloop.c
（コメント）test.sh の出力を #!/usr/bin/env で$PATH に従って探した gnuplot に食べさせている
- 第二回 htmlを吐き出してみるサンプルMakefileとtest.shとExArray1.java
（コメント）1は stdout, 2 はstderr, ( ) はサブシェルの起動,<< EOFは here document．java ではどこが重いか（気が向いたら）犯人探しもしてみてください．
- 第三回 Trie の骨格trie.cとMakefile
（コメント）頻度を前に書きだし パイプでつないで sort -rg
- 第三回 連想リストtest.awk
（コメント）BEGIN で 最初に句読点等をフィールドセパレータに指定。＋は一個以上の繰り返し。
- 第四回 ランダムグラフ・WSグラフ生成
readme-utf.txt,
kgenp.awk,
thrsh.awk,
wsmodel.awk,
wsdraw.awk,
wsdraw2.awk
（コメント）wsdraw, wsdraw2 はお遊びです。形式を指定ができるツールは便利ですね。
- 第四回 ランダムグラフ生成・第五回三角形を数える
Makefile,
args.h,
graph.h,
graph.cpp,
generate.cpp,
triangle.cpp
（コメント）graph は共通
- 第十一回 数独を SATで解く
sudoku_makein.c,
print_sudoku_board.c,
皆さんのコードから(ありがとうございます♪)
第一回 O.O.している C++ :
access.cppとMakefile
- 興味がある初心者の方は「写経＋解読」（？）をお勧めします♪
第一回 Octaveを使って：
ベクターコマンド利用しない場合と
ベクターコマンド利用した場合の比較。
- 数値解析用ソフトウェア
GNU Octave (matlab のお友達らしい) ダウンロード
- Mac で octave を port 使ってインストールしてみたら atlas のインストールでぱったり。たくさん待ちました（１時間くらいで一旦止めた）。port -v が verbose mode.
- matlab 導入は試みたけどヤリトリが面倒で挫折。電話は嫌い。
第一回 FORTRAN を使って:
matrix_time.f90
- 数値計算は FORTRAN という知人は多い。（書いてくれた人がいて良かった。人頼みですみません）
- atlas (octave) 入れたとき、install log を片目で眺めてて、fortran がすでに入ってるらしいことはぼんやりと認識してたので、コマンド探すとこから始めた。
ls `echo $PATH | sed "s/:/ /g"` 2> /dev/null | grep ありそうな名前（f77, f95, fortran とか）← 自分用なら ls の吐く stderr は気にしないが講義資料なので少しだけお化粧
- 配列の動的割付けは、宣言 integer, allocatable :: mat(:,:) 、割り付け
allocate(mat(n, n))、 解放 deallocate(mat)。これカードの時代はなかった(と思う)。
第二回 素敵に python ライフ: exec.pyと
使われているC のプログラム達 （注：C のコードは固めてあります）
- 使い方: python exec.py
- 平均アクセス時間を出力するCのプログラムfname (複数登録)を
gcc でコンパイル。行列サイズ size(複数登録）は、コンパイルオプションで渡す。
出力された時間を行列 rt[][]に格納。
- import subprocess, import os, import matplotlib.pyplot as plt,
import numpy as np, from math import *, import datetime してる。
- 日本語のコメントが入ってるので、適宜、nkf 等をかけてください。
-
注：現在、まだ C のプログラムは置いていません。 置きました(5/19)。
第二回 JavaScript で実験からグラフ化まで：
hw2_js_index.htmlと、
使われているJavaScriptのプログラム達 （注：JavaScript のコードは固めてあります）
- 使い方: hw2_js_index.html を、Safari, Firefox, Chrome などのブラウザで、それぞれ開き、パラメータを入れる。
- 利用されているライブラリ
- なるほど、ブラウザーによって違うんだなぁ・・・（レポートを読んだ感想）
参考文献など(セット本は第一巻のみ紹介)
アルゴリズムの教科書など
- The art of Computer Programming (Donald E.Knuth,(訳)有澤誠,青木孝,和田英一)
Knuth 先生の終わらない旅．古い版（英語,サイン入り♪）はもってるけど,いい機会だから買おうかな買いました．
- アルゴリズム設計マニュアル（Steven S. Skiena,(訳)平田富夫）
今期のタネホンその１
- 計算とアルゴリズム（浅野孝夫,今井浩）
今期のタネホンその２
- アルゴリズムとデータ構造(基礎のツールボックス) （Kurt Mehlhorn,Peter Sanders, (訳)浅野哲夫）
プログラマーの気持ちがわかってる本
- アルゴリズムイントロダクション
（Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,（訳）浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一）
無難な分厚い定番教科書
- バイオインフォマティクスのための
アルゴリズム入門(Pavel A.Pevzner, Neil C.Jones, (訳)渋谷 哲朗)
アルゴリズムの教科書で応用先が生命情報という作り方なので、
生命情報が専門でない人にとっても有用な本。イラストがなにげに素敵。
- データ構造とアルゴリズム（五十嵐健夫）
一週間で読み切ることができる教科書ならこれ．ともかく薄いのが素敵♪
離散数学よりの教科書
- 離散数学への招待・上（Jiri Matousek, Jaroslav Nesetril, (訳)根上生也,中本敦浩）
理屈っぽいお茶目が隠れてる離散構造の入門書・今期のタネホンその３
- Data Structures and Network Algorithms(Robert Endre Tarjan)
まだアマゾンがない時代、McGillの本屋さんで購入しました。本をかついで帰るためのリュックサックも一緒に買ったっけ。
岩野和生さんによる日本語訳二つ
（黄色い旧版）
（白い新訳）
- コンピュータの数学 (Ronald L.Graham, Oren Patashnik, Donald E.Knuth,
有沢誠, 萩野達也, 安村通晃, 石畑清)>
原題は CONCRETE MATHEMATICS A FOUNDATION FOR COMPUTER SCIENCE． 原題そのもの。
- Computers and Intractability: A Guide to the Theory of Np-Completeness (Michael R.Garey, David S.Johnson)
誰のところに遊びにいっても（ただしアルゴリズム屋さんね）必ず本棚にある本
- 組合せ論入門(George Polya, Robert E.Tarjan, Donald R.Woods, (訳)今宮淳美(翻訳)）
厚さは薄いけど中身はかなり濃い目
- グラフ理論入門（Robin J.Wilson， (訳)西関隆夫,西関裕子）
読む人のことを考えてる入門書
- Graph Drawing: Algorithms for the Visualization of Graphs
(Ioannis G.Tollis, Giuseppe Di Battista, Peter Eades, Roberto Tamassia)
drawing だけで一分野なんだな・・・と思った
- Computational Geometry: An Introduction (Franco P. Preparata, Michael Shamos)
計算幾何という分野を切り出した Shamos の博士論文(1979, Yale大学)を元に書かれた本。Preparata は「計算幾何の祖父」と呼ばれることも多い。
日本語訳はは絶版・中古のみ
- 組合せ幾何学のアルゴリズム（Herbert Edelsbrunner,(訳)今井浩,今井桂子）
学生時代,研究室の人と一緒に英語版と格闘した思い出の本。
- The Traveling Salesman Problem: A Computational Study （David L.Applegate,Robert E.Bixby,Vasek Chvatal,William J.Cook）
TSP に魅せられて。すごいの一言。
確率・統計・ランダマイズドアルゴリズム・スモールワールド
- Introduction to Information Retrieval
(Christopher D.Manning, Prabhakar Raghavan, Hinrich Schutze) 英語版は無料でオンライン入手可能、しかも図がカラー♪
検索の現場をよく知ってる人が大事なポイントの理屈を説いてくれる本。今期のタネホンその４。
- 情報検索の基礎(Christopher D.Manning, Prabhakar Raghavan,
Hinrich Schutze,(訳)岩野和生, 黒川利明, 濱田誠司, 村上明子)
上記の日本語版。（6/10 追記：誤訳が多く大事なところで意味が通じないことがあるので、英語が苦手でも
おかしいかなと思ったら、無料の英語版を引くと良いと思います。）
- Randomized Algorithms (Motwani and Raghavan)
直感的説明が素敵にかっこよくてすごい．Google 設立にもかかわってる Prabhakar Raghavanの本．
- テキストマイニングハンドブック(ローネン・フェルドマン, (訳)辻井潤一監訳)
カバー範囲が広い。
- 確率論とその応用(William Feller, (訳)河田龍夫, 卜部舜一)
全然古くならない 50年以上前に書かれた教科書。
- キーポイント確率統計 (和達三樹, 十河清)
物理学者が書いた統計の本。「わかったうえで使ってもらいたい」という目的意識が明確な本。薄いのも素敵♪
”・・・のと同様に、確率分布の相互関係を調べるのは大変興味深い。しかもこちらは「役に立つ」というおまけ付きなのである。”（本文より抜粋）
- Networks, Crowds, and Markets: Reasoning About a Highly Connected World(David Easley, Jon Kleinberg)
確固たる情報科学の基礎と、社会からの要請とを、繋いで見せてくれる教科書。グラフ理論やゲーム理論の基本から書いてあるので、意志と根性がある人におすすめ。
- スモールワールド ネットワークの構造とダイナミクス(Duncan J. Watts,(訳)栗原聡,福田健介,佐藤進也)
Small World を表すWSモデルを提唱した Watts の博士論文を元に書かれた本。
- 複雑ネットワーク―基礎から応用まで(増田直紀,今野紀雄)
きちんと書かれてる感じの本
おまけの話関係の教科書
- コンピュータアーキテクチャ 定量的アプローチ（John L. Hennessy, David A. Patterson, (訳)中條拓伯,吉瀬謙二,佐藤寿倫, 天野英晴)
通称へネパタ．メモリー階層（とか,計算機アーキテクチャ）に興味をもったなら,これ．
- コンパイラ―原理・技法・ツール（Alfred V.Aho,Jeffery D.Ullman, Ravi Sethi,
Monica S.Lam, (訳)原田 賢一)
通称ドラゴンブック．コンパイラに興味をもったなら,たぶんこれなのかな．いつの間にかモニカラムが著者になっていた♪
- オペレーティングシステムの概念（Abraham Silberschatz, Peter Baer Galvin, Greg Gagnei, (訳)土居範久, 大谷真, 加藤和彦, 光来健一, 清水謙多郎, 高田眞吾, 高田広章, 千葉滋, 野口健一郎)
千葉先生が訳してる。 先生、お値段が・・・
- コンピュータネットワーク(Andrew S. Tanenbaum, David J. Wetheral, (訳）水野忠則, 相田仁, 東野輝夫, 太田賢 , 西垣正勝, 渡辺尚)
- Distributed Systems: Principles and Paradigms (Andrew S. Tanenbaum, Maarten Van Steen)
日本語訳は前の版の物はあるが絶版・中古のみ
- Parallel Computer Architecture: A Hardware/Software Approach
(David Culler, J.P. Singh, Anoop Gupta)
並列アーキテクチャーならこれ。
読み物
プログラミング関連,文書作成ための参考書など
- プログラミング言語C（Brian W. Ritchie, Dennis Kernighan,(訳)石田晴久)
「とりあえず一冊」なら、これ．
- プログラミングコンテストチャレンジブック
~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~ (秋葉拓哉,岩田陽一,北川宜稔)
アルゴリズムがどう動くか中心のプログラミングの本。通称、蟻本。受験参考書の香りがほんのりと。著者のうちのお二人は CSで、在学中に執筆。すごいなぁ。
- シェルスクリプト基本リファレンス（山森 丈範）
上級者向けリファレンス．移植性に詳しい．
- 詳解 シェルスクリプト（Arnold Robbins, Nelson H.F.Beebe,(訳)日向あおい）
中級者向け．原題は "Classic Shell Scripting"．「詳解 シェルスクリプト」というよりは
むしろ「実践的シェルスクリプト」かも．
-
入門UNIXシェルプログラミング―シェルの基礎から学ぶUNIXの世界（Bruce Blinn,（訳）山下哲典）
初心者向け．読み物的．
- プログラミング言語AWK(Alfred V.Aho, Brian W.Kernighan, Peter J.Weinberger, (訳)足立高徳)
糟糠の言語．全く乗りこなせてないけど．
- sed & awkプログラミング(Dale Dougherty, Arnold Robbins,(訳),福崎 俊博)
基本からゆっくり．
- Pythonによるデータ分析入門 ―NumPy、pandasを使ったデータ処理 (Wes McKinney, (訳)小林儀匡, 鈴木宏尚, 瀬戸山雅人, 滝口開資, 野上大介)
レポートのソースコードを見てぽちった本。
- GNU Octave: Beginner's Guide (Jesper Schmidt Hansen)
例がたくさん。この本によると、GNU Octave は数値解析のために (1)多様なビルトインファンクション、(2)機能拡張のためのプログラミング言語、(3)描画機能を提供してくれるツールらしい。
matlab とソースを共にするための how-to あり。
- RとRubyによるデータ解析入門 (Sau Sheong Chang, (訳)瀬戸山雅人, 河内崇, 高野雅典, 橋本吉治)
Ruby と R は相性がいいらしい
- UNIXプログラミング環境（Brian Kernighan, Rob Pike,（訳）石田 晴久）
絶版ですが・・・一部内容古いですが・・・でも、思い入れのある本なので紹介しておく
- プログラミング作法（Brian Kernighan, Rob Pike,（訳）福崎俊博）
本ならではの味があると思う
- LaTeX2ε美文書作成入門(奥村晴彦,黒木 裕介)
細かい説明がおさえてある本
- TEX入門(大野義夫)
TeXの考え方を説明してくれている本．box, glue, METAFONT
レポート作成のための環境設定などの URL
アルゴリズムの動作などの動画