日本数式処理学会Mathematica分科会関東WSに参加してきました

Report

レポートを書くのに1週間も日が空いてしまった・・・


日本数式処理学会Mathematica分科会関東ワークショップ

日時：2011年5月14日(土)　10:00-17:30
場所：東邦大学習志野キャンパス　東邦会館1Fラウンジ，薬学部A号館A101
http://www.toho-u.ac.jp/accessmap/index.html
主催：日本数式処理学会(Mathematica分科会)
共催：CASTeX応用研究会
協力：東邦大学


チュートリアル「MathematicaV8について」
講師：日本電子計算　伊藤雅将氏


全体講演「Mathematicaのフォーマット出力(FortForm.m)
とバッチ処理(Mathematicascript)」
講師：宇都宮大学　佐藤禎宏先生
概要：
・フォーマット出力に関係してJLink を使って速度を速めたこと
・Windows版でバッチ処理を試みた失敗話とLinux版でのMathematicascriptを使った解決策。などのMathematica ver8 新機能のすばらしさと不具合などについて話す。


13:30-14:20(50分)
全体講演「Mathematicaを使った原子炉動特性の計算」
講師：日本原子力研究開発機構　高松邦吉氏
概要：
数式処理システムMathematicaを使って，原子炉動特性の連立偏微分方程式を解いてみた。入力方法、NDSolve、予想される値と計算結果の比較について，発表する。


14:30-15:20(50分)
講演「Mathematica Cookbook について」
講師：Symbolic Systems　松田裕幸氏
概要：
4月に出版予定の「Mathematicaクックブック」は，プログラミング言語としてのMathematicaに関する本としては，久々の本である。かつ800頁を越える大著でもある。本書の翻訳を終え，その内容について紹介する。この本は多くの応用分野をカバーしているが，CやJavaあるいはFortranともまったく異なるMathematica流のプログラミングスタイルを全編にわたり強調している。


15:30-16:20(50分)
講演「Mathematica+KETpicで動く作図ツールDyGeomの製作」
講師：明治大学　阿原一志先生
概要：
Mathematica上での簡易作図ツールDyGeomを製作開始した。
現在は
（１）基本的な作図手順をコマンド化
（２）KETpicを経由してTeXファイルとして出力
（３）数式処理的な出力
をサポートしている。
このパッケージを紹介するとともに，これから進む方向について議論する。


16:30-17:20(50分)
講演「KETpicで楽々TEXグラフ」
講師：東邦大学　高遠節夫先生，工学院大学　北原清志先生
概要：
本講演は，3月に出版されたKETpicマニュアル本(CASTeX応用研究会編)をもとに，KETpicの概要，最近の機能拡張と本の出版の経緯について話をする。


Mathematicaクックブック

Mathematicaクックブック


本当は秋葉原で行われた「Mathematicaクックブック刊行記念セミナー」に行きたかったのですが無理だったので、いっそ本拠地に乗り込もうということで行ってみました。
まず驚いたのは会場の設備と準備の良さ。各講演者のMathematicaファイルがDVD-Rに焼かれ、プレゼン資料も予め印刷済み。そして何よりMathematica環境がインストールされたWindowsノートPCが40台ほど用意されていたということです。



こんな豪華な勉強会環境が存在することに驚きました。
Mathematica自体は高価なソフトウェアですが、誰でも説明を聞きながら実際に触れるというのが素晴らしいですね。


午前中は伊藤氏によるMathematica8についてのチュートリアル。資料がよくまとまっていて、初心者にまず見せたいと思わせるよいnbだったと思います。たまにTwitterで「Mathematicaわからん・・・」と嘆いている方を見かけるので、本当は公開して欲しいのだけど・・・

午後でよかったのはお目当てだった「Mathematica Cookbookについて」と「Mathematica+KETpicで動く作図ツールDyGeomの製作」。
「Mathematica Cookbook について」では、クックブック翻訳者の松田氏がMathematicaの多言語との違いを強調してお話してくれました。キーワードは関数型とパターンマッチング。講演後にお話もできました。クックブックについての反応がないと嘆いていましたので、感想をぜひみなさん送ってあげてくださいｗ


