情報科学なんでもセミナー

平成 18 年 9 月までのセミナー記録．

平成 18 年度 秋休み

• 秋の特別編 2006
  • 射影空間における凸概念について（戸田）
  • 多項式時間解法の存在の非構成的証明（小林）

平成 18 年 4〜8 月

• 第 50 回 Time/Space Lower Bounds（バーク）
• 第 49 回 アンラッキーテトリス製作秘話（野村）
• 第 48 回 超現実数の定義と応用（平井）
• 第 47 回 プログラミング言語 H 概論（柴田）
• 第 46 回 Ruby on Rails 30 分 Hacking（斉藤）
• 第 45 回 Haskell とモナド（田中）
• 第 44 回 カンボジアレポート（岡本）
• 第 43 回 くすりとコンピュータ（桜庭）
• 第 42 回 計算領域への折り返しとアクセス（上野）

平成 18 年 1・2 月

• 第 41 回 ゲーム大好き♪（池上）
• 第 40 回 3D Visualization（& 女子大生）（森）
• 第 39 回 アメリカの大学院への留学（恐神）
• 第 38 回 自転車について考える（牟田）
• 第 37 回 量子コンピュータ入門（樋口）

平成 17 年 9〜12 月

• 第 36 回 “アイ・ティー”業界で働くための基礎知識 〜眠れないエンジニアにならないために〜（佐々木）
• 第 35 回 コンピュータオセロ 〜人類を超えた知能〜（海野・大倉・林崎・藤田）
• 第 34 回 タッチタイピングについて考える（中山）
• 第 33 回 TRON プロジェクトの過去・現在・未来（矢代）
• 第 32 回 在線 k 服務者問題（河村）
• 第 31 回 韓国のオンラインゲームとプロゲーマ（辛）
• 第 30 回 C# と Cω（山崎）
• 第 29 回 NLG（自然言語生成）の技術（中西）

平成 17 年度 秋休み

• 特別企画 秋の実演特集 NanDEMO 2005（終了）

平成 17 年 4〜7 月

• 第 28 回 どこでも Let's make 〜 はじめての Autotool（今井）
• 第 27 回 鉄道とコンピュータ 第 2 回（横山）
• 第 26 回 噂の colinux（西鳥羽）
• 第 25 回 教科書には載らないニッポンのオンラインソフトの歴史（稲葉）
• 第 24 回 DTM と MIDI 入門（阿部）
• 第 23 回 検索と圧縮──Compressed Suffix Arrays/Trees（岡野原）
• 第 22 回 HyperTransport（西川）
• 第 21 回 文字コード（川中）
• 第 20 回 次世代ゲーム機のアーキテクチャ研究（石井）
• 第 19 回 ベイズ推定とその応用（中嶋）
• 第 18 回 折紙展開図解析演習（舘）
• 第 17 回 おうちでサーバ。（吉野）
• 第 16 回 与太話の作り方 〜サルだから書けるストーリー〜（柴田）
• 第 15 回 計算量クラスに対する演算子（上野）

平成 17 年 1〜3 月

