計算理論の基礎:オートマトン

計算理論の基礎を読んでいるので整理のために少しまとめておきます。

www.amazon.co.jp

計算理論の3大分野

他の分野同様計算の理論もいくつかの分野に分かれていますが、そのなかでも重要なのが以下の3つの分野です。 計算の理論における根本的な疑問は計算機の本質とその能力の限界にあり、各分野別の角度からその答えを探っています。

  • 計算の数学的モデル(オートマトン)... 計算の数学的モデルとその性質・能力
  • 計算可能性 ... 計算機が解決できる問題とそうでない問題の違い
  • 計算の複雑さ ... 問題の難しさを決める要因について

オートマトン

第1巻のテーマはオートマトンです。計算機に対し入力として文字列の集合を与えた時にそのモデルで認識できるかどうかなどが議論の中心になります。本書で紹介されている計算モデルは

の3つです。(チューリング機械は計算可能性への導入として第2巻に収録されています。)

有限オートマトン

はじめに紹介される計算モデルは有限オートマトンと呼ばれるものです。ここで有限なものは記憶領域であり、この制約のためこのモデルの能力は他のモデルに対し限られています。 有限オートマトンの正式な定義は以下の5つの値の組で表されます。

  • 状態の集合
  • 入力アルファベットの集合
  • 遷移関数
  • 開始状態
  • 受理状態の集合

入力された文字列が受理状態で終了するときこれを"認識する"と言います。またある有限オートマトンで認識される文字列の集合(=言語)を正規言語と呼びます。つまりある有限オートマトンに対応する正規言語が1つ存在します。

この文字列の集合である言語に対して3種類の演算(和集合演算、連結演算、スター演算)を定義することができ、その総称を正規演算と呼びます。そしてこの正規演算を使って正規言語を表現したものを正規表現と呼びます。

決定性と非決定性

先の定義で表される有限オートマトンというのは決定性という性質を持ちます。非決定性の方が捉えやすいでしょう。ある入力に対して遷移先状態が複数存在し、枝分かれが起きるときこれを非決定的と言います。逆にどの入力アルファベットに対しても遷移関数が1つの状態を出力するとき決定性を持ちます。この2つを区別し決定性有限オートマトンDFA: Deterministic Finite Automata)と非決定性有限オートマトン(NFA: Nondeterministic Finite Automata)という名前がつけられています。また正規演算を使って簡潔化したNFAを一般化非決定性有限オートマトン(GNFA: Generaristic Nondeterministic Finite Automata)と言います。

直感的には非決定性有限オートマトンの方が表現力があるように感じます。しかし驚くべきことにこのDFAとNFAは能力の点において等価です。本書にはこの証明が記載されているので興味がある人は読んでみてください。このためDFAを使うかNFAを使うかはケースバイケースで使いやすい方を選ぶことになります。本書では正規演算の閉包性を証明するためにNFAが紹介されました。

ある言語に対応する有限オートマトンが存在するかどうか、つまり有限オートマトンの能力の限界、ある言語が有限オートマトンで認識可能かどうかはポンピング補題と呼ばれる定理を用いて背理法により確認することができます。

プッシュダウン・オートマトン

次に紹介されるのはさらに強力な言語を記述できる文脈自由文法(CFG: Context Free Grammer)とそれを認識する計算モデルであるプッシュダウン・オートマトンPDA: Push-Down Automata)です。この文脈自由文法では正規表現で表すことのできなかった再帰的な構造も扱うことができ、プログラミング言語の仕様やコンパイラといった応用例があります。この文脈自由文法を用いて記述された言語を文脈自由言語(CFL: Context Free Language)と呼びます。

文脈自由文法は以下の4つの値の組で定義されます。

  • 変数の集合
  • 終端記号
  • 変数 → 変数および終端記号、で構成される書き換え規則(rule)の集合
  • 開始変数

この文脈自由文法を設計する際のポイントは以下の4つです。

  • CFLを小さなCFLの和集合に分解して考える
  • 言語が正規であればDFAからCFGに変換する
  • 2つの部分文字列がお互いに関連するときのパターン
  • 再帰構造に対するパターン

1つの言語に対して様々に書き換え規則を表現することができますが、その中でも最も単純化された表現をChomski標準形と呼びます。

さて先ほどの有限オートマトンは記憶領域に制限がありましたが、この制限を取り除き無限の記憶領域を与えます。ただし今回はそのアクセス方法に制限があり、スタック(First In First Outのデータ構造)としてしか使用できないとします。この計算モデルをプッシュダウン・オートマトンと呼びます。PDAの定義は以下の6つの値の組で表されます。

  • 状態の集合
  • 入力アルファベットの集合
  • スタック・アルファベットの集合
  • 遷移関数
  • 開始状態
  • 受理状態の集合