「Mathematica+KETpicで動く作図ツールDyGeomの制作」では、Mathematicaの変数のまま計算できるという特性を利用し、それを作図ソフトに利用、dviファイルに変換するということをしていました。見た目は教育用の作図ソフトですが、その中では多項環イデアルの解とかすごいところに問題が帰着していて面白かったです。




今回初めてワークショップに参加して思ったのは、他の勉強会等と比べて圧倒的に平均年齢が高いこと。Mathematicaが高価で手が出しづらい、数式処理という特性上大学で使われることが多いという点から大学関係の方が多かったように思われます。聞けば10年ぐらい前からほとんどメンバーが固定で、同窓会のようになってしまっているとのこと。僕のように完全に一般の参加者はまれなのでしょう。
Mathematicaは、他の技術系の話題に比べると圧倒的に検索しにくい、記事が書かれていないのですが、ここは平均年齢が高いことと関係があるような気がしました。平均年齢が高い→Twitterやブログなどで記事を書くことがない→情報共有がされない、人目に触れない→Mathematicaが世間に知られない→使用する人間の平均年齢が高くなる・・・という悪循環が起きているのではないでしょうか。Mathematicaの技術的な面についてはWolfram Researchががんばっていて、ドキュメントセンターの情報がとても豊富なのですが、それでもわかりにくいところがまだまだあります。特に新しく実装された部分については例が貧弱だったりなかったり、急に初心者置いてきぼりの適当な説明になっていたりしますから、自分が悩んで解決できたことなどについてはどんどん記事を書いていって欲しいなぁ。
あとは、Mathematicaについての質問・回答ができるようなフォーラムを作るとかね・・・とにかく情報共有ができるような環境を作ることがまずは大事かな、と。Wolfram Researchのテクニカルサポートではなく。

第6回「アルゴリズム勉強会」に参加してきました

Report

アルゴリズム勉強会

アルゴリズムを勉強していく会です
目的はアルゴリズムを実装と理論的の両方を身につけることです。

アルゴリズムを勉強したいと思っている初心者の方は、ぜひ参加してください。
いまのところ「アルゴリズムイントロダクション」を読んでいく予定です。

twitterのハッシュタグは #ITAReadでお願いします

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

  • 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
  • 出版社/メーカー: 近代科学社
  • 発売日: 2007/03/01
  • メディア: 単行本
  • 購入: 13人 クリック: 378回
  • この商品を含むブログ (59件) を見る


@oskimura さんに「参加しませんかー」と言われたので「参加しますー」というやりとりが開催の2週間前。その日にAmazonで「アルゴリズムイントロダクション」を購入しました。
今回は第5章「確率論的解析と乱択アルゴリズム」からなのでそこまで読んでおくように、とのことでしたが間に合うはずもなく。5章はノー予習で参加することになりました。
そもそも「乱択アルゴリズムって何？」という状態の私でしたが、それでも今回の勉強会は実りの多いものでした。当然わからない部分はたくさんあるのですが、随所に用意されている練習問題を他の参加者の方が説明をしてくれて、「なるほど！」と関心する場面多数。プロジェクタに表示ではなく板書で進んでいくスタイル、僕は好きでした。
15人ほどの参加者がいましたが、その中で2,3人の方が特にたくさん説明をされていたので、次回はちゃんと準備をして、発表もできるようになりたいと思いました。


続き物の勉強会に途中から参加するのは抵抗があるかもしれませんでしたが、第6回から参加で、しかも無勉強の私でも十分に面白い内容でしたので、興味のある方は次回是非お会いしましょう。次回は5.4「確率論的解析と高度な指標確率変数の利用法」からです。