• 第 14 回 情報科学における形状の表現と処理（海野）
• 第 13 回 デザインパターン$(0!9!9アホでマヌケなプログラミングをぶっとばせ(B（川中）
• 第 12 回 絵を描く（渡辺）
• 第 11 回 ベクトル指向のすすめ（吉野）
• 第 10 回 テクノ・ミュージックとヒューマン・コンピュータ・インタラクション（川崎）
• 第 9 回 サルでも作れるカーネルモジュール（今井）
• 第 8 回 分岐予測（石井）
• 第 7 回 言語学における科学（吉川）
• 第 6 回 Flash と情報科学（遠藤）
• 第 5 回 イベント駆動型プログラミング（西田）
• 第 4 回 C++ Templates 2005（稲葉）

平成 16 年 12 月

• 第 3 回 鉄道とコンピュータ（横山）
• 第 2 回 ゲーム考 〜シューティングゲームを情報科学する〜（柴田）
• 第 1 回 実関数の計算量と最大値問題（河村）

秋の特別編 2006

開場：午後 2 時 45 分（コーヒー・お菓子とかがでます）

午後 3 時 10 分〜
射影空間における凸概念について
戸田 貴久（富士通研究所）

射影空間において自然にあらわれる凸概念とはいかなるものであるか？  本研
究では、実ユークリッド空間における凸性を一般化し、実射影空間において、
単純局所凸集合、および、その一般化である局所凸集合の概念を導入した。ユー
クリッド空間の凸集合に関する組合せ幾何でもっとも有名な定理の１つである
ヘリーの定理が、実射影空間の局所凸集合に関する一般化された定理として示
される。これは、射影空間の双対性を用いる計算幾何学の問題に応用されるこ
とが期待される。

午後 4 時 30 分〜
多項式時間解法の存在の非構成的証明
小林 佑輔（東大 数理情報学専攻 M2）

ある問題がクラスPに属することを示すには, その問題に対する多項式時間アル
ゴリズムを実際に構成すればよい. しかし, 多項式時間アルゴリズムが知られ
ていないにも関わらず, クラスPに属することが示されている問題も存在する.
本発表ではこのような性質を持つ問題を紹介する.

なお, 内容は主に下記の文献の紹介になる予定である.
M. R. Fellows and M. A. Langston, "Nonconstructive Advances in
Polynomial-Time Complexity", Information Processing Letters, 28
(1987/88), 157--162.

第 50 回 Time/Space Lower Bounds

Abstract

Computational Complexity Theory attempts to classify the inherent complexity of certain problems with regard to certain resource bounds such as time and space. Despite much effort we have very few provable complexity class separations. However, there have been some interesting partial separations in the form of time/space lower bounds on certain problems.

In this presentation we discuss the fundamentals and survey the general techniques of these results.

第 49 回 アンラッキーテトリス製作秘話

場所が前回と違います．ご注意ください．

概要

テトリスを遊んだことがある方は、嫌なブロックがたて続けに降ってくる、欲しいブロックが来ないなど、「コンピュータが意地悪をしているに違いない！」と思わされるような不運を何度か経験したことがあると思います。「アンラッキーテトリス」はそのようなジンクスを意図的に発生させるテトリスです。

「アンラッキーテトリス」の作品紹介として、意地悪なブロック決定アルゴリズムの説明、西田研 M2 の師氏と共同開発した前作「チートテトリス」との比較、完成品のデモなどを行います。

前提はテトリスのルールの知識と出来ればプレイ経験です。

第 48 回 超現実数の定義と応用

曜日・開始時刻・場所が前回と異なります．ご注意ください．

概要

Donald E. Knuth による数学小説『Surreal Numbers: How two ex-students turned on to pure mathematics and found total happiness』の題材である超現実数を紹介します。

超現実数は、任意の実数よりも大きな数をたくさん含み、たくさん含みすぎて、もはや集合ではない、怪しい体系です。美しい定義と、無さそうで有る使い道を説明します。

前提知識はとくにありません。なお、total happiness の発見は保証しません。

第 47 回 プログラミング言語 H 概論

開始時刻が前回と異なります．ご注意ください．

概要

Microsoft 主催のプログラミングコンテスト ImagineCup で昨年・今年採用された Herbert はプログラミング言語 H という専用のロボット記述言語を使用します．そのプログラミング言語 H について簡単に説明し，過去の問題を参考にプログラミング技法について学びます．またプログラミング技法のみならず，問題解決の上でどこに着目すべきかという点についても，実際の問題を考慮しつつ議論します．

第 46 回 Ruby on Rails 30 分 Hacking

開始時刻が前回と異なります．ご注意ください．

概要

Ruby on Rails は Web アプリケーション開発のためのノウハウが集積されている フレームワーク＆ライブラリです。今回は、Rails や Web アプリケーション開発の 基礎について説明し、実際にRailsを用いて、30 分間で、wiki を実装するデモを 行います。ファイル添付機能付き、さらに、AJAX を使った wiki の dynamic preview 機能などにも挑戦します。

Ruby や SQL を使用しますが、これらについて知らなくても、理解の上で支障は ないかと思います。

第 45 回 Haskell とモナド

開始時刻が前回と異なります．ご注意ください．

概要

近年、Haskell というプログラミング言語がにわかに注目を集めています。なぜ今 Haskell なのか、純粋関数型とは何なのか、他の言語とはどう違うのか。今回は、Haskell を理解し利用する上で非常に重要な概念であるモナドについて、 詳しい解説を行い、実際の応用例を見て行くことによりその有用性を示します。

基本的な関数型言語の知識を前提とします。

第 44 回 カンボジアレポート

概要

池内研で毎年行われてきたカンボジア・アンコール遺跡の 3D 計測。 その過酷な計測作業の内情から、カンボジアのおすすめ観光スポットまで幅広く紹介する。

第 43 回 くすりとコンピュータ

概要

くすりは現代のコンピュータプログラマの眠れぬ夜と穴だらけの胃を支える重要な要素である。 薬学部薬学科出身の話者が、薬の正しい知識と、コンピュータの創薬分野への応用について解説する。

前提とする知識は特にありません。

第 42 回 計算領域への折り返しとアクセス

日程が変更されました．ご注意ください．

概要

折り返し計算量は、時間・領域計算量とともに本質的な計算資源として研究されてきた。 これに対してアクセス計算量という新たな計算資源を導入し、 折り返しとアクセスの違いが“L versus P”問題と関連していることを説明する。 さらに、折り返しとアクセスの違いについていくつかの結果を紹介する。 仮定する予備知識は、チューリングマシンの概念のみである。

第 41 回 ゲーム大好き♪

曜日と部屋が前回とは異なります．ご注意ください．

概要

皆さんの中にはゲームが好きな人が多数いらっしゃると思いますが， 今回考えるゲームは無限ゲームと呼ばれるものです。 通常，ゲームは有限回で勝敗がつくか引き分けになりますが， 無限ゲームでは無限回手を出してから勝敗が決まります。 今回は，無限ゲームの基本的な性質とその応用について紹介したいと思います。 予備知識は特に何も仮定しません。

第 40 回 3D Visualization（& 女子大生）

概要

3 次元ボリュームデータを可視化するには どのような手法があるのか概略を説明し、 その中で自分の研究テーマも少し紹介する。

閑話休題として、 女子大時代のさまざまな話も盛り込む予定。

第 39 回 アメリカの大学院への留学

概要

昨年カーネギーメロン大学コンピュータサイエンス学科で博士号を取得した 経験を踏まえ、アメリカの大学院とはどのようなものかをお話します。 アメリカで博士号を取得するメリット、アメリカの大学院とはどのような ところか、アメリカの大学院に入学するにはどうしたらよいか、などの 疑問にお答えします。必要とする前提知識はありません。

第 38 回 自転車について考える

概要

最後に自転車に乗ったのはいつですか？ 今回は現代人が陥りがちな運動不足を自転車で解決する方法について、 1．旅行に出かける、2．通勤に自転車を使う、この両方を 実体験をまじえながら話したいと思います。 レンタサイクルやママチャリで始められるレベルに抑えて話しますのでどうぞご参加下さい。

第 37 回 量子コンピュータ入門

概要

現在計算機の中で行われている計算は，0 と 1 の配列に“あるルール”を適用 する，という形で行われています．それではそのルールはどのような要請のも とで出来上がっているのでしょうか．それは，モノがあるかないかを最小単位 として扱う古典物理学のルールが決めていることなのです．

量子力学は，モノがあるかないかだけではなく，モノがどのような状態にある かまでを記述する方法です．特に計算においては，状態の重ね合わせが許され る，ということが大きな意味を持ちます．この重ね合わせにおいて，ある種の 物理的に可能な変換（Unitary 変換）を通しても，重ね合わせた複数の情報の 相関が失われないために，ある種のアルゴリズムにおいて古典的計算機よりも 飛躍的にステップ数を減らすことができます．

今回の発表では，量子力学について立ち入った話はしませんが，計算機理論に おいて必要な最低限の数学的な準備と，因数分解を多項式時間で解ける Shur の 因数分解アルゴリズムについてお話します．量子コンピュータの物理的実現に ついては，時間が許せば紹介します．

前提知識としては，教養程度の線形代数を必要とします．

第 36 回 “アイ・ティー”業界で働くための基礎知識 〜眠れないエンジニアにならないために〜

概要

情報科学を学ぶ学生の中には、アイ・ティー業界で仕事をすることに興味を持って いる人がいるかもしれません。また、研究者の立場として業界の中をちょっとは 知りたい、という人もいるかもしれません。そんな方々を対象に、“業界の中の人の 視点”で SE ってなに？のような基本的なお話をします。

第 35 回 コンピュータオセロ 〜人類を超えた知能〜

曜日と部屋が前回と違います．ご注意ください．

概要

オセロゲームはルールが簡単なことから、人工知能研究の題材として長く用いら れてきました。今やコンピュータオセロは人間が到底勝利できない強さにまで到 達しています。今回は、IS2004 有志により作成された世界レベルのオセロプログ ラムの実装を中心に、コンピュータオセロの歴史や現在のトレンドについて解説 します。

前提知識としては、オセロゲームのルールおよび、完全情報零和ゲームの AI に関 する基本的な考え方（minimax や α-β）を理解していることを想定しています （情報科学科 3 年の「知能システム論」で習う程度の範囲で十分です）。

第 34 回 タッチタイピングについて考える

曜日が前回と違います．ご注意ください．

概要

普段私たちがコンピュータを扱う際、何気なくこなしているタッチタイピングに ついての話をします。具体的な内容としては、 入力方法に関する話題では QWERTY 配列と Dvorak 配列、 ローマ字入力とカナ入力の比較と考察を、練習ソフトに関する話題では 「正確性」と「速度」という、2 つの重要な要素からソフトの分類をし、また更に タイピング「対戦ゲーム」について紹介を行います。

前提とする知識は特にありません。

資料

• スライド：PowerPoint．

第 33 回 TRON プロジェクトの過去・現在・未来

曜日・時刻が前回と違います．ご注意ください．

概要

最近、さまざまなメディアで TRON プロジェクトのユビキタス・コンピューティングに 対する取り組みが伝えられ、世間の注目を集めています。今回の発表では、 TRON プロジェクトが 20 年間の間、どのようにユビキタス・コンピューティングに 取り組んできたかをお話しし、さらにそれらの反省点をふまえて、どのような 方向へと将来向かっていくかについて考えてみたいと思います。

第 32 回 在線 k 服務者問題

曜日・時刻が前回と違います．ご注意ください．

概要

通常の算法は，入力が完全に与えられてから，答を考えます．これに対し，入力が時間の流れに沿って少しずつ与えられ，それに応じて逐次，未来の入力を待たずに即座に応答せねばならない状況が世の中にはしばしばあります．これを 在線計算（online computation）といいます．

とくに，何らかの費用を最小化する問題を在線計算で解くとき，未来の入力を知っているのと知らないのとでは費用が何倍違うかという比を，その算法ないし問題の 対抗率（competitive ratio）といいます．これは，未来を予知することにどれだけ価値があるかという尺度のひとつと考えられます．

このような在線最適化問題のひとつとして k 服務者問題（k-server problem）を紹介します．この問題の対抗率は未解決ですが，いくつかの特殊な場合については知られています．

第 31 回 韓国のオンラインゲームとプロゲーマ

曜日が前回までと違いますのでご注意ください．

概要

現在韓国ではプロゲーマという職業がかなり人気を得ています。 その謎のプロゲーマは何をやっているのでしょうか。いったいどんなゲームで食って生きられるのかについて語り、 そして韓国ではなぜオンラインゲームが流行っているのか日本ではなぜあまり人気がないのかについて話したいと思います。

第 30 回 C# と Cω

概要

最近発表された「C# 3.0」と、 C# をベースに Microsoft Research で研究がされている「Cω」を紹介し、 これら 2 つの言語における 関数型言語的要素・LINQ（Language Integrated Query）・同期処理機構 等を中心に 話します。

一般的なオブジェクト指向言語・関数型言語による プログラミング経験があることが望ましいです。 加えて、スレッド同期処理・SQL・XML 等の知識があると、 より理解がしやすいと思われます。

第 29 回 NLG（自然言語生成）の技術

概要

NLP の研究の多くは NLU（Natural Language Understanding）を目指していますが、 その逆を行く NLG（Natural Language Generation）も近年ようやく研究の枠組みが 固まりつつあります。 今回の発表では、NLG の概論を簡単にご紹介するとともに タスク非依存の NLG についてお話ししたいと思います。 N-gram モデルや CKY parsing をご存知の方はより理解しやすいと思いますが、 そうでない方でも大丈夫なように心がけます。

特別企画 秋の実演特集 NanDEMO 2005

概要

「情報科学なんでもセミナー」では秋の特別企画として標記の実演（デモ）特集を企画いたしました．普段のセミナーでは 1 人で一回分の登壇講演という形をとっていますが，今回は数分程度の短いネタも歓迎します．いつものとおり，分野・内容にもとくに制限はありません．「なんでも」奮ってご発表ください．多数の皆様のご発表をお待ちしております．

日程

• 発表申込締切：平成 17 年 8 月 27 日（土）
• NanDEMO 2005：平成 17 年 9 月 2 日（金）午後 4 時 30 分〜

プログラム

準備中．

懇親会

終了後には懇親会を予定しています（詳細が決まり次第お知らせいたします）．

発表申込

締め切られました．

発表賞

聴衆の投票により，発表賞を決定します．

組織委員会

稲葉 一浩，河村 彰星，西田 健志（chair），柴田 有

第 28 回 どこでも Let's make 〜 はじめての Autotool

概要

所謂 configure スクリプトを簡単に作るツール Autoconf と、 Makefile を簡単に作るツール Automake について話します。 必要な予備知識は Unix 上のシェルで基本的なコマンドが使える事です。 望ましい予備知識は B シェルスクリプト、gcc、GNU make の使用方法。 あと、ソケットや X11 等 ANSI の範囲外になる C プログラム 作成経験があると意義をご理解頂ける事と思います。

第 27 回 鉄道とコンピュータ 第 2 回

概要

前回 に引き続き、鉄道の情報科学的な側面を簡単に紹介する。 今回は

• 続・安全確保の基本
• 鉄道と数理（車両運用問題、運賃最適化問題など）

を取り上げる予定である。

第 26 回 噂の colinux

概要

プログラミングや TeX は Linux 上のほうがやりやすい。 でもプレゼン資料はパワーポイントがいい。 デュアルブートにすれば両方使えるがいちいち再起動するのはめんどくさい。

そんなあなたに Windows 上で Linux が動作するオープンソースソフトウェア colinux。 今回のセミナ〜では colinux の紹介、実演（できれば）、内部仕様等を発表します。

第 25 回 教科書には載らないニッポンのオンラインソフトの歴史

開始時間が前回より少し遅くなります．

概要

パソコン通信やインターネットを通じて流通する「オンライン ソフト」と呼ばれる種類のソフトウェアがあります。Microsoft の Office や Adobe の Illustrator などに代表される「パッケージ ソフト」とは異なり、オンラインソフトは主に個人や小規模な 団体によって制作され、公開されてきました。

今回は、そんなオンラインソフトの歴史について発表します。

※ 表題は「教科書には載らないニッポンのインターネットの歴史」からとりましたが、関連はほとんどありません。

第 24 回 DTM と MIDI 入門

時刻が前回よりも早いのでご注意ください．

概要

コンピュータ音楽の基礎のひとつである MIDI の概要を解説し、 ものすごく簡単にシーケンサーがどう動いているかを説明します。 また、実際にデータを作成する際の生楽器に似せるための小細工をいくつか紹介します。

前提とする知識は、中学校くらいの音楽の知識です。

第 23 回 検索と圧縮──Compressed Suffix Arrays/Trees

時刻が前回までと違うのでご注意ください．

概要

近年、インデクシング技術の一つである Suffix Arrays/Trees 関連の理論、工学的枠組みが急速な発展を遂げています。これらは更に圧縮技術とも結び付き、現実的で強力なインデクシング技術となりつつあります。今回はまだ論文になっていない最新の話題や、論文にならないような実用上の話も交えつつ説明したいと思います。 前提知識として文字列検索、データ圧縮の基礎が必要ですが、無くても大丈夫です。

第 22 回 HyperTransport

概要

AMD64 アーキテクチャで採用されている、プロセッサ・プロセッサ間およびプロ セッサ・チップセット間のインターコネクトである HyperTranport 技術について 概説します。HyperTransport の概要、PCI などの技術とはどこが違うのか、など を解説し、なにが Hyper なのか、を明らかにします。 前提知識は仮定していません。

第 21 回 文字コード

概要

文字を符号化する文字コードには、様々な規格が乱立しています。 これらの文字コードの(1)歴史や、(2) どのように符号化が行われている のか、(3)ほかの文字コードに変換するにはどうするか等についてお話し します。

前提知識は、特にありません。

参考文献は、『文字コード超研究』など。

第 20 回 次世代ゲーム機のアーキテクチャ研究

概要

次世代 Xbox も発表され、Nitendo や Sony も 次世代ゲーム機を発表することが予定されています。 次世代ゲーム機とは何が「次世代」なのでしょうか？ 現在各社から公開されている情報から 次世代ゲーム機の凄さを検証します。

前提とする知識は PS などの名前が分かる程度で十分です。

第 19 回 ベイズ推定とその応用

場所が前回までと違いますのでご注意ください．

概要

近年、スパムメールの自動フィルタリングに有効であるとして脚光を浴びてい る、ベイズ推定という手法があります。今回のなんでもセミナーでは、この手 法について簡単な解説を行います。また、応用対象であるスパムフィルタやコ ンピュータビジョンなどにおいて、これがどのように利用されているかについ ても概観したいと思います。

前提とする知識は高校程度の確率論です。

第 18 回 折紙展開図解析演習

概要

展開図というのは折紙の基本形を平面に広げ、その折り線の配置を示した図です。 一つの面上に全ての折り情報が記されているので、ほとんどの折紙構造がここからよみとれるはずなのですが、 概して展開図というのは初心者には分かりにくいものだったりします。 そこで展開図を読みとくためのコツについて語り、いろいろ実践して見るというのが今回の企画です。 演習なので各自折紙用紙を用意していただけると幸いかもです。

第 17 回 おうちでサーバ。

概要

近頃、常時接続環境の一般家庭への普及に伴い、自宅で Web サーバやメールサーバ などを運用する人が増えています。

レンタルサーバを借りれば、運用などは管理会社に任せられます。しかし、せっかく 常時接続回線があるのだから、自分で好きに設定できるサーバを持ちたいと思う人が現 れることは、至極自然な流れでありましょう。

とはいえ、サーバの設定となると、なんだかそれだけでめんどくさそうな感じがする のもまた事実。

今回は、実際に Web・メールなどのサーバを立ててみた経験談から、サーバを公開す るまでには何が必要なのか、をお話しします。

＃ちなみに、話者はこないだの週末にマシンを一台組んで、現在環境設定中です。

基礎知識としては、PC-UNIX 系のコマンドの基本（ls や cp が何をやるか等）です。 CUI でキーボード叩くのが大好きな方を歓迎します。

もしも Linux on VMWare などの環境を立ち上げられるようであれば、お供にして参 加すると、なおよいかもしれません。

第 16 回 与太話の作り方 〜サルだから書けるストーリー〜

概要

全てのヒトにとって時間とは有限なものに他ならないのですが、 その有限の時を必ずしも使い切るだけのモノがあるとは限りません。 いまやネットワーク技術の発展により、 有限の時を遥かに凌駕するだけのモノを得ることができるようになりました。 しかしそれよりも大分前の時代、ネットワークなどない時代、 人々は有限の時さえも無限に感じるくらいの手持ち無沙汰を感じていたのではないで しょうか？ そんな状況でヒトは何をするのか？ その一例についての話をします。

我々人間は有限の時の中を生きる存在でありながらも、 時として有限ではない何かを作り出すことがあります。 そんな無限の世界を垣間見ることをテーマにして、 第 16 回なんでもセミナーは話を進めていこうと考えております。

（※この内容は 4 月 4 日 17 時頃のものです。微妙に仕様変更があるかも知れません。）

第 15 回 計算量クラスに対する演算子

概要

計算量クラスに対して作用し新しいクラスを生成するようなもののことを演算子と呼 びます。今までに、P から NP を生成する演算子（NP＝∃・P）や coNP を生成する演算子 （coNP＝∀・P）などが研究されてきました。今回のセミナーでは、P、PSPACE の関数版 である FP、FPSPACE に対して、FP から FPSPACE を生成するような演算子を紹介します。 さらに、この演算子は一般に計算における時間と空間との間の関係を上手く特徴付け ていることを示します。前提とする知識は、チューリングマシンの概念と P、NP、 PSPACE の定義です。

第 14 回 情報科学における形状の表現と処理

概要

計算機で形状を扱うためには、 目的とする処理に適した表現形式を選んで記述してやる必要があります。 今回のなんでもセミナーでは、具体的に、 形状が CG、CAD、CV 界隈ではどのように表現されていて、 それぞれの表現形式はどういった処理に適しているのか、 事例をいくつか挙げながら概観したいと思います。

第 13 回 デザインパターン$(0!9!9アホでマヌケなプログラミングをぶっとばせ(B

概要

世の中にはたくさんのアホでマヌケなプログラムがあります。そのほとんど は、ちゃんとした作り方を知らないために、適当に作って泥沼にはまってしまっ たものたちです。今回は、アホでマヌケなプログラムにデザインパターンを適用 し、どのように修正するべきかを語ります。また、良く使われるデザインパター ンも紹介します。

第 12 回 絵を描く

概要

世の中のほとんどの人は年をとると共に絵を描かなくなります。 コンピュータに向かっていると益々絵を描くことを忘れてしまいます。 今回のなんでもセミナーでは鉛筆で絵を描くことと、コンピュータで絵を描くことの 双方についてお話したいと思います。

前提知識は特に必要ありません。 話者に絵の技術を求めてはいけません。

第 11 回 ベクトル指向のすすめ

概要

ベクトル処理とは、複数のデータに対して並列に同一の演算を行う処理のことです。 一例としては、MMX をはじめとする SIMD（Single Instruction Multiple Data）命令 などが挙げられます。 今回のなんでもセミナーでは、アルゴリズムをベクトル風に処理する手法についてお話 しします。

前提知識は、C 言語の構文が読めれば大丈夫です。 論理演算（AND、OR など）が大量に出てきますので、それぞれどういう論理になっている かをあらかじめ知っておくと聴きやすいかと思います。

第 10 回 テクノ・ミュージックとヒューマン・コンピュータ・インタラクション

概要

歴史的に見て、テクノロジーの進歩は常に音楽への影響を与えてきた。 今回は、この四半世紀ほどの間に広く普及してきた テクノミュージックとコンピュータの関係に焦点をあて、 ユーザインタフェース研究の観点から テクノミュージックのためのシステムをいくつか紹介する。

前提とする知識は特にありません。 映像中心の内容となり、いわゆる計算機科学的な内容は話さないと思われます。 あらかじめ御了承ください。

第 9 回 サルでも作れるカーネルモジュール

概要

Linux は他の現代的なOSと同様カーネルローダブルモジュールの 動的ロードをサポートしています。 これが、カーネルを再コンパイル、リンクする必要なしにカーネルの動作を変更する 事を可能にします。 多くのデバイスドライバがローダブルモジュールとして提供され、使用されています。 今回は、 Linux におけるローダブルモジュールの書き方と簡単な例を紹介します。 実用的なデバイスドライバやカーネルにおける実装の詳細は扱いません。 必要な予備知識は、基本的なCのコードを読める程度で十分です。

資料

• スライド：PDF
• サンプルコードなど

第 8 回 分岐予測

概要

分岐予測に関する歴史的な背景や 現代のプロセッサに使われている分岐予測器に関する話です。 前提知識はハードウェアに関しては特に必要ない（はず）です。 C++は少し読めると良いでしょう。

第 7 回 言語学における科学

概要

近年の自然言語処理の技術の発展はすばらしい。 計算機科学者にとっての自然言語研究においては、 計算に使用できる形式やそれを用いたアルゴリズムが中心となる。 今回は、それより少し低い階層に属する言語学そのものの中から、 チョムスキー理論を紹介する。 特に、重点はそれを支える科学的視点におくことにする。

※ 日本の（普通の）中学生程度に英語が理解できれば平気なように心掛けます。 また、チョムスキー理論の詳細に立ち入るつもりもなく、その概略を通して「科学」を 実感できればぐらいに思っています。私も詳細は知りません。

また、当日に認知科学や言語学に関連する書籍の紹介をしたいと思います。

第 6 回 Flash と情報科学

「曜日」「時刻」「場所」ともに，前回までとは違います．ご注意ください．

概要

Macromedia Flash（TM）は広く普及した、 インタラクティブなアニメーションを実現する マルチメディアテクノロジーです。 その開発の概念や発想、アプローチは、 Java アプレットなど情報科学をベースにしたものとは 大きく異なります。 Flash での開発の特徴やテクニック、情報科学との相違などを 事例を通じて紹介します。

※「この講演を聞くだけで Flash が作れるようになる」ということは多分ありません。

前提とする知識は、「Flash を再生してみたことがある」程度の予定です。

事例として使う（かもしれない）Flash です。 順不同、未完成のものもあります。

第 5 回 イベント駆動型プログラミング

概要

話者が User Interface 研究の一環として、 イベントを盛り上げるためのプログラムを書いた体験、及び 現在進行中・構想段階のプロジェクトについて紹介します。

学会を盛り上げるためのチャットシステム、 忘年会を盛り上げるための投票システム、 学園祭を盛り上げるためのエンタテイメントシステム などの話をします。

※ 前提とする知識は特にありません。

併設イベントについて

MessyWolf 大会（開発中ゲームの β テスト）は 開発の遅れにより延期となりました。 楽しみにしておられた方にはお詫び申し上げます。

第 4 回 C++ Templates 2005

概要

プログラミング言語 C++ の template 機能は、型に依らない処理を 関数やクラスとして記述するために追加されました。しかし現在では、 その後に発明された様々なテクニックやトリックによって、当初の 想定を越えて広く利用されています。今回は、この応用例の幾つかを 紹介します。

前提とする知識は、C++ か Java か C# のプログラムをなんとなくでいい ので読めること、です（template そのものについては発表中にも 説明します）。

資料

• スライド：PowerPoint．
• 配布資料：HTML．

第 3 回 鉄道とコンピュータ

概要

普段我々が親しんでいる鉄道は、とても多くの要素からなり 深く探求する価値のある世界である。 このセミナーでは、その中の情報科学的な側面を簡単に紹介する。 今回は

• 安全確保の基本──閉塞
• Longest Oneway-ticket Problem（SWA氏のプロジェクトによる）

を取り上げる。 なお、前提とする知識は 排他制御、整数計画法、グラフ上の（深さ優先）探索 である。

第 2 回 ゲーム考 〜シューティングゲームを情報科学する〜

概要

ゲームという世界のうち、一つのジャンルであるシューティングゲームについて考察します。 シューティングゲームと一口に言っても、何がそれに該当するのか、 該当するものの間にはどのような違いがあるのか？ ゲームがより一般的なものになり始めたファミコンの時代、 そのソフトウェアのうちのシューティングゲームを中心に、 シューティングゲームのシステムを一通り見た後で、 将来的なシューティングゲームの世界を考察します。

※ 話者は近年のシューティングゲームについては良く知りません。 意見をくださる識者を募集しています。

第 1 回 実関数の計算量と最大値問題

概要

「普通の」計算量理論は自然数など離散的な対象を扱う計算の複雑さを測りますが， これを応用する形で，実数から実数への関数についても計算量が定式化され， 葛［Ko82］によって調べられています． この理論を紹介します．

前半では， 実数をどのように表現して Turing 機械の枠組で捉えるかを説明し， 計算量を定義します． 後半では，閉区間上の多項式時間計算可能な関数の最大値を求める難しさが， 通常の計算量クラス P ?= NP の分離に関連づけられることを示します．

［Ko82］

Ker-I Ko. The Maximum Value Problem and NP Real Numbers. Journal of Computer and System Sciences, 24:15–35, 1982.

前提とする知識は，Turing 機械と（普通の）クラス P と NP の定義です．