箱玉系で使われるcrystal base論について

crystal base論は量子群U_q q = 0の表現論として、構築されたものです。この記事では、箱玉系(ball-box system)の基本的な要素であるcrystalという代数構造と組み合わせ数Rについて量子群U_q(sl_{n+1}) の場合について説明します。

1. Crystalの定義

U_q = U_q(sl_{n+1})のcrystalの定義をします。 Iを添え字集合とします。crystal Bとは、集合B写像


\begin{aligned}
wt:B \rightarrow \bar{P} \\
\tilde{e_i}, \tilde{f_i}:B \rightarrow B \cup \{ 0 \}  \\
\varepsilon _i, \varphi _i : B \rightarrow \mathbb{Z} _{\geq 0} (i \in \bar{I})
\end{aligned}


の集まりで以下の性質を満たすものです。

  1. b \in Bかつ\tilde{e_i}b \in B ならばwt(\tilde{e_i}b) = wt(b) + \alpha_i
  2. b \in Bかつ\tilde{f_i}b \in B ならばwt(\tilde{f_i}b) = wt(b) - \alpha_i
  3. \varphi _i(b) = max { m \geq 0 | \tilde{f_i} ^m (b) \neq 0 }
  4. \varepsilon _i(b) = max { m \geq 0 | \tilde{e_i} ^m (b) \neq 0 }
  5. \varphi _i(b) - \varepsilon_i(b) = ( h_i, wt(b))
  6. \tilde{e_i}(0) = \tilde{f_i}(0) = 0
  7. b, b' \in Bならばb'=\tilde{f_i}(b)b=\tilde{e_i}(b')は同値

wt(b)bウェイトといいます。\tilde{e_i},\tilde{f_i}柏原作用素といいます。その作用、すなわち、7.の状況をb \xrightarrow{i} b'と表し、これを頂点b からb'へ向かう「色」iの矢印と見立てれば、Bは色付き有向グラフとして図示されます。これをcrystalグラフといいます。crystalグラフの一つの頂点から色iの矢印は1つ出るか(\tilde{f_i} \neq 0)、出てないか(\tilde{f_i} = 0)のどちらかです。同様に、7.により、各頂点には色iの矢印は1つ入るか(\tilde{e_i} \neq 0)、入らないか(\tilde{e_i} = 0)のどちらかです。

U_q (sl_2)の例を挙げます。この時\alpha_1 = 2 \bar{\Lambda}です。

  • B(\bar{\Lambda_1})
    B(\bar{\Lambda_1})のcrystalグラフは次のように表されます。
    \fbox{1} \xrightarrow{1} \fbox{2}

  • B(2\bar{\Lambda_1})
    B(\bar{\Lambda_1})のcrystalグラフは次のように表されます。
    \fbox{1}\fbox{1} \xrightarrow{1} \fbox{1}\fbox{2} \xrightarrow{1} \fbox{2}\fbox{2}

    q=0の場合(箱玉系の場合に相当)

    q=0に絞ると上の定義は少し簡単にできます。 Iを添え字集合とします。この時crystal Bとは、集合B写像\tilde{e_i}, \tilde{f_i}:B \rightarrow B \cup { 0 }の集まりで、以下の性質を満たすものです。

  • 任意のb \in Bと任意のi \in Iに対して、\tilde{e_i}^n(b) = \tilde{f_i} ^n(b) = 0を満たすn > 0が存在する。
  • \tilde{e_i}(0) = \tilde{f_i}(0) = 0
  • b_1,b_2 \in Bに対して、\tilde{f_i}(b_1) = b_2が成り立つことと、\tilde{e_i} (b_2) = b_1が成立することは等しい。
    (ウェイト(wt)に関する部分の定義を省きました。)
    また、b \in Bに対して、

\begin{aligned}
\varepsilon _i(b) = max { m \geq 0 | \tilde{e_i} ^m (b) \neq 0 }\\
\varphi _i(b) = max {m \geq 0 | \tilde{f_i} ^m (b) \neq 0 } 
\end{aligned}

を定めます。
箱玉系を構成するにあたって、\hat{sl} _ {n+1}と結びついている、crystalB _ lを使います。そしてn \in \mathbb{Z} _ {1 \leq n}のもとで、I={0,1,...,n}をとります。
この時集合B_lは、次のようにして与えられます。


\begin{aligned}
B_l = 
\left\{
(x _ 1,..., x _ {n+1} ) \in \mathbb{Z} ^ {n+1} | x _ i \geq 0, \sum ^ {n+1} _ {i=1} x _ i = l)
\right\}
\end{aligned}