記録するのはノートPCのエディタなどでもいいと思いますが、数式をエディタで入力するのは難しいので、紙があるとなにかと便利だと思います。
ちなみに今回僕はノートを忘れたので、応急処置としてMathematicaをエディタとして使いました。初めての試みでしたが、2次元的な数式を表現できるし、式変形などもすぐに検算できてとてもよかったです。

Visual Studio 2010でコマンド引数を設定する

configuration

vs2010でリダイレクトで悩んだので書いておきます。


プロジェクトのプロパティ→構成プロパティ→デバッグ→コマンド引数の部分で指定する。
"data.txt"を読ませたい場合は < data.txt とすればよい。
よくわからないけど、絶対パスだとうまくいかなかった。プロジェクトのリソースファイルにファイルを置いて、それを指定するといい。


@sakefさんに「絶対パスはダブルクオートで囲めばよい」と教えていただきました。
つまりコマンド引数部分に「< "C:\\Users\\ ... \\data.txt"」と入力すればできます。


検索用：Visual Studio 2010, VS2010, リダイレクト, コマンド, 引数, 入力, 出力

Google Code Jam 2011 Qualification Round

GCJ C++
Problem Small Large
A o o
B o o
C o o
D - -

Dめんどくさくてやってない

Code Jam - Google’s Coding Competitions

Problem A. Bot Trust

Problem A

愚直にシミュレーション。Large Datasetのconstraintが T,N<=100 なので助かったが、これが10^9とかになると死ねる。

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100;
int datanum;
char T[MAX_N];
int N[MAX_N];
int p;
int caseno;

int getNextB(){
	for(int i=p ; i<datanum ; i++){
		if(T[i]=='B') return N[i];
	}
	return -1;
}

int getNextO(){
	for(int i=p ; i<datanum ; i++){
		if(T[i]=='O') return N[i];
	}
	return -1;
}


void solve(){

	int step = 0;
	int orangep = 1;
	int bluep = 1;

	p=0;
	char c = T[p];
	int n = N[p];
	
	while(p < datanum){

		// next button is orange
		if(c=='O'){
			//orange robot
			if(n==orangep){
				p++;
				c = T[p];
				n = N[p];
			}
			else if(n>orangep){
				orangep++;
			}
			else orangep--;

			//blue robot
			int k = getNextB();
			if     (k>bluep) bluep++;
			else if(k<bluep) bluep--;

		}
		// next button is blue
		else{
			//blue robot
			if(n==bluep){
				p++;
				c = T[p];
				n = N[p];
			}
			else if(n>bluep){
				bluep++;
			}
			else bluep--;

			//orange robot
			int k = getNextO();
			if      (k>orangep) orangep++;
			else if (k<orangep) orangep--;

		}
		step++;
	}

	cout << "Case #" << caseno << ": " << step << endl;
}

int main(){
	int casenum;
	cin >> casenum;

	for(caseno=1 ; caseno <= casenum ; caseno++){

		cin >> datanum;
		for(int i=0 ; i<datanum ; i++){
			cin >> T[i];
			cin >> N[i];
		}

		solve();
	}
}

Problem B. Magicka

Problem B

Combineについては"We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters)."の記述があるので、combineして新しく追加された文字に対してさらにcombine、というような連鎖に対する心配はしなくていい。
このコードではcombine, opposeに命令を全て突っ込んで全部走査しているけど、アルファベットで配列にマッピングすれば定数時間でアクセスできるのでそっちの方が速い。

#include <iostream>
#include <istream>
#include <string>
using namespace std;

const int MAX_C = 37;
const int MAX_O = 29;

int caseno;
int caseNum, combineNum, opposeNum, invokeNum;
string combine[MAX_C], oppose[MAX_O], invoke;

bool check(string s1, string s2){
	if(s1==s2) return true;

	string ss;
	ss += s2[1];
	ss += s2[0];

	if(s1==ss) return true;
	return false;
}