遷移関数は状態の集合を返すため非決定性を持ちます。先に書いたとおりこのPDAにより認識される言語を文脈自由言語と呼びまたある言語に対しそれを認識するPDAが存在する時その言語を文脈自由言語と呼びます。

有限オートマトンと同様にポンピング補題を使うことによりPDAの限界=ある言語を認識するPDAが存在するかどうかを証明することができます。

チューリング機械

さてプッシュダウン・オートマトンには記憶領域へのアクセス方法に制限がありました。この制限を取り除き、テープ上に記録したどの領域にも自由にアクセス可能にした計算モデルをチューリング機械と呼びます。チューリング機械の持つ性質として、受理状態あるいは拒否状態に入った時点で停止すること、ループという永久に停止しない状態が存在することがあります。このチューリング機械はコンピュータに対する正確なモデルになっており、チューリング機械の能力の限界を調べることはコンピュータにできないことを知ることに繋がります。定義は以下の7つの値の組で表されます。

  • 状態の集合
  • 入力アルファベットの集合
  • テープ・アルファベットの集合
  • 遷移関数
  • 開始状態
  • 受理状態
  • 拒否状態

チューリング認識可能であるとはある言語に対し認識可能(受理・拒否・ループのいずれかの終了状態であることがわかる)なチューリング機械が存在することであり、チューリング判定可能であるとはある言語に対し判定可能(受理・拒否のいずれか)なチューリング機械が存在することを言います。

このチューリング機械にはいくつかの亜種が存在し、テープを2本もつなどそれぞれ変更点がありますが、自由なアクセスが可能な無限の記憶領域という本質は共通しており、一方でもう一方をシミュレート可能なため能力の点では等価です。

ある問題の解を求めるアルゴリズムがそれをチューリング機械上でのステップを示すことと等価であることをChurch–Turing提唱といいます。それによりある問題を解くアルゴリズムが存在するかどうかをチューリング機械の判定可能性により確かめることができます。

まとめ

ざっくりした説明になってしまいました。詳しくは書籍の方をご覧ください。それぞれの数学的証明もじっくり掲載されているので証明から理解したい人にもおすすめです。

2018年を振り返る

こんにちは。いつにも増して筆不精ですが年の瀬なので今年一年を振り返っておこうと思います。

昨年の振り返りにもあるように今年は効率的な学習を強く意識しました。

kentakudo.hatenablog.com

具体的には一年を四半期に区切りそれぞれテーマを絞って学ぶスタイルをとりました。それぞれ以下のテーマです。

それぞれ個別にみていきます。

1〜3月:デザインパターン機械学習

こちらにまとめてあります。

kentakudo.hatenablog.com

記事にあるように、もともとはデザインパターンとネットワークをテーマにする予定でしたがDL4USのコースに当選したため丸々二ヶ月機械学習を勉強していました。デザインパターンに関しては有名な本二冊(「オブジェクト指向における再利用のためのデザインパターン」「増補改訂版Java言語で学ぶデザインパターン入門」)を読んだもののよく理解できず、またネットワークも「UNIXネットワークプログラミング〈Vol.1〉」を途中まで読んでOS周りの知識が足りないためそこを補ってから読んだ方が早く理解できそうだという結論に達しました。機械学習はDL4USとCourseraのオンラインコースプログラマ向けの本をいくつか読んでかなり楽しく学べた一方、残念ながら根本的に興味が薄いなということを認識しました。機械学習を専門にすることは想像できないですが、機械学習には何らかの形で関わりたいと思っているのでさらに踏み込んで勉強したい分野です。

4〜6月:オペレーションシステム

こちらまとめです。

kentakudo.hatenablog.com

とても難しかったです。難しかっただけに「あ、わかったかも」という瞬間の気持ち良さも強く、機械学習とは対照的に勉強することでますます興味が増した分野です。(機械学習も難しかったんですけどね。。)Raspberry Piを使うというアイデアは勉強している途中に思いついたものですが「なにか作る」という点でとても学習効果の高いものだったので同じ形ではないにせよ他の分野を学ぶときにも活かせそうなアイデアだと思います。完成まで至らなかったですし、IoTという視点でも来年はもっとラズパイで遊ぼうと思っています。

7〜9月:テスト、オブジェクト指向、セキュリティ

こちらがまとめになります。

kentakudo.hatenablog.com