B_lの各元は、ヤング盤によっても表現することができます。それぞれのx=(x _ 1,...,x _ {n+1}) \in B _ lについて、長さlの一列の半標準盤を対応させられます。例えば、n=2,l=2とすると、そのcrystalは、


\begin{aligned}
B_2 = 
\left\{
(2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)
\right\}
\end{aligned}

となります。これはヤング盤では、
B_2={[1][1], [2][2], [3][3], [1][2], [1][3], [2][3] } と表せます。(各マスがボールを表していて、マスの中の数字が、対応するボールは今何マス目にいるのかということを表しています。) B_lは、l-foldの対象テンソル表現の基底のラベリングした 集合です。
x=(x _ 1,...,x _ {n+1}) \in B _ l\tilde{e_i},\tilde{f_i}:B _ l \rightarrow B _ l \cup \{ 0 \} (0 \leq i \leq n)


\begin{aligned}
\tilde{e_i}(x) = (...,x _ i+1,x \ {i+1} -1,...), \tilde{f_i}(x) = (...,x _ i -1,x _ {i+1} +1)
\end{aligned}

で定める写像とします。これらの写像B_lからB_lに移るか、あるいはそれ以外のところに移ります。それ以外のところに移った時、\{ 0 \}に移ったと解釈します。
[tex:\varepsilon i(b),\varphi i(b) :B \rightarrow \mathbb{Z} (0 \leq i \leq n)]は、その定義により、 x=(x _ 1,...,x _ {n+1}) \in B _ l\tilde{e_i},\tilde{f_i}:B _ l \rightarrow B _ l \cup \{ 0 \} (0 \leq i \leq n)


\begin{aligned}
\varepsilon _i(x) = x _ {i+1},\varphi _i(x) = x _ i
\end{aligned}

のように表せます。([tex:\varepsilon i(x)]は、[tex:\varepsilon i ^ m (x)]が0にならないように作用させ続けられる最大の回数をm表します。)
さて、任意の2つのcrystalB,B'に対して、テンソル積を定義することができます。集合としては、B \otimes B'は直積となります。しかし、これは crystal構造を保っています。任意の(x,y) \in B \times B'について、B \otimes B'の要素として、x \otimes yをとることができます。x \otimes 0 = 0 \otimes y = 0とします。
x \otimes y \in X \otimes X'に対して、写像[tex:\varepsilon i(x),\varphi i(x),\tilde{e_i}(x), \tilde{f_i}(x)]は次のようにして与えられます。


\begin{aligned}
\varepsilon _i(x \otimes y) = \varepsilon _ i(x) + ( \varepsilon _i(y) - \varphi _i(y)) _ + \\
\varphi _i(x\otimes y) = \varphi _i(x) + (\varphi _i(y) - \varepsilon _i(y)) _ + \\
 \\