void solve(){

	string s;
	int p=0;

	for(int p=0 ; p<invokeNum ; p++){
		s += invoke[p];

		if(s.size()==1) continue;

		// combine
		string cs = s.substr(s.size()-2, 2);

		for(int i=0 ; i<combineNum ; i++){
			if( check( cs, combine[i].substr(0,2) ) ){
				s.pop_back();
				s.pop_back();
				s += combine[i][2];
				break;
			}
		}

		// oppose
		string os;
		os += s.back();
		bool opposed = false;
		for(int i=0 ; i<s.size()-1 ; i++){
			os += s[i];


			for(int j=0 ; j<opposeNum ; j++){
				if( check( os, oppose[j] ) ){
					//s.erase(i);
					s.clear();
					opposed = true;
					break;
				}
			}
			if(opposed) break;
			
			os.pop_back();
		}

	}
	
	cout << "Case #" << caseno << ": ["; 

	if(s.empty()){
		cout << "]" << endl;
		return;
	}

	for(int i=0 ; i<s.size()-1 ; i++){
		cout << s[i] << ", ";
	}

	cout << s.back() << "]" << endl;

}



int main(){

	cin >> caseNum;

	for(caseno=1 ; caseno<=caseNum ; caseno++){

		cin >> combineNum;

		for(int i=0 ; i<combineNum ; i++){
			cin >> combine[i];
		}

		cin >> opposeNum;

		for(int i=0 ; i<opposeNum ; i++){
			cin >> oppose[i];
		}

		cin >> invokeNum;
		cin >> invoke;
		solve();

	}

}

Problem C. Candy Splitting

Problem C

num2powerなんて配列を作っているけど、実際はxorでいい。
つまり、

  1. 全ての数のxorをとる。xorした値が0以外→"NO"
  2. 一番小さい値以外をすべて足した値が答え

「一番小さい値以外をすべて足す」ということは、泣き叫ぶパトリックには実は一番小さいものだけあげておけばいいということ。xorをとって0でないのならそもそもどうやってもパトリックを泣かせないのは不可能だし、xor=0ならどう分けてもパトリックは納得する。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;

int caseNum, dataNum, caseno;
vector<int> v;

int num2power[21];

void bitCount(int n){
	int a=1;

	for(int a=0 ; a<21 ; a++){
		if( (n & 1<<a) == 1<<a) num2power[a]++;
	}
}



void solve(){
	cout << "Case #" << caseno << ": ";

	for(int i=0 ; i<21 ; i++) num2power[i] = 0;
	

	
	for(int i=0 ; i<v.size() ; i++){
		bitCount(v[i]);
	}

	
	for(int i=0 ; i<21 ; i++){
		if(num2power[i]%2==1){
			cout << "NO" << endl;
			return;
		}
	}

	sort(v.begin(), v.end());

	int k=0;
	for(int i=1 ; i<v.size() ; i++){
		k += v[i];
	}

	cout << k << endl;
	return;

}

int main(){

	cin >> caseNum;
	int k;

	for(caseno=1 ; caseno<=caseNum ; caseno++){
		cin >> dataNum;
		v.clear();

		for(int i=0 ; i<dataNum ; i++){
			cin >> k;
			v.push_back(k);
		}

		solve();
	}
}

C++でマージソート

algorithm C++

マージソート - Wikipedia

#include <iostream>
#include <vector>

//型の最大値を取得するために使用
#include <limits>

using namespace std;

template <class T>
void print(vector<T>& v){
	for( vector<T>::iterator it = v.begin(); it != v.end() ; ++it) cout << *it << " ";
	cout << endl;
}


template <class T>
void merge(vector<T>& v, int p, int q, int r){

	int n1 = q-p+1;
	int n2 = r-q;

	T *L, *R;

	L = new T[n1+1];
	R = new T[n2+1];

	for(int i=0 ; i<n1 ; i++) L[i] = v[p+i];
	for(int i=0 ; i<n2 ; i++) R[i] = v[q+i+1];

        // 番兵
	// numeric_limitsで最大値をL, Rの最後に入れる(Infinityのつもり)
	// string型の配列などを入れるとエラー
	L[n1] = numeric_limits<T>::max();
	R[n2] = numeric_limits<T>::max();

	int i=0, j=0;
	for(int k=p ; k<=r ; k++){
		if(L[i] <= R[j]){
			v[k] = L[i];
			i++;
		}
		else{
			v[k] = R[j];
			j++;
		}
	}
}