この三ヶ月間は「勉強したいと思っている残り物詰め込み期間」ということでテーマを三つ、それぞれひと月ずつ勉強しました。初めの二ヶ月は「テストとTDDはどう違うのか」という疑問から始まり、オブジェクト指向に到るまで関連の有名な本を中心に読んでいきました。実用の面から言って一番役に立った期間でした。TDDを日頃の業務で即実践できるので段違いに身に付くスピードが早かったです。オブジェクト指向を理解することで結果として1月に挫折したデザインパターンもかなり理解が進みました。セキュリティに関しては分野に触れた程度の理解に止まっており、もう一度学びたい、次はCTFにも出てみたい、と思っています。

10〜12月:デザイン、DevOps

当初はデザインのみを学ぶ予定でしたが本業の都合と、デザインにそこまで気持ちが向かなかったことがあり2つのテーマを平行して勉強する形になりました。結果としてどちらも中途半端になってしまい「一度に一つ」を守ることがいかに大切かを再認識しました。デザインはいくつか本を読んだのに加えDesignLab 101のオンラインコースおよびUAL: Central Saint Martinで一週間グラフィックデザインショートコースを受講しました。とくにショートコースは"mind blowing"な経験で始まる前は不安でいっぱいでしたが終わってみると一週間頭を使いっぱなしで楽しくてたまりませんでした。いきなりWebデザインやIllustratorを始めるよりもグラフィックデザインを学ぶ方が「デザインとはなにか」という点を学ぶことができるのでおすすめです。「デザイナーになろう!」とはなりませんでしたが、とても楽しかったのでタイミングがあれば違うコースを受講してみようかなと思います。最終的に目標としていたポートフォリオサイトのデザインはかろうじて達成できたかなと思うので興味ある方はぜひご覧ください。笑

読書リスト

昨年に続き読書リストをあげておきます。

  1. オブジェクト指向における再利用のためのデザインパターン
  2. Java言語で学ぶデザインパターン入門
  3. ITエンジニアのための機械学習理論入門
  4. プロフェッショナルシリーズ 深層学習
  5. 詳解 ディープラーニング TensorFlow・Kerasによる時系列データ処理
  6. Python Machine Learning — Second Edition
  7. はじめてのOSコードリーディング
  8. プログラムはなぜ動くのか
  9. 30日でできるOS自作入門
  10. Linuxのしくみ
  11. はじめて読む486
  12. Linux カーネル読解室
  13. BareMetal で遊ぶ Raspberry Pi
  14. はじめて学ぶソフトウェアのテスト技法
  15. 知識ゼロから学ぶソフトウェアテスト
  16. ソフトウェアテスト技法
  17. テスト駆動開発
  18. 実践テスト駆動開発
  19. The Art of Software Testing
  20. リファクタリング
  21. エクストリームプログラミング
  22. レガシーコード改善ガイド
  23. Agile Testing
  24. オブジェクト指向でなぜつくるのか
  25. クリーンコード
  26. アジャイルソフトウェア開発の奥義
  27. パターンハッチング
  28. ソフトウェアアーキテクチャ(POSA)
  29. エンタープライズアプリケーションアーキテクチャパターン
  30. プログラミング作法
  31. 不正アクセス対策
  32. 体系的に学ぶ 安全なWebアプリケーションの作り方
  33. おうちで学べる セキュリティのきほん
  34. この一冊で全部わかるセキュリティの基本
  35. 動かして学ぶ セキュリティ入門講座
  36. セキュリティコンテストチャレンジブック
  37. サイバーセキュリティプログラミング — Pythonで学ぶハッカーの思考
  38. ハッカーの学校
  39. HACKING:美しき策謀
  40. Object oriented software construction
  41. データベース実践入門
  42. インターフェイスデザインの心理学
  43. さよなら、インターフェイス
  44. なるほどデザイン
  45. 新しいシェルプログラミングの教科書
  46. レイアウト、基本の「き」
  47. 詳解シェルスクリプト
  48. Layout Essentials 100 design principles for using grids
  49. 「シェル芸」に効くAWK処方箋
  50. 入門vi
  51. You can draw in 30 days
  52. Ansible: Up and Running, 2nd Edition
  53. Terraform: Up and Running
  54. 初めて作るクラウドインフラ Amazon Web Service ネットワーク入門
  55. Amazon Web Service in Action
  56. AWS System Administration
  57. CentOS 7 構築・運用・管理パーフェクトガイド

計57冊

総評

昨年「来年学びたいこと」として

を挙げていました。

昨年紹介したこちらの記事および今年読んだ「本を読む本」におけるシントピカル読書、シントピカル学習を実践した結果、言語処理系には手をつけられませんでしたが体感として目指していたところの85%は達成していると思うので成功の年だったといっていいんじゃないかと思います。