\tilde{e_i}(x\otimes y) =
\left\{ 
\begin{array}
\tilde{e_i}(x) \otimes y   \mbox{if}  \varphi _i(x) \geq \varepsilon _i(y) \\
x \otimes \tilde{e_i}(y)   \mbox{if}  \varphi _i(x) < \varepsilon _i(y)
\end{array}
\right. \\
 \\
\tilde{f_i}(x\otimes y) =
\left\{ 
\begin{array}
\tilde{f_i}(x) \otimes y   \mbox{if}  \varphi _i(x) > \varepsilon _i(y) \\
x \otimes \tilde{f_i}(y)   \mbox{if}  \varphi _i(x) \leq \varepsilon _i(y)
\end{array}
\right. \\

\end{aligned}

ただし、(x)_+ = max(x,0)とします。
このように定義してあげると、テンソル積は、crystalの定義を満たします。 (実際に1.~3.が成立します)
この構成方法を複数回用いることで、(テンソル積は結合法則が成り立つため)2つよりも多いcrystalのテンソル積も定義することができます。
crystalは、crystalグラフといわれる色付き有向グラフで表現することができます。
以下の図では、\tilde{f_i}\xrightarrow{i}で表しています。公理3.より、\tilde{f_i}\tilde{e_i}は等価であるので、\tilde{f_i}についてのみ表します。

  • B_1
    [1] \xrightarrow{1} [2] \xrightarrow{0} [1]

  • B_2
    [1][1] \xrightarrow{1} [1][2] \xrightarrow{1} [2][2] \xrightarrow{0} [1][2] \xrightarrow{0} [1][1]

  • B_1 \otimes B_2
    [1] \otimes [1] \xrightarrow{1} [2] \otimes [1] \xrightarrow{1} [2] \otimes [2] \xrightarrow{0} [1] \otimes [1] \xrightarrow{0} [1] \otimes [1]

2. 組み合わせR

一般にcrystalB \otimes B'B' \otimes Bは同じ構造をしています。(同型です。) 組み合わせRとは、柏原演算子の作用で結びつけられたB \otimes B'B' \otimes Bの間の全単射のことです。言い換えると、組み合わせRは次のような関係を満たす写像B \otimes B' \rightarrow B' \otimes Bのことを指します。


\begin{aligned}
R(\tilde{e_i}(x \otimes y)) = \tilde{e_i}( R(x \otimes y)),  R(\tilde{f_i}(x \otimes y)) = \tilde{f_i}( R(x \otimes y)) \\
(2.1)
\end{aligned}

特殊な場合を除き、組み合わせRは上の条件を課すことで一意に決まることが知られています。
定義より、R _ {BB'} \circ R _ {B`B} = Id _ {B \otimes B'} が成立します。

\hat{sl} _ {n+1}crystal 組み合わせRに対して、区分線形な式が存在します。与えられたx = (x _ 1,...,x _ {n+1}),y=(y _ 1,...,y _ {n+1}) \in \mathbb{Z} ^ {n+1}に対して、\tilde{x} = (\tilde{x} _ 1,...,\tilde{x} _ {n+1}),\tilde{y}=(\tilde{y} _ 1,...,\tilde{y} _ {n+1}) \in \mathbb{Z} ^ {n+1}を次のように定めます。


\begin{aligned}
\tilde{x} _ i = x _ i - P _ i(x,y) + P _ {i-1}(x,y), \\ 
\tilde{y} _ i = y _ i + P _ i(x,y) - P _ {i-1}(x,y), \\
P _ i(x,y) = \max _ {1 \leq k \leq n+1} 
\left(
\sum _ {j=k} ^ {n+1} x _ {i+j} + \sum _ {j=1} ^ {k} y _ {i+j}
\right) \\
(2.2)
\end{aligned}

命題2.1

与えられたx \in B _ l, y \in B _ {l'}に対して、\tilde{x},\tilde{y} \in \mathbb{Z} ^ {n+1}を上のように定めます。すると、次の1.,2.が成立します。
1. 全ての要素は非負です。ゆえに\tilde{x} \in B _ l,\tilde{y} \in B _ {l'}です。
2. R(x \otimes y) = \tilde{y} \otimes \tilde{x}によって、写像R:B _ l \otimes B _ {l'} \rightarrow B _ {l'} \otimes B _ lを定義します。すると、この写像は、\hat{sl} _ {n+1}crystalの組み合わせRとなります。(すなわち、R(\tilde{e_i}(x \otimes y)) = \tilde{e_i}( R(x \otimes y)),  R(\tilde{f_i}(x \otimes y)) = \tilde{f_i}( R(x \otimes y))が満たされます。)

この命題は、後述する組み合わせRに関するアルゴリズムを上の式(2.1)と等価であることを示すことで証明できます。
組み合わせ数Rに関する式は、\sum _ {i=1} ^ {n+1} (x _ i - \tilde{x} _ i) =\sum _ {i=1} ^ {n+1} (y _ i - \tilde{y} _ i) = 0という条件の下で次の関係式によって特徴で付けられます。


\begin{aligned}
x _ i + y _ i = \tilde{y} _ i + \tilde{x} _ i, max(-y _ i,-x _ {i+1}) //
(2.3)
\end{aligned}

この関係は、(2.1)の式の結果として出てくるものです。

参考文献

ベーテ仮説組み合わせ論 国場敦夫 Integrable structure of box-ball systems:crystal, Bethe ansatz, ultradiscretization and tropical geometry

教師なし学習(クラスタリング問題)の数理的な問題設定

教師なし学習の数学的な問題設定

教師なし学習の問題としては、2つの問題設定があります。

(\bf{x} _ i, z _ i) (ただしi = 1,...,n)という標本の集合が存在するとします。この集合の各要素について、\bf{x} _ iは観測可能だが、それに対応するz _ iは観測できません。このような状況下で、z _ iを推定するというのが教師なし学習の1つ目の問題です。また、母集団に存在する未知の\bf{x}についても、それに対応するzを予測するというのが2つ目の問題です。

1. クラスタリング問題

1.1 ハードクラスタリング

z _ i \in \{ 1,...,K \} のときクラスタリングまたはハードクラスタリングといいます。ハードクラスタリングは、教師変数のない他クラス分類問題と言いかえることもできます。また、ハードクラスタリングは、\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \{ 0, 1 \} ^ K, |\bf{z} _ i| = 1 \} と言いかえることもできます。(one-hot encoding, 1 of K 表記)

K-平均法

  • 予測
    k \in [ K ] クラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、

\DeclareMathOperator*{\argmin}{arg\,min} %argmin
\begin{aligned}
z _ k = 
  \left\{
    \begin{array}{11}
      1 & k = \argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\
      0 & otherwise
    \end{array}
  \right.
\end{aligned}

と定めます。要は一番近いクラスタ中心に属するという意味です。

  • 目的関数
    \mu = \mu _ k, Z = z _ {ik}とし、

\begin{aligned}
J(\mu) = \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\
= \min _ {Z} \mathfrak{L}(Z, \mu) \\ 
ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\
Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。
\end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)Zについての最小化をします。


\begin{aligned}
Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\
すなわち次のようにパラメータを更新をします。\\  
z _ {ik} = 
  \left\{
    \begin{array}{11}
      1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\
      0 & otherwise
    \end{array}
  \right.
\end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)\muについての最小化をします。


\begin{aligned}
\mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\
すなわち次のようにパラメータを更新をします。\\  
\mu _ {k} = \frac{\Sigma _ i z _ {ik} \bf{x _ i}}{\Sigma _ i z _ {ik}}
\end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。

1.2 ソフトクラスタリング

\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \bf{z} \in [ 0, 1 ] ^ K, | \bf{z} _ i| _ 1 = 1 \} のときソフトクラスタリングといいます。z _ {ik}はデータiがクラスkに属する割合と解釈されます。

ソフトK-平均法

  • 予測
    k \in [ K ] クラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、

\begin{aligned}
z _ k = \frac{exp(-\beta ||\bf{x} - \mu _ k || ^ 2)}{\Sigma _ k' exp(-\beta ||\bf{x} - \mu _ k' || ^ 2)} 
\end{aligned}

と定めます。統計力学に出てくるカノニカル分布みたいな形をしていますね。

ちゃんとプリント読まないときついかも

  • 目的関数 K-平均法のminをsoftminで置き換えます。

\mu = \mu _ k, Z = z _ {ik}とし、


\begin{aligned}
J(\mu) = \beta ^ {-1} \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\
= \min _ {Z} \mathfrak{L}(Z, \mu) \\ 
ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\
Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。
\end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)Zについての最小化をします。


