計算理論, ナップザック問題, 鳩の巣原理と格子点, StripeからSMSを使わずに認証を手動で有効化すると返信が来ました
計算理論
オートマトン, 正規言語, P vs NP問題とかの話をする講義.
単位取得できないかもなあと思いつつ, ふんわりとしかそのへんの話を理解できていないので是非講義は受けておきたかった. 水曜日はこの講義しか無いスケジュールになってしまったけど, 無理矢理受講しました. 最悪単位は取れなくても良い, 知識が欲しい.
試験が持ち込みありで, 持ち込みテキストは手書きのみという話だったので, 例によってダメ元で｢印刷じゃダメですか?｣と聞いてみました. 学生に情報をまとめさせたいので, プリントのコピーを防止したいため, 自分で打ち込む場合は良いらしいです. 試験が近づいたら話そうという話になりました. なんとかなりそう? 授業時間後に今一度聞きに行ったら何か学習障害かどうか診断を受けているか聞かれたので, 精神障害者保健福祉手帳を見せたらすんなり納得してくれました. 便利.
今日はガイダンスと, 数学系の講義ではいつも繰り返されている証明や数の集合の話をするようですね.
この講義は効率の良い方法を考えるようなアルゴリズム論を扱うものではない. 計算理論では効率が良いとは何か, どんな解法を用いても解けない問題とは何かを考えていく.
ナップザック問題
本質的な難しさは取得するかの変数が0か1しかないという所にあり, これが実数を取れれば重さあたりの価値が最も高いものを取れば良いことになる.
ナップザック問題は知っていたので関連するプログラムを書こうと思いましたが, haskellで選択変数のようなリストを全列挙するのにスマートな方法が思いつかない.
もちろん
let vl = [0, 1]
[[v1, v2, v3, v4, v5] | v1 <- vl, v2 <- vl, v3 <- vl, v4 <- vl, v5 <- vl]
のようにすれば可能ですが, これってvの各要素をハードコーディングしているからあまりスマートとは言いがたい感じがします.
自分で実装してみました.
let vs i = [map (\i -> if i `elem` bs then 1 else 0) [1 .. i] | bs <- subsequences [1 .. i]]
として実装可能ですが, こういうの標準ライブラリにあって良いと思いますしありそうだと思いませんか.
鳩の巣原理と格子点
5個の格子点があると線分の中点が格子点になる2点の格子点が存在するという話, 前に聞いたけど証明方法を忘却していました.
私はいつも数学の話を忘却してしまう…
StripeからのSMS認証に関する返信
SMS認証はすべての人に最適ではないので, 手動でAPIを使えるように設定しますという返信が来ました. アメリカのどっかの機関もSMS認証はセキュアではないと警告しているしこの先変えていくのかな.
hatena-bookmark