来年は

取り組みたい課題が2つあります。

一つ目は積年の課題であるアウトプットです。これまで意識的にインプット偏重の学習をしていました。駆け出しのプログラマとして正しかったとは思うものの、アウトプットが苦手である以上言い訳である感じは拭えません。学習効率改善の余地としてアウトプットは最大のボトルネックである他、プログラマとしてやっていく以上もう少しプレゼンスがあった方が都合がいいなと思います。反応があった方が楽しいですしね。水物でもありますし気にしすぎもよくないので、期待値低めで頑張りたいと思います。

二つ目は専門性に関してです。昨年までのデタラメな学習からテーマを絞った学習にシフトして効率という面では大きく進歩しました。しかしいまだに「広く浅く」という印象が強く「これが僕の強みです」と言えるものを持っていないのがコンプレックスです。来年は一つのテーマに腰を据えて自分の強みにしていくことを始めたいなと思います。


諸々の事情がありここのところこれからについてモヤモヤ考える日々を過ごしています。大学を卒業して強い希望もなく"とりあえず"でプログラマを選んだ時に「3年間全力でやってやめてしまおう」と冗談半分で思っていましたがあっという間に3年半が経過してしまいました。「やり尽くした」という境地には至っていませんが機会に恵まれ3年間でとても多くのことを学べました。あいかわらずプログラマとしてやっていくことには強い希望もなく、それ故にプログラマとして到達できるところもたかが知れているなと思うんですけども他にやりたいことがあるわけでもないし、なんだかんだプログラマが向いているなとも思うので結局これまで同様に「走りながら考える」というのを続けるしかないかなというのが今の所の結論です。

プログラマとしてやっていくにしてもそれはそれで一つ違うフェーズに入るかなと思います。一つには「3年間」という意識が常にあったこと、もう一つはある程度自信がついてきたことです。これまでは「なんとか追いつかなくては」という意識でやっていたし、とくにメルカリという環境にあっては同年代で何歩も先にいる同僚がごろごろいる中でビハインドを取り返すという強いモチベーションがありました。一方常に「これじゃダメだな」と思っていたのは、いいプログラマというのはいいプログラムを書ける人ではなく、プログラムにより問題を解決する人だということです。もちろんもう知識は必要ないというつもりはないですがそれ自体には終わりがないことですしタイミングもいいのでそろそろ問題解決にフォーカスすべき時期にきたかなという感じがします。じゃあ具体的にどうするのと言われるとそれはまだよくわかってないんですけどね。特に僕はコミュニケーションもだいぶ苦手ですし自分に合った問題解決スタイルを探すのが当面の目標になりそうです。

【NOTE】Prometheus

This is a note taken when investigating Prometheus.

TODO

  • get familiar with Grafana
  • setup mail server and send alert via email as well as Slack

【NOTES】Consul

The followings are the notes taken when spiking Consul.

miscs

MySQLでレプリケーションを設定する

レプリケーションMySQLで最も重要な機能の一つで、その用途は多岐に渡ります。それゆえ素早くセットアップできることが好ましいです。ここではその手順をまとめておきます。

方法はいくつかありますがここではマスターからmysqldumpでデータを取ってくる方法を使います。

1. マスターサーバーのコンフィギュレーション

マスターでは以下のようにオプションを設定します。

[mysqld]
bind-address = 10.132.0.2
server_id = 1
log_bin = /var/log/mysql/mysql-bin.log
sync_binlog = 1

server_idレプリケーションするグループ内で一意である必要があります。デフォルトが1なので他のインスタンスと衝突しないように違う値を割り当てるのが安全ですがここではデフォルトのままにしておきます。今回はローカルネットワーク内にマスター・レプリカを立てるのでbind-addressにはローカルIPを書いておきます。log_binにはバイナリログの位置を指定、sync_binlogフラグを立てることでトランザクション毎にバイナリログが同期することを保証します。

2. マスターにレプリケーションユーザーを作成する

レプリケーションではマスターがサーバーでレプリカがクライアントの役割を果たします。よってマスター側にレプリカがアクセスする用のユーザーを作成します。

GRANT REPLICATION SLAVE ON *.* TO 'slave_user'@'%' IDENTIFIED BY 'password';
FLUSH PRIVILEGES;

ここではクライアントホストに%を指定することで複数のレプリカでユーザーを使い回す想定で作成します。

3. マスターのデータをmysqldumpで取得する

バックアップをとる方法でまとめたのと同様にmysqldumpコマンドによりデータの論理バックアップを取得します。

$ sudo mysqldump --all-databases --master-data=2 --single-transaction --flush-logs > backup/dumpfile.sql