\begin{aligned}
Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\
すなわち次のようにパラメータを更新をします。\\  
z _ {ik} = 
  \left\{
    \begin{array}{11}
      1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\
      0 & otherwise
    \end{array}
  \right.
\end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)\muについての最小化をします。


\begin{aligned}
\mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\
すなわち次のようにパラメータを更新をします。\\  
\mu _ {k} = \frac{\Sigma _ i z _ {ik} \vec{x _ i}}{\Sigma _ i z _ {ik}}
\end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。

論理回路

はじめに

この記事では、論理回路について説明します。

論理回路を導入するモチベーション

まず、論理回路を導入するモチベーションをいいます。そもそも、コンピュータを利用する目的は何でしょうか。もちろんそれは人によってまちまちでしょうが、ざっくりと一言で言ってしまうと計算させるためであると言えると思います。では、どのようにしたら機械に計算させることができるでしょうか。また、そもそも”計算”とは何でしょうか。
まずは、人間が計算をするときの基本戦略を考えてみましょう。ここでは、掛け算の筆算を例にして考えます。掛け算の筆算は、まず最初に1の位を計算して、次に10の位を計算して、・・・と言うようにひと桁同士の掛け算を覚えておき(例えば筆算では、下に記録しておく)、その結果を足し合わせることで、答えを導き出しています。

実は、実際のコンピュータの計算でもこのようなアプローチを利用しています。 つまり、プリミティブな計算表を準備しておき、それらを組みあわせることで複雑な演算を実現しているのです。 掛け算の例に戻ると、人間(日本人)の場合は九九の表覚えていて、その表に書いてある答えを組み合わせることで、複雑な掛け算を実現しています。そして、コンピュータは、記憶力がいいので、九九よりももっと多くの計算結果を覚えさせておくことができます。 実際の計算では、この表として、真理値表という形式を使っています。真理値表とは、次のようなm個の入力変数の列と、n個の出力変数の列からなる表で、それぞれの変数は、0または1の値を取ります。したがって全ての入力を網羅するために、真理値表は、2 ^ m個の行を持ちます。そして、この真理値表を現実世界で具体的に実現する手段として、デジタル回路を用います。真理値表の各変数が2進数で表現されているように、すべてのデータは2進数で表現します。また、2進数の一つ一つの桁のことをビットといいます。(なぜ2進数を採用するのかは、2進数で表現するのが一番実装しやすいからであると僕理解しています。)

