ソートの計算量も，個数ではなく入力サイズで測るべきでは? 離散対数問題を検討したとき，法pで見ると線形時間になるけれど，実際には入力サイズで測らないといけないので，(準)指数関数になるということから，他のアルゴリズムでも厳格に入力サイズで測らな…

筆者が個人的に，ファンタジーの法則と呼んでいる問題解決法についてお話しましょう．ファンタジーというのは別世界と行き来する物語のことで，ファンタジーの法則とは，別世界と行き来することで問題をうまく解くという法則です． 【ファンタジーの法則】 …

整数のオーダを，入力サイズのオーダに変換する 昨日の続きです． 素数 とその生成元 ，そして [tex:1\le y という離散対数問題において， の候補を0から順に試して解を見つけるという「総当たり法」を実施すると，計算終了までの時間計算量は になる*1ので…

授業で「トロイの木馬Trojan horse」を説明していないことに，試験直前に気付きました． 大ポカです． 攻撃の仕方(やり取りされる情報の流れ)に関して，man-in-the-middle攻撃やreplay攻撃とまた違う興味深さがあるので，来年以降は取り入れるとします．

離散対数問題の時間計算量は「pに比例」じゃダメなの? ダメです．一言でその理由を説明すると，「計算量は，入力のサイズをもとに求めないといけないから」です． 順を追って説明しましょう．ここでは，離散対数問題*1を次のように定義しておきます．すなわ…

今日の1限に，情報セキュリティの試験を実施し，今期のこの科目はおしまいです． といっても，採点，模範解答の作成，JABEEエビデンス整備という作業が待っていますが． それと，P=NP問題に関する文章を出さないようにしていました*1が，明日から再開しますI…

Emacs22で，かな漢字変換kana-kanji conversionをスムーズにできるよう，~/.emacsに手を加えてみました． 日本語設定，かな漢字変換設定を貼り付けます． ところで，Emacs22はもともと，UTF-8のファイルをスムーズに編集できるようにとインストールしたので…

CとGNU開発ツールによる組み込みシステムプログラミング 第2版 テレビゲーム教育論―ママ!ジャマしないでよ勉強してるんだから 授業あるいはゼミで，プログラミングや情報技術の応用を語るときの参考資料になりそうです．扱っている対象は違いますが，ともに…

ふと，google:四六時中を調べてみました．上位から順に見て，興味深いものを並べます． http://gogen-allguide.com/si/shirokujityuu.html http://www.matikado-tantei.jp/archives/2005/10/post_92.html http://miroku.nomaki.jp/top.html http://oshiete1.…

文旦に話を戻すと，苗木は，三本の竹で支えるということをしてやるそうだ．竹を同じ長さに切り，それらをバランスよく組み，その間を苗木が通るようにするのである．もし三本の竹のバランスが崩れていれば，苗木はまっすぐに伸びず，根づきも悪くなる．文旦…

一つのシステムに複数のバージョンを入れていると，保守性に欠けますね．手元の環境で，いくつか調査しました．

今朝いいのが思い浮かばなかったので，晩の更新です． 昼間に書店で，語彙をつけるのによさそうな本を2冊，購入しました． 舊漢字―書いて、覺えて、樂しめて (文春新書) VOW〈19〉街のヘンなもの大カタログ 前者は，さまざまな旧漢字を取り上げています．旧…

その1 文献メモを作って集約するのは，データベースでインデックスを作るようなものです． 文献調査をしたら，その都度，文献メモを作っておきます．それと，冊子の中にある論文は，コピーをとってそれを手元に置いておき，冊子は本棚に戻すなり，借りた人に…

ちょっと昔話を． ユークリッドの互除法を使って，最大公約数を求めるプログラムを，ある学生が書いていました．しかし期待する出力になりません． コードを再現すると… int gcd(int a, int b) { int r = a % b; if (r == 0) { return b; } gcd(b, r); } 再…

学生による教育再生会議 (平凡社新書) 学力問題，教師への支援，学校選択制，教育委員会のあり方について，文献調査や当事者(教員，教育委員会職員)へのヒアリングを通じて，現状の問題点を浮かび上がらせるとともに，対案を提示しています．政策として採用…

今日は2問．関連する話なので． なぜ「35を素因数分解せよ」は「問題」じゃないの? 35でも，一千万桁を超えるような合成数でも*1，何らかの方法でその個別問題の答えを求め，記録しておけば，あとは同一の個別問題が出たら，記録していたのを書き並べるだけ…

そんな中，欲しいと思ったのが，「ホスト名に基づいてファイル名を生成する」こと．例えば，ホスト名がabcなら，~/.emacs.abc を読み出し，ホスト名がxyzなら ~/.emacs.xyz を読み出すよう，~/.emacs の中に書いておきたいわけです． あれこれ調べたのですが…

debian に emacs22 を入れたら日本語がやっとまともに使えるようになったのでその備忘録。 (略) さらにいろいろ調べてると、どうもみんな emacs-snapshot (emacs22) を入れてるらしい。 emacs22からはutf-8の対応が本体に組み込まれているのでmule-ucsの重い…

「決定可能」はなぜアルゴリズムを先に決めるの? 授業で，ある問題が決定可能であることの定義は アルゴリズムが存在して，問題に属する任意の個別問題がそのアルゴリズムで解ける であって， 問題に属する任意の個別問題に対して，アルゴリズムが存在して，…

1 ここで定義している木構造では，後で挿入したほうを，兄弟関係sibling relationshipの「兄」とするんですね． まあ中心となる処理のことを考えると，そうするのが合理的なのは分かるけど，ちょっと違和感がありました． …そうそう，だんご3兄弟を連想しま…

非決定性機械って実在するの? 昨日のエントリでは，「決定性のアルゴリズム」，「非決定性操作」といった表現を選びました．決定性というのは，いつも使っているコンピュータの振る舞いです． 非決定性操作ができる機械があるのか，ですが，授業ではテューリ…

情報セキュリティの授業で，「もしP=NPならば，現代暗号の安全性が根底から崩れる」ということを示すため，その前提となる要素を駆け足気味に説明しました．おそらく学生には，計算理論の面白いところが伝わらず，「なんじゃこら」だったのではないかと思い…

Amazonで注文して，昨日届きました． いかにして問題をとくか: 前からときどき書店で見かけていたのですが，思い切って買いました． プログラマの数学: これもよく見かけます．学生が困ったとき，参照してもらうかもしれない本です． 数学ガール (数学ガール…

大学生のための知のスキル表現のスキルから． アメリカの小学生にプレゼンテーションの基本を学ぶ(第2章) ノートのとり方を学ぶ(第3章) ディベートの方法を学び，実際にやってみる(第4章) 時間管理をして，まとまった分量の文章を書く(第5章) 演劇的プレゼン…

仮引数の配列変数は，ポインタなのか配列なのか - わさっきの続きです．検証コードを書いてみました． #include <stdio.h> void f1(int y[]); void f2(int y[]); void f1(int x[3]) { printf("%d\n", x[0] + x[1] + x[2]); } void f2(int x[2]) { printf("%d\n", x[0]</stdio.h>…

…いろいろおかしい．まず「正確に10×20のint配列に限られる」というのは間違いで，このように書いても，関数内のmy_arrayは，ポインタ変数になります*1． *1：関数プロトタイプ内のmy_arrayは，配列変数と見なしても，仕様上，問題ありません．とはいえ宣言…

いきなりですが問題です． 成功確率が (ただし[tex:0

1 暗号ではないプロトコルの具体例として，研究室配属というイベントがあります．9月末の数日間で，1年半，あるいは院に進学する人にとっては，3年半の研究室生活laboratory lifeが決まるようなものです．みなさんには，居心地のいい研究室，雰囲気のいい研…

1990年代のCプログラミング - わさっきの脚注とコメントから派生する話題を一つ． Cでは，実行時に変数が何型なのかを教えてくれるような機能が提供されていません． しかしながら，sizeof演算子を使えば，変数が配列か否かを識別することができます． そこ…

この日記を見てくれている，当学科の学生へ： 明日5限に，学部の大講義室で，講演があります． 講演者は，NTTソフトウェア株式会社 代表取締役社長の伊土誠一様です． 紹介者の教授より，1年生に限らず，多くの学生に参加を呼びかけてほしいと依頼がありまし…