情報科学講座 第01回「Np完全問題 -001-」

 iPhone4S上で育成シミュレーションゲーム「おさわり探偵 なめこ栽培キット」をプレイしていて出会ったNp完全問題について記述する。

これまでの軌跡
 あまりにも有名になりすぎてしまったため、話題に乗るためにやらざるを得ない状態になってしまったことから、私はこの「なめこ」と付き合うことになった。そして、プレイし続けた結果、このNp完全問題と出会った。

Npについて
 Np(Nameko Point)とは、このゲームにおける通貨の単位である。プレイヤーはなめこを収穫する際にこれを得る。得られるNpはなめこの種類によって予め定められている。なめこフードを始めとする道具類を購入、使用する際にこれを失う。

Np-complete

図1


Np完全問題
 Np完全問題とは、なめこを収穫してもNpが増えなくなる問題である。私はただただなめこを収穫したい一心でここまで励んできたのに、この問題に心を打ち砕かれた。そう、いくら頑張ってもNpが増えないのである。
 この状態に陥った際のスクリーンショットが図1である。なめこが今を春べと咲き誇っているのに、ここでなめこを収穫してもNpは全く増えない。なめこ飽和状態である。
 ちなみに、表示上のNpと内部変数のNpは一致しているらしい。過剰収穫を行った後、何らかの操作でNpを失うと、正確にその分を引かれたNpが表示された。したがって、「表示上は999999Npだが内部ではちゃんとカウントされている」ということはない。また、「999998Npの状態で6Npを獲得すると999999Npになる」ことも確認できた。

回避策
 Np完全問題に陥らないようにする唯一の策は、この上限値999999Npを常に意識し、なめこを収穫し過ぎないようにすることである。困難なことではあるが、今のところこれ以外の方策は発見されていない。これからなめこをプレイする人は気をつけたほうがいい。

注意
 なお、この問題はNP完全問題とは関係ないことに注意されたい。

参考: NP完全問題 – Wikipedia

[2012/06/23] Googleホリデーロゴがチューリングマシンに!

Google Holiday Logo Turing Machine

Google Holiday Logo Turing Machine


 2012年06月23日の今日は我らが祖、アラン・チューリングの生誕100周年! これに合わせ、Googleのホリデーロゴがチューリングマシンになっていた!

 橙色のボタンを押すとプログラムを変更でき、緑色のボタンを押すとこれを実行できる。実行後のテープの状態が右上のものと一致していたら、Googleのうち1文字が点灯する。6つ全部に正解してGoogleをすべて点灯させよう!


 アラン・チューリングはイギリスの数学者であり、計算機科学者でもある。世界初のコンピュータが登場する10年前にコンピュータの理論的な限界を示したことで有名。彼はコンピュータを先取りした概念で理論的なモデルを考えた。このシンプルなモデルはチューリングマシンと呼ばれた。

 このチューリングマシンというものは、次の3つで構成される。

  • 1. 無限の長さを持つ記録テープ
  • 2. 1に情報を書き込むヘッダ
  • 3. 機械の内部状態を記録するメモリ

これらの上でチューリングマシンは以下のように動作する。

  • 1. テープ上のヘッドの位置に情報を書き込む
  • 2. 機械の内部状態を変える
  • 3. ヘッダの位置を左右に1つ移動する

 本日のGoogleのホリデーロゴはこのチューリングマシンを模したもの。彼はたったこれだけの構成と動作でコンピュータを表現したのだ。

 彼の功績をたたえ、情報科学・計算機科学の分野では「チューリング賞」(ノーベル賞みたいなもの)が創設されている。彼なくして今のコンピュータ及びその理論は成り立たなかったと言っても過言ではない。

 彼は暗号解読の分野でも仕事をしており、あの有名な暗号機「エニグマ」の機械による解読も成し遂げた。


[参考] アラン・チューリング – Wikipedia
[参考] チューリングマシン – Wikipedia

情報検定(J検) 情報活用試験 1級 受験記録

 2012年06月17日に「PBT方式(ペーパー)平成24年度前期試験」を受験した。本検定の受験は初めて。試験の概要や方式などの情報は、公式サイトやWikipediaを参照して欲しい。