数の表現方法

では、具体的にコンピュータでは、二進数でどのように数を表現しているのか見ていきましょう。

負の数の表現

負の数を二進数で表現するために、一般にコンピュータでは、負の補数表現という方法が採用されています。負の補数表現では、2進数で正負を表現するために、一番頭のビットを正負を表すのに使います。一番先頭のビットが0ならば、正、1ならば負とします。そして、正の数(及び0)は、通常通り定義します。なので、例えば、4bitの場合を例として考えると、次のように、正の数および0は表わせます。

二進数表現
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111

次に負の数を考えます。さてどのように負の数を定義してあげるのが、一番都合がいいでしょうか。ここで、次のような例として、2 - 6 = -4という計算を考えてみましょう。この右辺を二進数で表すと、0010 - 0110となります。そこで、-4を表す二進数表現を????と書くと、(?には0または1が入ります。)右辺の6を移行してきて2 = 6 + -4となります。すなわち、0010 = 0110 + ????が成立してほしいわけです。これを満たすように、????をさだめると、 ???? = 1010のとき、0110 + 1010 = 10010 となり、繰り上がりを切り捨てることで、2を表す、0010と一致します。このようにして負の数も定めてあげると、負の数は以下の表のように定義できます。

二進数表現
-1 1111
-2 1110
-3 1101
-4 1100
-5 1011
-6 1010
-7 1001
-8 1000

小数の表現

実数は指数関数を利用することで定義します。例えば単精度浮動点小数では、小数を表現するのに32ビット使いますが、次のようにその32ビットの中で、役割が分かれています。ちなみに、この浮動点というのは、誤差が生じるという意味です。

| 占有ビット | 名称 | 役割 | | ---- | ---- | ---- | |0~22ビット | fraction | 仮数部(符号なし整数) | 23~30ビット | exponent | 指数部(符号付き整数) | 31ビット | s | 符号部 |

そして、以下の式によって10進法の数字と対応付けます。


(-1) ^ s \times fraction \times 2 ^ exponent


データの精度は232ですが、指数部分があるおかげで大きな数も表せるようになっています。

ブール代数

2進数の演算を実装するにあたって、まずはその演算規則、つまり代数を知る必要があります。我々は、2進数の代数としてブール代数を採用しています。この代数系は電気回路で実現しやすいというメリットがあります。

ブール代数の構成

ブール代数では、全ての変数は、0か1のうちのどちらかとなります。そして、典型的な構成では、次の3つの演算子を定義します。