// マージソート
// intで範囲指定する版
template <class T>
void merge_sort( vector<T>& v, int p, int r ){

	if(p < r){
		int q = (p+r)/2;

		merge_sort(v, p, q);
		merge_sort(v, q+1, r);
		merge(v, p, q, r);
	}
}


int main(){
	
	vector<int> v;
	v.push_back(5);
	v.push_back(10);
	v.push_back(3);
	v.push_back(1);
	v.push_back(0);
	v.push_back(100);
	v.push_back(-1);
	

	print(v);

	merge_sort(v, 0, v.size()-1 );

	print(v);
	
	return 0;
}

「アルゴリズムイントロダクション」p.28より、番兵を使った場合のマージソート。疑似コードでは番兵がInfinity扱いなのでnumeric_limitsなんて使ってみたが、numericなので当然そうでない型だとエラーが起こる。
番兵なしverを書く必要あり。


参考：numeric_limits - C++ Reference

C++で挿入ソート

algorithm C++

挿入ソート - Wikipedia

#include <iostream>
#include <vector>
#include <string>
using namespace std;


// 挿入ソート (値渡し)
template <class T> vector<T> insertion_sort(vector<T> v){
	
	int i,j;
	T key;
	for(j=1 ; j<(signed)v.size() ; j++){
		key = v[j];

		i=j-1;
		while(i>=0 && v[i] > key){
			v[i+1]=v[i];
			i--;
		}
		v[i+1] = key;
	}
	return v;
}

// 挿入ソート(参照渡し)
template <class T> void insertion_sort2(vector<T>& v){
	
	int i,j;
	T key;
	for(j=1 ; j<(signed)v.size() ; j++){
		key = v[j];
		i=j-1;
		while(i>=0 && v[i] > key){
			v[i+1]=v[i];
			i--;
		}
		v[i+1] = key;
	}

	return;
}

int main(){

	// int配列
	vector<int> v;
	v.push_back(5);
	v.push_back(10);
	v.push_back(3);
	v.push_back(1);
	v.push_back(0);
	v.push_back(100);
	

	/*
	// string配列
	vector<string> v;
	v.push_back("abc");
	v.push_back("aaa");
	v.push_back("heo2");
	v.push_back("12hrsl");
	*/

	for(int i=0 ; i<v.size() ; i++) cout << v[i] << " ";
	cout << endl;


	//v = insertion_sort(v);
	insertion_sort2(v);


	for(int i=0 ; i<v.size() ; i++) cout << v[i] << " ";
	cout << endl;

	return 0;
}

追記1

で。iteratorで範囲指定する方がいいというご指摘を頂いたので挑戦してみましたがわけわからず。(下のコード)
@nyaocat さんがわざわざ参考にとコードをかいてくださったのですが、バブルソートと違い(上と同じように実装する場合は)keyを変数として持つ必要があるので vector::iterator てな長々しい引数になり、そして「テンプレート 引数を 'T' に対して減少できませんでした」という謎なエラーにぶちあたって挫折しました。(あとから気づきましたが関数の中もめちゃくちゃです)


「signedでキャストするとコンテナのサイズがintの値を超えたら破綻する」というご指摘も頂きましたが、vectorが持てる要素が1億個を超えるような時代が見えたら考えます。


#include <iostream>
#include <vector>
#include <string>
using namespace std;


template<class Iter>
Iter next_Iter( Iter it ){
	return ++it;
}

// iteratorで範囲指定
template <typename T> 
void insertion_sort(typename vector<T>::iterator begin, typename vector<T>::iterator end){
	
	vector<T>::iterator it = begin, it2 = begin;
	T key;

	while(++it != end){
		key = *it;

		it2 = it;
		it2--;

		while(it2 != begin && *it2 > key){
			*next_Iter(it2) = *it2;
			it2--;
		}
		*next_Iter(it) = key;
			
	}
	return;
}