--all-databasesにより全てのデータベースを対象にし、--master-data=2によりダンプデータにレプリケーションの開始位置を書き込ませます。--single-transactionは複数データベースのデータを取得する際の不整合を防ぐオプション(InnoDB専用)、--flush-logsによりバイナリログのローテートを指示します。

4. スレーブのコンフィギュレーション

スレーブのmysql.confファイルを以下のように設定します。

[mysqld]
bind-address = 10.132.0.3
server-id = 2
relay-log = /var/log/mysql/mysql-relay-bin.log

スレーブはserver-idに2を割り当て、ローカルIPの設定もします。マスターから取得するバイナリログはまずリレーログという領域に置かれます。その後マスター接続するのとは別のスレッドがリレーログの内容をデータに書き込みます。relay-logの値にリレーログを書き込む場所を指定しておきます。

5. ダンプしたデータのリストア

先ほどマスターから取得したダンプファイルをスレーブに適用します。

$ sudo mysql < dumpfile.sql

6. スレーブでレプリケーションの設定をする

スレーブでマスターとバイナリログ上のレプリケーションの開始位置を指定します。レプリケーションの開始位置は以下のようにダンプデータから取得できます。

$ cat dumpfile.sql | head -n30 | grep CHANGE
-- CHANGE MASTER TO MASTER_LOG_FILE='mysql-bin.000002', MASTER_LOG_POS=154;

mysqlに以下のクエリを流します。

CHANGE MASTER TO
    MASTER_HOST='10.132.0.2',
    MASTER_USER='slave_user',
    MASTER_PASSWORD='password',
    MASTER_PORT=3306,
    MASTER_LOG_FILE='mysql-bin.000002',
    MASTER_LOG_POS=154,
    MASTER_CONNECT_RETRY=10;

7. マスターに更新クエリをかける

レプリケーションがうまくいってることを確認するためにマスターのデータを更新してみましょう。

8. レプリケーションの開始

スレーブ側でレプリケーションを開始します。

START SLAVE;

9. レプリケーションの確認

スレーブ側では以下のように確認します。

SHOW SLAVE STATUS\G

またマスター側での確認は

SHOW MASTER STATUS;
SHOW SLAVE HOSTS;

です。

先ほどマスターで更新したデータがスレーブに書き込まれていること、マスターへの更新クエリがスレーブに反映されることも確認しましょう。

参考

MySQLで差分バックアップをとる

リストア処理においてフルバックアップと合わせて必要になるのが差分バックアップです。ということで備忘録。

1. バイナリログを記録する

まずはこれをしないと始まりません。設定ファイルのlog-binの項目をコメントインし、サーバーを再起動しておきましょう。

2. フルバックアップをとる

--flush-logsオプションをつけてログをローテートしておきます。こうしておくとリストア時にファイルの先頭から復元すればよいため手順がシンプルになります。

$ sudo mysqldump --flush-logs --lock-all-tables --all-databases > backup/full-$(date +%Y%m%d).sql

3. バイナリログを保存しておく

$ sudo mysqlbinlog /var/log/mysql/mysql-bin.000005 > binlog/diff-$(date +%H%M%S).sql

これで保存した分まで復元できるので常に最新のものを安全な場所に保管できるようにしておきましょう。

バックアップの処理はここまでで以降リストアの処理です。緊張感が欲しい方はDROP DATABASEしましょう。

4. フルバックアップを復元する

$ sudo mysql < backup/full-20181030.sql

フルバックアップ取得時まで復元しました。次にバイナリログ分を適用します。

5. バイナリログの適用

フルバックアップと同じようにmysqlコマンドに流すだけです。

$ sudo mysql < binlog/diff-193632.sql

これで完了です。

ログをローテートしたくないとき

バックアップ時に--master-data=2オプションをつけましょう。こうすることでダンプデータにどのバイナリログのどの位置からリストアすればいいかがわかります。

sudo mysqldump --lock-all-tables --all-databases --master-data=2 > backup/full-$(date +%Y%m%d).sql
$ head -n30 backup/full-20181030.sql | grep 'CHANGE MASTER'
-- CHANGE MASTER TO MASTER_LOG_FILE='mysql-bin.000005', MASTER_LOG_POS=831724;

位置を指定してリストアする

mysqlbinlog時に--start-positionを指定して展開します。

$ sudo mysqlbinlog --start-position=831724 /var/log/mysql/mysql-bin.000005 > binlog/diff-$(date +%H%M%S).sql

あとは同じリストア手順。(ということはバイナリログはmysqlbinlogを通さずそのまま保管したほうがいいのか......。)

参考