Logical Sum(論理和

まず一つ目は、Logical Sum(論理和です。論理和の標準的な表現法としては、次の3パターンがあります。

  • C = A OR B
  • C = A + B
  • C = A v B

上の表現から分かるように、論理和は、2つの元から1つの元への射影となっています。その射影規則は真理値表によって下のように表せます。

A B C
0 0 0
0 1 1
1 0 1
1 1 1

二つ目はLogical Product(論理積です。論理積論理和と同様に主に3パターンの表現方法があります。

  • C = A AND B
  • C = A ・ B
  • C = A ^ B
A B C
0 0 0
0 1 0
1 0 0
1 1 1
  • Logical Negation(論理否定)

C = NOT A

C = A- C = A`

A C
1 0
0 1

これらの結合で、あらゆる真理値表を実現できる。

想定されるすべての変数を含む論理積最小項と呼ぶ。

最小項の論理和で表した論理関数のことを加法標準形または論理和標準形という。

例:Z = !ABC + A!BC + AB!C + ABCは加法標準形。
!ABC, A!BC, AB!C, ABCは最小項。ただし!XはXの否定を表す。

組み合わせ回路

組み合わせ回路とはブール代数を実現する回路のことです。

Gates

2入力1出力 AND,OR,NOTをどのようにして表すか。

簡単な論理演算回路(リレー回路) (電気回路) AND>直列 OR>並列 NOT>電磁石で離れるようにすればいい。

>>リレー回路は動作が不安定(時間がかかったら、埃が入ると動かなくなったりする)

そこで、トランジスタの登場 AND Gate,OR Gate, NOT Gate(電子回路)

演算の実装

必要な計算の例 - 四則演算 - 論理演算 - シフト演算 - 比較演算

四則計算

足し算

半加算器 真理値表による表現

x y C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

論理回路への実装
いろいろな回路が組める。(ブール代数の式の恒等変換をする。) 全加算器の真理値表 z:繰り上がりしてきた入力

x y z C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

これを32個並べると、32bitのコンピュータが実現できる。

キャリー先読み論理回路 >桁上げだけ先に計算させてしまう。

引き算

半減算器、全減算器の真理値表を作って、同じように論理回路に実装する。

コンピュータ制御でよく使われる回路

  • Decoder, Encoder
  • Multiplexer(Selector), De-multiplexer
  • Parity Check

  • 多数決回路(Majority Circuit)

Decoder

命令を2進数で0~7で定義して、Inputを与えるとそれに応じたシグナルを出す。つまり[tex:{0,1}{0,1}{0,1} \rightarrow {0,1,2,3,4,5,6,7}]という写像機械語の命令を翻訳するのに使う。

Multiplexer

スイッチング。selectorの入力によって、input0とinput1のどちらを流すかを決める。電気信号の流れを制御する。

2-to-1

真理値表による表現

Input0 Input1 Selector Output
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

ブール代数による表現

[tex: C=(A!S) + (BS)]

電気回路

Parity Checker

エラーがあったときに誤り訂正するための符号化をチェックするやつ。 1bitだけ余分に付加して、必ず信号が偶数になるように符号化する。 1bitの誤りならば、奇数になっているので気付ける。

ALU (Arithmetic Logic Unit)

 1bit数を扱う、4bit後の計算機の命令

| op1 | op0 | a | b |
- op1,op0 ... 2bitの命令 00 ... a ^ b 01 ... a v b 10 ... a + b 11 ... NOP

and,or,加算器をくみあわせる。

  • 32個つなげれば、32bitの計算機ができる。
  • 入力を4bitより増やせばよりたくさんの命令を搭載できる。

PLA(Programmable Logic Array)

どんな演算でもいらないところをユーザーが焼き切ってしまえば、実現できる。

カルノーマップ

加法標準形から回路を作ると、回路の数が大きくなってしまう。 カルノーマップ...回路を簡略化するための表 カルノーマップは4入力が限界、、、。それ以上はコンピュータに計算させる必要がある。

論理回路の基本的な作り方

  1. 真理値表を作る。
  2. ブール代数の論理式に直す。
  3. カルノーマップを作成し、簡略化する。
  4. 論理回路ゲートを使って、実装する。

東大 創造情報 院試について(2020年度冬入試)

はじめに

この度、2020年2月に行われた東京大学大学院 情報理工学系研究科 創造情報学専攻の冬院試を受験し、合格しました。
受験に際して、先人達の受験に関するブログ記事を参考にさせていただいたので、自分も今後受験する人たちのために自分の院試勉強内容、試験当日の事、その他感想などを載せておきます。 自分の経歴としては、学部は東大の数物系学科出身(理物でも理数でもない弱いとこ)、夏入試では、物理工学科を受験し一応合格しましたが、志望していた研究室に入れず、受かった研究室が正直あまり自分の興味と合わず、情報系の分野にも興味があったことから、冬に創造情報を受けることにしました。(決めたのは2019年の9月頃)。東大だと冬院試をやっている専攻は、情報学環と情報理工がありますが、情報学環の方は教授の推薦文などが必要で、用意できなかったため受けられず、情報理工の中でもググったら1番冬入試についての情報が多かったので創造情報を受けることにした、という感じです。

院試を受けようとおもった時点での実力

院試勉強開始時点でCS分野の知識はほぼほぼゼロでした。
プログラミングについては、機械学習のバイトをしていて、jupyterlabに書き捨てるようなゴミコードを書いてたぐらいでした。いわゆる競技プログラミングと言われる類のものはやった事がなかったです。9月にatcoderのABCを初めて解いた時、確かABCまで解けてDがTLEで解けなかったというのを覚えています。

やったこと

大学で情報系の授業を取りました。
具体的には、駒場で開講されている情報数理科学7(機械学習の講義)、情報工学Ⅱ(コンピュータアーキテクチャとOSについて)、情報通信理論(情報理論の一部)、情報数理科学演習Ⅱ(競技プログラミングの問題演習をする)を取りました。どれも非常にためになったので、駒場にいる人にはおすすめです()。
授業とは別に、教科書も読みました。読んだ教科書は、離散数学4〜6章、情報理論途中まで、ディジタル回路、コンピュータアーキテクチャの本途中まで、データ構造とアルゴリズム5章までです。詳しくは他の人のブログにあると思うでそれを参考にして下さい。過去問は解いてる時間がなくて、一応問題だけ眺めました。

具体的な記録

9月

とりあえず、冬入試を受けることにしたので、atcoderをはじめました。最初pythonでやっていましたが、c++のほうが早いというのを知って、c++の勉強をはじめました。

10月

バイトをたくさんしてました。

11月

TOEFLを受験しました。勉強期間は大体1週間くらいだっと思います。TOEFLはテンプレートを暗記してるのとしてないのでだいぶ点数が変わるので(多分15点くらいは変わる気がする、writingとspeakingで)、ちゃんと対策をしておいた方がいいと思いました。

12月

卒論とバイトで忙しかったです。

1月

1月の中旬ごろにやるべきことをリストアップした結果一日13時間くらい勉強をしないと終わらないことに気付き、泣きそうになりました。

2月

卒論の発表と院試の試験が被って死にそうになりました。試験終わった後は結果発表までずっとそわそわしてました。

試験当日のことについて

自分の年は、コロナが流行っていたので、中国から来た方は別の教室で受験してさせられているなどイレギュラーな感じがしました。1日目は筆記試験で、2日目がプログラミング、3日目が面接でした。

1日目(筆記試験)

卒研の発表が午前中にあって、大変でした。試験は思ったより簡単で拍子抜けしましたが、自分の年は問題が簡単だったぽくてTwitterでは満点続出だろみたいな声が結構あって、自分はわりと適当に答えた箇所も結構あったので不安になりました。(合格人数何人か知らないし)→自分の年は13人でした。

2日目(プログラミング試験)

多分そんな難しくない問題だったと思うのですが、試験中に頭が全然うごかなくなってしまって非常に焦りました。おかげで3/5解いた時点で30分くらいしか時間がなくて、後の二問は貪欲法で適当に書きました。
午後の口述試験は、入力の結果だけ見られてるような感じでした。プログラムの説明とかは全くしなかったです。あっさりしすぎててやる意味あるのか疑問に思いました。

3日目(面接)

志望分野の知識と卒業研究について聞かれました。時間は5分くらいだっと思います。

やってよかったこと

  • 情報系の授業をとる
    単位も貰えて、院試の勉強にもなってめっちゃ良かったです。

やらなくてよかったこと

  • c++の勉強
    結局pythonで、受験しました。

やれば良かったこと

  • 研究室訪問
    面接で初対面は良くなかったと思います。

  • TOEFL対策もう少し
    あと1週間やればテンプレートをもう少し覚えられたので、あと5〜10点はスコア上がりそうだなあと思いました。

  • 機械学習の勉強
    今後も使うだろうし、第三問で頻出なのでもっと重点的に勉強すれば良かったです。

点数開示

後日公開します。
自分の手答えとしては、筆記の方は、大体全部埋められて、語句の説明が微妙なのがあるかなあという感じなので、8割くらいではないかと思っています。プログラミングの方は、部分点込みで6割くらいかなあと思っています。

TOEFLの方は75点でした。60点くらいを想像してたので運が良かったのかなと思ってます。

参考にしたサイト

後日追加します。

新しく買ったWindows PCにUbuntuをデュアルブートする

はじめに

自分用メモ

環境等

19.10

必要なもの

手順

1. Ubuntuのイメージファイルを落とす

用意したusbにUbuntuiosイメージをに入れて、ライブusbを作る。

参考

Linuxをインストールできる「ライブUSBメモリ」をWindowsで作成する方法【スクリーンショットつき解説】 | LFI

2. ハードディスクのパーティションを分割する

参考

jp.easeus.com

3. UbuntuをいれたいPCのBIOS設定を変更して、ライブusbを起動できるようにする。

パソコン起動時にF10連打でbios画面に入れます。(HPのPCの場合)

4. ライブusbを挿して、PCを再起動

5. 自分の好みの設定で、Ubuntuをインストール

気を付けて選ばないとWindowsを消してしまうことになるので注意。

6. BIOSを起動して最初に起動するOSをUbuntuに変更する。

アルゴリズムと計算量、基本的なデータ構造

目次

1. アルゴリズムとは

アルゴリズムとは与えられた問題を解くための手順のことです。アルゴリズムは明確な手順を記した疑似コードという形とよばれる表現方法で記述されることが多いです。疑似コードから計算機プログラムへの変換の例として、ユークリッドの互除法アルゴリズムを紹介します。

例1-1:ユークリッドの互除法

疑似コード

Euclid(m, n) { //整数mとnの最大公約数を返す
    以下の操作を繰り返す
    mをnで割ってあまりをrとする
    もしr=0であれば、計算結果としてnを返し終了
    mにnを代入して、nにrを代入する
}

これをもう少しプログラムらしくすると下のようになります。

int Euclid(int m, int n) { //整数mとnの最大公約数を返す
    repeat
    r << mをnで割ったあまり;
    if (r = 0) return n;
    m << n, n << r;
}

新しい問題を解くためには、自分で新しい問題を解くかなければならないですが、そのためにはまず疑似コードのレベルでプログラムを設計することが大事です。

2. 計算量

アルゴリズム計算量とは、入力として与えられたデータの大きさnに対して、計算の手間がどれくらいになるかをnの関数として、見積もったものです。普通に考えるとプログラムの動作にかかる時間で議論すべきですが、これは実行する計算機の性能に依存してしまうためアルゴリズム本来の効率を議論するのに適しません。計算量という概念をもう少し明確に定義すると、正定数c,n _ 0が存在して、すべてのn > n _ 0で、T(n) \leq cf(n)となるとき、


\begin{aligned}
T(n) = O(f(n))
\end{aligned}

表記します。

3. 配列とリスト

複数のデータが順序を持って並んだもの()は計算機が扱うデータの中で最も基本的なものです。列を表現するためには大きく分けて配列による表現とリストによる表現があります。それぞれ短所と長所があるので、プログラムの目的によって適切に使い分ける必要があります。

配列

配列による表現は、あらかじめ確保された連続した領域に要素をしまうもので、列の何番目かの要素を指定すると。O(1)の計算時間で即座にその位置の要素を取り出すことのできるデータ構造です。しかし、列の途中に要素を追加する場合は、それ以降の要素を一つずつ後ろにずらしてあげる必要があり、列の途中の要素を削除する場合はそれ以降の要素を前にずらしてあげる必要があります。どちらもO(n)の計算時間がかかります。

リスト

リストによる表現は、要素一つ一つに独立した領域をもたせ、次の要素を格納している場所を示すポインタを前の要素に持たせておくことで全体を辿れるようにしたものです。配列と違いi番目の要素を取り出すには、前から順に辿って行かなければならず、O(n)の計算時間がかかります。しかし、列の途中に要素を追加したり、削除したりするのには、一つ前の要素と挿入したポインタを付け替えるだけで済むので、計算時間はO(1)で済みます。



以上のように、列へのアクセスが多く長さがあまり変わらないときは配列、逆に列の要素の追加や削除が多く、要素にアクセスするときは最初から順番に取り出すことが多い場合は、リストを使うと良いでしょう。

配列とリストの実装

通常の手続き型言語でデフォルトで用意されているのは配列です。リストを使うためには、自分で実装するか、ライブラリを利用するといいでしょう。ライブラリを利用するときは、実際の実装が明らかになってないことも多いので注意してください。

4. スタックとキュー

スタックとキューについては別の記事で説明したことがあるので、説明を割愛させていただきます。リンク先の記事を参照してください。

slimelimestech.hatenablog.com

キューの実装に当たっては、配列を用いて単純に実装すると、dequeするたびに配列を前に詰める操作が必要になってしまいます。これを避けるために一連の配列領域の先頭と最後尾がリング状に繋がっているとみなして、データの先頭番地と最後尾番地を保持する循環行列という方法があります。

5. 木

は一つの根のしたのに多数のノードが階層構造をもって接続されているデータ構造であり、一つの親ノードの下に複数の子ノードが接続された形となっています。子を持たない末尾のノードはと呼ばれます。データのアクセスは通常を起点として、中間ノードを辿っていくことで実現されます。木の表現方法としてはセルをポインタで繋いだものが一般的ですが、一つの親ノードに接続される子ノードの個数が一定である場合には配列による表現も可能です。

Linux(Ubuntu18.04)でeduroamに接続する方法

この記事の内容

eduroamにつなげるのに苦労したので、その対処法を書いておきます。

条件

  • すでにユーザーIDとパスワードは取得済みです。

詰まったところ

右上のメニューのWifiタブから、"ネットワークを選択"を選んで、eduroamに繋ごうとすると下のような画面が出てきて、どこに何を入力していいのか分からなくなりました。 f:id:slimelimes:20191129191456p:plain

解決方法

結論としては、上の2つの入力部分は無視して大丈夫です。"CA証明書が要求されましたが存在しません"にチェックを入れて、下の2つの空欄に取得したIDとパスワードをいれれば、接続できます。