int main(){
	vector<int> v;
	v.push_back(5);
	v.push_back(10);
	v.push_back(3);
	v.push_back(1);
	v.push_back(0);
	v.push_back(100);
	

	insertion_sort( v.begin(), v.end() );
	// error C2783: 'void insertion_sort(vector<T>::iterator,vector<T>::iterator)' : テンプレート 引数を 'T' に対して減少できませんでした
	// main.cpp(15) : 'insertion_sort' の宣言を確認してください。

	for( vector<int>::iterator it = v.begin(); it != v.end() ; ++it) cout << *it << endl;

	return 0;
}

追記2

Twitterで泣き叫んでいたら解決法を教えていただきました。

  1. insertion_sort のように呼び出す
  2. iterator_traitsを使って、イテレータが指す型の情報を呼び出す
  3. swapを使う

全てVC10で動きました。@Flast_ROさん、@Dr_Garugariさん、 @nyaocatさんありがとうございました！
(prev_Iter(begin)って呼び出し方は大丈夫なのかな・・・)
ところでswapって上2つに比べて計算量がちょっと多いんじゃないかしら。


iterator_traits参考：iteratorを引数にするジェネリック関数 iterator_traits - dogatana's diary


#include <iostream>
#include <vector>
using namespace std;


template<class T>
void myswap( T& lhs, T& rhs){
	T tmp = lhs;
	lhs   = rhs;
	rhs   = tmp;
}

template<class Iter>
Iter prev_Iter( Iter it ){
	return --it;
}

template<class Iter>
Iter next_Iter( Iter it ){
	return ++it;
}


// iteratorで範囲指定
// 呼び出し時に insertion_sort<int> のように型名をつける
template <typename T> 
void insertion_sort(typename vector<T>::iterator const begin, typename vector<T>::iterator const end){
	
	typename vector<T>::iterator it = begin, it2 = begin;
	T key;

	while( ++it != end){
		key = *it;

		it2 = it;
		it2--;

		while(it2 != prev_Iter(begin) && *it2 > key){
			*next_Iter(it2) = *it2;
			it2--;
		}
		*next_Iter(it2) = key;
	}
}


// iterator_traitsを使って、イテレータが指す型の情報を呼び出す
template <class Iter> 
void insertion_sort2(Iter const begin, Iter const end){
	
	Iter it = begin, it2 = begin;
	typename iterator_traits< Iter >::value_type key;

	while( ++it != end ){
		key = *it;
		it2 = it;

		while( --it2 != prev_Iter(begin) && *it2 > key ){
			*next_Iter(it2) = *it2;
		}
		*next_Iter(it2) = key;
		
	}
}

// swapによる実装
template <class Iter>
void insertion_sort3( Iter const begin, Iter const end ){
	Iter it, kt;

	for( it = next_Iter(begin) ; it != end ; ++it){
		for( kt = it ; kt != begin && *kt < *prev_Iter(kt) ; --kt){
			myswap( *kt, *prev_Iter(kt) );
		}
	}
}

int main(){
	vector<int> v;
	v.push_back(5);
	v.push_back(10);
	v.push_back(3);
	v.push_back(1);
	v.push_back(0);
	v.push_back(100);

	//insertion_sort<int>( v.begin(), v.end() );
	//insertion_sort2( v.begin(), v.end() );
	insertion_sort3( v.begin(), v.end() );

	for( vector<int>::iterator it = v.begin(); it != v.end() ; ++it) cout << *it << endl;
	return 0;
}

Visual Studio 2010で勝手にコマンドプロンプトが閉じないようにする

configuration

下のリンクで全て解決。

http://d.hatena.ne.jp/jonki/20110414


検索用：Visual Studio 2010, VS2010, cmd, コマンドプロンプト, 閉じる, 終了する, コンソール, 設定, 変更