sourceでごにょごにょするのを忘れていた。
考えてみると、例えばシステムの文字コードがEUC-JPで、sedで置換したいファイルの文字コードがUTF-8だったら、sedが途中で止まってしまう。
sourceでごにょごにょするのを忘れていた。
考えてみると、例えばシステムの文字コードがEUC-JPで、sedで置換したいファイルの文字コードがUTF-8だったら、sedが途中で止まってしまう。
Pythonのpercolが地味にバギーなので、pecoを入れた。
公式のREADMEをそのままなぞるだけ。
pecoを導入してzshのhistoryに使うようにした - さよならインターネット
oh-my-zsh の環境で、peco-select-history が動かない - Qiita
oh-my-zshのカスタムプラグインにぶっこむ。
function peco-select-history() { local tac if which tac > /dev/null; then tac="tac" else tac="tail -r" fi BUFFER=$(\history -n 1 | \ eval $tac | \ peco --query "$LBUFFER") CURSOR=$#BUFFER zle clear-screen } zle -N peco-select-history bindkey '^r' peco-select-history
今週はExcelにスクショを貼るのがトレンドらしいですが、 逆にExcelをスクショしてみた。
mov命令でImmediate to Register/Memoryかつw=1、つまりデータありのやつを一つの関数にまとめる。 まとめるっていうか、一つの関数に押し込んだだけなのだが。
最初の4ビットじゃなくて、次の4ビットのパターンが比較的似ているので、とりあえずそのあたりをリファクタする。
P181-P191
コンピュータ科学を学ぶ理由について
実変数の複素または実数値函数を別の同種の函数に写す変換 フーリエ変換 - Wikipedia
コンピュータ科学者の思考を学ぶ
計算モデル
アルゴリズム(プログラミング技術から離れて存在する)
チューリングの登場、1930年代になってから計算の近代的理論が導入された
すべての数学的問題を解くことのできるアルゴリズムは「存在しない」
計算理論に対する2つのアプローチ
特定の問題に対して異なる複数のアプローチ
状態q1→qn(n個) 状態を大きくしても劇的には改善しない
レジスタなどが一定以上増えても性能向上には寄与しない
有限状態機械を考える良い方法
チューリング機械のテープは一方向に無限に伸びている テープ区画(=メモリのアドレス)に0,1,2,3といった番号を割り振る
0か1かbしかない機械を考える。(0は左端)
テープの長さは無限で、0か1かの情報が入っている部分は有限。(概念上は無限だが、使われている部分は有限)
プログラムにしたがって1ステップずつ従っていく。
プログラムはq, x, q', x'
実行 テープヘッドを左へ右へずらしながら実行していく。
プログラムはひとつらなり。 これらはプログラムの実行により状態が変化していく。
<q, x, q', x'> <q, x, q', x'> <q, x, q', x'> <q, x, q', x'> <q, x, q', x'>
enumでこの中のどれかであること、今指しているのがコレ。みたいなやつ。=二重の条件のパターンマッチ。
内部状態 q1...qn 特別な状態 qs qh 今指し示しているxの中身を変えて、テープの位置を右か左にずらす。例外はテープの左端にあるときテープをさらに左にしようとするとプログラムは停止する。
テープの左端はアドレス0であって、テープの途中から左端が始まるわけではない。
qs q1 q2 q3 qh
0 or 1 or b(lank)
複数セルが0 1 0 1みたいな感じで続いている
チューリング機械は負でない整数から負で整数を出力するようになっている。
f(x) = 1を計算するだけでもものすごい力がいる。 が、理論上チューリング機械を使えばあらゆる数学的問題を解決することが可能となる。(ただし実行効率は度外視している)
チューリング機械によって計算可能な関数とアルゴリズムによって計算可能な関数が等価であるとチューリングは主張する。
数学で厳密に特定できることがわかったことが大きい。
70年以上たってもチューリング機械が計算出来ない問題があることは証明されていない。(エミュレートしようとして出来ない)
コンピュータはユニークなIDをふれる
量子コンピュータはチューリング機械は同じく数学的な問題を解決することが出来る。 量子コンピュータによってチューリング機械よりはるかに効率的に計算できる問題もある。
高次の擬似コードを使う。
例。brainfuckはチューリング完全
チューリングモデルのいかなる側面も変更できない。
単一テープのチューリング機械との違いは、プログラムが違うこと。
でも、チューリング機械は同じ計算結果が得られる。
No.
たとえば、トポロジー空間がトポロジー的に等価であるかどうかを決定する問題は決定不能
訳が雑
M(x)=x
近代的なプログラム可能なコンピュータと同様な考えにそっている。 命令の並びを変えれば何でも出来る。 CPUの命令セット
1台の機械によってあらゆる問題を計算できるマシンが存在しうる。
チューリング数xを有する機械は数yが入力されると停止するか?この問題を解決するアルゴリズムは存在しない。(所謂背理法、自己言及のパラドックスで証明出来る)
出力ビット
0→1→0→1を繰り返す
組み合わせ回路
回路に内部状態のことは考えない
これらを組み合わせることで、様々な計算が出来る。
少数の決まったゲートだけを使って任意の関数を計算できる。
f(x)
f0 = f(0;x1,.....,xn) f1 = f(1;x1,.....,xn)
1.wires 2.ancilla bits 3.the FANOUT operation 4.the CROSSOVER operation 5.the AND,XOR,and NOT gates
quantum
qubit 量子ビットは、情報のコピー(クローン)が出来ない。コピーしたらオリジナルは、死ぬ。
nand回路があれば他の回路を表現できる。
3bitの回路を計算するのに5bitの回路でも10bitの回路でも構わない。
(アルゴリズムの設計についてはこの本では扱わない)
O(n)
compare and swap コンペア・アンド・スワップ - Wikipedia
難しい。ので、ブルーバックスからやり直そうと思う。