1. 申し込み
 申し込みの際には、受験票が届く期限がWebサイトのどこにも示されていなかったため不安を感じた。

2. 当日: 試験会場
 会場は横浜を希望し、岩崎学園情報科学専門学校だった。六階の小さな教室で、受験者は20人程度だった。試験官は会場校の教員1人で、受験者には会場校の学生が多かった。問題冊子は持ち帰ることができた。

3. 当日: 試験内容
 今回の試験は例年に比べてやや難しめだった印象を受けた。J検は定義が緩く曖昧な問題が多いので、想像や運を駆使しなければ満点が取れないというのが私の認識である。

4. 当日: エピソード
 今回の試験問題では問題文にミス(ABC分析で1箇所、ユーザ認証で1箇所)があり、私の右に座っていた学生が試験後に試験官である教員に質問をしていた。その教員がミスを否定していたのには幻滅したが、学生が賢かったのはよいことだ。

5. 当日: 出来栄え
 試験の出来はそこそこ。曖昧な問以外は自信を持って回答できた。電卓、消しゴムは持参していたが使わなかった。

6. 結果
 試験翌日の19:00ごろにサイトに解答が掲載された。自己採点の結果、2問誤答していることが分かった。点数で言えば95点くらいか。満点を目指していただけにショックが大きい。
 と、思っていたが、実際には誤答は1問で、98点での合格だった。満点でない時点で同じ事である。カードサイズの合格証を自分で印刷することができた。いわゆる合格証書や合格証明書の類は、追加で購入しなければ手に入らない。


[参考] 情報検定:J検
[参考] 情報検定 – Wikipedia

ZAGGkeys Flex レビュー

 「ZAGGkeys Flex」を定価で買った。ZAGGと言えばスマートフォンなどの保護フィルムで有名だが、同じスマートフォン用でキーボードもいくつか出している。今回買った「ZAGGkeys Flex」は、軽量、薄型、多機能が売りのキーボード。公開仕様や一般的なレビューは他のサイトに任せるとして、購入前に私が気になっていた点について書こうと思う。


1. キーピッチ
 メーカーの仕様表に載っていない。[A]キーの左端から["]キーの左端の距離を10で割って実測したところ、17mmぴったりだった。

2. ストローク
 これもメーカーが公表していない。ノギスでの実測で1.8mmだった。抵抗がリニアでなく、「クッ」と押した感じがわかる。パンタグラフのような音がする。音が好きではないが、この手の商品にしては打鍵感は気に入った。

3. 重量
 軽い。誰が持っても、文句なしに軽いと言えるだろうと思った。

4. 形状
 本体裏側の左右の端が、指一本分くらいの幅でくぼんでいる(そこだけ薄いので机から浮く)。そのおかげで、机からキーボードを取り上げるときに引っかかりがあって持ち上げやすい

5. 欠点
 色がシルバーの一色しかない。同じシリーズのSoloは3色あったので、黒も出して欲しいところだ。また、充電用のUSBポートが本体上部にあるのだが、ここはケース収納時に隠れる場所である。したがって、ケースに収納したまま充電を行うことができない

6. LED
 LEDは全部で3つ。Charge, Status, CapsLockだ。色は残念ながら、それぞれ青、赤、緑だ。Chargeは充電中に点灯し、充電が完了すると消灯する。Statusは電源を入れた直後に2・3秒点灯して消えるほか、ペアリング中点滅し続ける。CapsLockはロック中点灯する。

7. 総評
 展示品がない状態での購入は賭けに近かったが、結果としてはいい買い物ができたと思っている。購入して帰宅した後、この記事を書こうと思ってAmazonを見たら値段が1割も下がっていたのには動揺を隠し切れない。


[参考] ZAGGkeys FLEX | Wireless Bluetooth Keyboard & Stand for Tablets | ZAGG Japan
[参考] Amazon.co.jp: ZAGGkeys FLEX Bluetoothキーボード「国内正規代理店商品」 for iOS/Android(iPad,iPhone,Galaxy,Acer Asus Eee Pad…etc)