JULY

第18号（平成21年7月）
E/!F/!Lovui ɈშුĶUif!Bsu!pg!DpnqvufsQsphsbnnjohķɅĂॸ࢞౰‫ݪ‬Ķ[EEķȦऻ੪ȯɦȹȭɂɅȾȞɀ

るだけで大変な栄誉なんですよ」とか、「こんな載り方をしʋˋʬʽĜʗʍɼʀˋʑಮ০āஂ࣋ୂāვāణ‫ێ‬

返ってくるので、どうもこれは本当におそれ多いことになっ学会の論文賞よりよっぽどすごい」とか、「索引に名前が出たのは日本人初の快挙です」とか、ただごとでない反応がているのだということが実感されてきた。それで、とにかく昨年の秋、１通の電子メールが届いた。見覚えのない差出原稿の校正作業に協力せねば、ということで、当時やってい人名で、英語で何か書かれており、「詳しくはここからダウ た研究を一旦、脇に置いて、1ヶ月程はこちらに専念するこンロード」というような記述もあって、毎日届く怪しいスパとになった。
さてここで、今回掲載された内容について簡単に説明しムメールと外見上は大差ないように見えた。だが、何かいつもと違うような気がしたので、捨てずによく読んでみると、 ておくと、まず本書は「アルゴリズムのバイブル」とも呼ばれ、世界中で読まれている名著中の名著である。全7巻の予どうも大変なことが書いてあるようだった。
そのメールは、チューリング賞や京都賞の受賞者で、出版定でKnuth先生が生涯をかけて執筆しているもので、現システムTeXの開発者としても知られるD. E. Knuth先生

在、第4巻を執筆中である。
（Knuth先生はすでに70歳を超からのもので、それを先生の秘書が転送してきたものだっ えており、全７巻完成は困難と見られている。）4巻は書き上た。メールの内容は、Knuth先生が執筆中の名著「The Art

がったところから随時、分冊（fascicle）として出版されてof Ｃｏｍｐｕｔｅｒ Ｐｒｏｇｒａｍｍｉｎｇ」において、湊が以前に考案した技法「ZDD」について解説したので、考案者として校正作業に協力して欲しい、との依頼であった。私は、にわかには信じられず、やっぱりスパムかもと疑ったが、Knuth先生のホームページから、おそるおそる原稿をダウンロードしてみると、確かに、自分の名前とともに「ZDD」が載っている。しかもただ載っているだけでなく、項目として詳細に説明されていて、70問以上もの演習問題まで付いている。これはどうも本物らしいと思って、何人かの先生方にお知らせしたところ、「それはたいへんだ、

図１：Knuth先生からの手紙と掲載された本Ľ2Ľ

おり、これまでに分冊2、3、4が先に出て、次に分冊0がの実験結果を記載している。264問に及ぶ演習問題に出て、この度出版されたのは最後に残っていた分冊１では、学生が学会で発表できるレベルの問題が多数含まある。この分冊のテーマは「論理の表現と処理」で、特にれており、しかもそれらの解法も示されている。関連文

後半は「二分決定グラフ」（Binary Decision Diagram;

献は徹底的に調査されており、私の過去の論文の細か略称BDD） と呼ばれる、論理関数のデータ構造とアルなミスまで把握されている。さらには、ドミノ敷き詰め問ゴリズムが140ページに渡って詳細に解説されている。

題のルーツとして、江戸初期の和算の書「塵劫記」（初版1627年）が引用されているのには驚かされる。

一方、「ゼロサプレス型BDD」（Zero-suppressedBDD; 略称ZDDまたはZBDD） は、湊が1993年に考Knuth先生は、BDD（特にZDD）が、本当に気に入っ案・命名した技法で、大規模な集合族データを効率よくたようで、この章の執筆作業がとても楽しかったとメー

圧縮して表現し、高速に演算処理を行うためのBDDのルに書かれていた。その気持ちは、本の内容からも伝わ改良技法である。BDDの改良技法はこれまでに多数提ってくる。研究者にとっては、自分が考案したアイデアの案されているが、Knuth先生はその中で特にZDDの重面白さを他者に共感してもらうことが大きな喜びであ

要性を認識され、BDDとZDDを同格に扱い、章の後半るが、偉大なKnuth先生とそれを共有できたことは、私

部分30ページ以上を割いて、ZDDの解説や演習問題をにとって最高の幸せだと感じている。

載せている。さらにKnuth先生は、昨年、米国スタンフォ

今回の掲載内容は、私が15年前に考案した技術が元ード大と英国オックスフォード大で、「Fun with ZDDs」になっているが、それだけでなく、ZDDを応用したデーというタイトルで特別講義を行っており、ZDDの重要性

タマイニングのアルゴリズムなど、北大・情報科学研究科を指摘されている。

で行った最近の仕事も引用されている。Knuth先生からさて、校正作業の過程で、私はいくつかの字句レベルは、私のこれまでのZDDに関する継続的な取り組みをの誤りの指摘と、アルゴリズムを読みやすくするための高く評価されていた。北大での研究活動でお世話になっ改善提案を送った。程なくしてKnuth先生より封書が届た先生方に心から感謝するとともに、今後も変わらぬごき、中から出てきたのは、使い古しの紙の裏面に、私が指導・ご協力をお願いする次第である。

送った電子メールの文面を印刷して、そこにKnuth先生が鉛筆書きで、技術的な確認事項などをびっしり書き込‫࠰ࡖࡠݤ‬ɅȤȫɥ৙ߔृ८ဘɈဲ੍ɅȾȞɀ

んだ手紙だった。さらに、先生のサインが入った2ドル少々の小切手が同封されていた。Knuth先生の有名な夏季期間における連続休暇取得の奨励並びに省エネ逸話として、彼の著書の誤りを指摘すると2.56ドル（=ルギー対策のため、平成２１年８月１２日（水）から１４日28セント）、改善点を指摘して採用されると32セントの（金）の３日間、工学系建物の閉鎖を実施します。
（対象：謝礼の小切手を支払う約束になっている。この小切手は工学研究科・工学部、情報科学研究科、エネルギー変換「コンピュータ業界の最高の栄誉」とされていて、ほとんマテリアル研究センター、量子集積エレクトロニクス研

ど誰も換金する人はいないそうである。
（当然、私も大究センター、ベンチャー・ビジネス・ラボラトリー、環境ナ事に持っている。）なお、昨年11月以降は、金融危機の影

ノ・バイオ工学研究センター、トポロジー理工学教育研

響等により、現実の小切手を振り出すのは止めて、架空究センター）の銀行に2.56ドル入金したことを示す証明書を送るこ

なお、期間中は、原則的に年末年始の期間と同様の体とにしたそうである。私は架空銀行の証明書も頂いた制となり、対象組織が休業となります。郵便物は、郵便局が、それには 0x$1.00（Hexadecimal Dollars）と記留となりますので受領および発送等の取扱いは、８月１７

載されていて、そのユーモアとこだわりにKnuth先生ら日（月）からとなり、宅急便は、原則警備員室にて受理・しさが表れている。

保管となります。事故等の対応は、緊急連絡体制に従うこととなります。皆様、ご協力くださいますようお願いしKnuth先生の精力的な仕事ぶりは、とても70歳を過ます。

ぎた人間とは思えない。ただただあきれるばかりである 。こ の 章 を 執 筆 す る 際 に も 、極 め て 効 率 の 良 い
BDD/ZDD演算処理系を自らコーディングされて、独自Ľ3Ľこれらの機会を、ご関係の方々との交流の場として活ိ౰32༃๱‫ྣ࢞ॸߔݨ‬ၒ஝ࣸੜ൰௻࣍

用していただければと考えておりますので、多くの皆さんのご参加をお待ちしております。

情報科学研究科からは下表の６８件が採択され、総額２億６４４０万円の交付が内定しました。
種 目
特別推進研究特定領域研究新学術領域研究
基盤研究（A）
基盤研究（B）
基盤研究（C）
挑戦的萌芽研究
若手研究（A）
若手研究（B）
計

新規
０
１０２
９５
１
１
９２８

継続
１４
１５７
７
６
１８４０൦Ǎ‫ޑ‬ଭ଴ॸ࢞ଞɅɢɥ
ඪɈ೯୸ɈȹɛɈ‫ڽ‬ယᄘࢼວʓʷʢĜၡਠ

計
１
５
１
７
１６
１２
７
２
１７６８

4月25日（土）から26日（日）の日程で、グローバルCOEの支援を受けて、定山渓ビューホテルにて学生主体の共同セミナーを開催しました。
本セミナーは、主題として「第1回若手研究者による知の創出のための異分野共同セミナー」を掲げ、ナノエレクトロニクス・情報・メディア・バイオの各領域の学生の異分野間交流を目的として開催されました。
本セミナーは、参加学生によるポスターセッションをTdjfodfɅĶᆲાɜȾɦʭɻ˃ʗĜķऻ੪

中心に、3件の招待講演および各研究室代表による研究

情報エレクトロニクス専攻光システム計測研究室（協室紹介講演、民間企業の方をお招きしての座談会、グル力講座）の竹内繁樹教授らは、世界最大規模の光量子回ープディスカッションと、非常に密度の高いものとなりま路「量子もつれフィルター」を開発し、その成果が米国科した。

学雑誌Science に掲載されました（ An Entanglement

参加者は、大学院学生45名、教員9名、招待講演者3名

Filter , vol.323, p483, （2009））。本研究は、同研究室を数え、両日を通して非常に活発な議論を交わすことがの岡本亮助教、笹木敬司教授、情報科学研究科博士後期できました。

課程の永田智久さん、および英国ブリストル大学、広島大

参加学生の義務としたポスターセッションでの議論で学と共同で行われました。量子情報処理が、部品を組みは、学生が積極的に他分野の学生との討論を楽しむ様合わせ、機能を発現する「回路」を構築できる段階に達し子が見られ、招待講演においても、特に講演者とは異なたことを示す成果であり、将来の量子コンピュータや超る分野の学生からの質問が活発に行われ、時間を超過長距離の量子暗号の実現につながるものです。

するほどでした。
本セミナーの成功は、参加学生の熱意はもとより、私たち学生を信頼して計画のほぼ全てを任せてくださっHDPF଱੓Ɉਡ໘ʏˋʵʐɾʸɂ႘ᛊ‫ޏ‬ၚ৫ৄᆔ‫ޏ‬

た先 生 方 、そして両日セミナーを支えてくださった
GCOE事務局の皆様の尽力によるものです。ここに謝グローバルCOEプログラム「知の創出を支える次世意を表したいと思います。

代IT基盤拠点」（拠点リーダー：有村博紀）では、昨年度（情報科学研究科GCOE RA、猪村 元）に引き続き、若手研究者支援のための産学協同GCOE
国内シンポジウムを、2009年9月30日、10月1日の2日間、京王プラザホテルにて開催予定です。本シンポジウ

௶ၡ‫ݨ࢞ॸߔݨ‬fˁĜʣˋʈ࣋੮౲ྩ௻࣍

ムは、国内にある多くの研究機関、企業、関連大学等向けに、本プログラムの成果発表だけではなく、博士後期本研究科では、大学院特論講義を対象にｅラーニング課程の学生や、ポストドクターのアクティビティを具体的教材の製作を進めています。昨年度末の時点で利用可に紹介することを目的としています。

能な20科目に加え、今年度1学期は7科目について教材を製作しています。科目名等の詳細については情報科

また、引き続き、10月2日には、各方面で活躍されてい学研究科ホームページをご参照ください。

る卒業生の方々との意見交換の機会である北楡会の母校交流会が企画されています。
Ľ4Ľ

【人事異動】[教授]（昇任）平成2１年６月1日
今井 英幸
コンピュータサイエンス専攻
数理計算科学講座（同講座 准教授より）[准教授]（昇任）平成2１年６月1日
工藤 信樹
生命人間情報科学専攻
生体システム工学講座（同講座 助教より）（採用）平成21年４月１日
上野 貢生
生命人間情報科学専攻（協）生体機能工学講座（北海道大学電子科学研究所 特任准教授より）【受賞】
2009年３月2５日
ジョーダン チャールズ ハロルドコンピュータサイエンス専攻 修士課程２年（当時）
電子情報通信学会北海道支部 平成20年度電子情報通信学会北海道支部学生員奨励賞 The Classiﬁcation
Problem in Relational Property Testing
2009年３月2５日
藤井 孝史
情報エレクトロニクス専攻 修士課程２年（当時）
電子情報通信学会北海道支部 平成20年度電子情報通信学会北海道支部学生員奨励賞「透過電子顕微鏡を用いたPr0.7Ca0.3MnO3薄膜の伝導特性評価の研究」

ఛ࣋ۙ௘‫ގ‬１．最終学歴および学位、2．前職、3．専門分野
今井 英幸 教授
コンピュータサイエンス専攻 数理計算科学講座
１．昭和６２年北海道大学大学院工学研
究科情報工学専攻修士課程修了、博士（工学）２．コンピュータサイエンス専攻数理計算科学講座 准教授
３．多変量解析学、情報解析学
工藤 信樹 准教授
生命人間情報科学専攻 生体システム工学講座
１．昭和６２年北海道大学大学院工学研
究科生体工学専攻博士課程修了、博士（工学）
２．生命人間情報科学専攻 生体システ
ム工学講座 助教
３．医用超音波、医用光学
上野 貢生 准教授
生命人間情報科学専攻 （協）生体機能工学講座
１．平成１６年北海道大学大学院理学研
究科化学専攻博士後期課程修了、博士（理学）２．北海道大学電子科学研究所 特任准教授
３．光ナノテクノロジーʭʁʠʆʻˁ˂Ĝ

2009年３月2５日
斉藤 裕大
メディアネットワーク専攻 修士課程２年（当時）
電子情報通信学会北海道支部 平成20年度電子情報通信学会北海道支部学生員奨励賞「仮想MIMOシステ
ムを用いた上り回線における固有ビーム伝送特性」
2009年３月2５日
平松 朋樹
メディアネットワーク専攻 修士課程２年（当時）
電子情報通信学会北海道支部 平成20年度電子情報通信学会北海道支部学生員奨励賞「悪天候時に撮像された車載カメラ動画像の復元に関する研究」

図２：量子もつれフィルター（本文P3より）2009年３月２５日
吉田 龍一
メディアネットワーク専攻 修士課程２年
電子情報通信学会北海道支部 平成20年度電子情報通信学会北海道支部学生員奨励賞「フォトニック結晶ファイバを用いた温度制御型光デバイスの構成法に関する研究」

図３：共同セミナー招待講演会場の様子（本文P3より）記事の詳細及びこちらで紹介されていない記事については、情報科学研究科ホームページ、工学部広報ホームページをご参照ください。
○情報科学研究科ホームページ
http://www.ist.hokudai.ac.jp/news/○大学院工学研究科・情報科学研究科・工学部広報ホームページ
http://www.eng.hokudai.ac.jp/news/publication/news/

2009年４月１３日
横田 幸恵
生命人間情報科学専攻 博士後期課程３年
日本化学会 第８９春季年会学生講演賞「ナノギャップ金構造による増強ラマン効果」

ＩＳＴ ＮＥＷＳ No.18

2009年４月１８日
齊藤 晋聖
メディアネットワーク専攻 准教授
財団法人 船井情報科学振興財団 平成20年度 船井情
報科学奨励賞「フォトニック結晶ファイバの高度利用技術の開発に関する研究」

平成21年7月15日発行

発行：北海道大学大学院情報科学研究科 広報・情報室（編集担当：吉岡真治・浅井哲也・佐藤健二・小山内詔子）
情報科学研究科ホームページ
http://www.ist.hokudai.ac.jp/
Ľ5Ľ