Knowledges about Java 【Interview preparation】

Introduction

This article is for my preparation of technical interview. And this focuses on programming language “Java”.

final keyword

The final keyword in Java has different meaning depending on whether it is applied to a variable, class or method.

・Variable : The value cannot be changed once initialized.
・Method : The method cannot be overridden by a subclass.
・Class : The class cannot be subclassed.

finally keyword

finally keyword is used with a try/catch block. The finally block will be executed after the try and catch blocks.

Overloading vs. Overriding

Overloading is the mechanism that we can define some functions with same name if the arguments of the function are different.

Overriding is the mechanism that we can override the function which is defined in super class.

Collection Framework

ArrayList

An ArrayList is a dynamically resizing array, which grows as you insert elements.

Vector

A vector is very similar to ArrayList except that it is synchronized. So, when the list is accessed at same time, we should not use ArrayList.

LinkedList

In LinkedList case, each element has the next element as a property. So we can add or remove an element speedy.

HashMap

We can store value with key by HashMap.

HashTable

HashTable is similar to HashMap except that it is synchronized.

TreeMap

TreeMap is a one of the Map structures. The feature is that keys are sorted. It is ascending order.

TreeMap has node which has left, right, and parent node internally. So it has binary tree.

LinkedHashMap

TreeMap is a one of the Map structures. The feature is that the order that we add elements into the map is kept.

【グラフ理論とネットワーク理論】Network and Flow #3

Introduction

Here is the article I wrote last time class.

keita-matsushita.hatenablog.com

Network and Flow

Network is defined as below.

・Network : Graph G(V, E) in which branch capacity Ci(> 0) is defined.
・f(vi, vj) : Branch flow value from vi to vj.
　(0 <= f(vi, vj) <= c(vi, vj) : c is a capacity)

And Flow is defined as below

・Flow : f = {f(vi, vj)}
・vs : Source, vt: Sink, F = Flow value
・Flow conservation equation

Outgoing flow - Incoming flow = {F for vs | -F for vt | 0 for else}

Undirected network (無向ネットワーク)

The feature of undirected network is below.

0 <= f(vi, vj) + f(vj, vi) <= c(vi, vj)

Maximum Flow Minimum Cut Theorem (最大フロー最小カットの定理)

・(X, ~X) : Cut which divides Vs and Vt at X
・Cut capacity c(X, ~X) = Σ(Vi, Vj) (X, ~X)
・Minimum cut (Xo, ~Xo) c(Xo, ~Xo) = min(c(X, ~X))

Maximum Flow Minimum Cut Theorem is defined as below

[ Maximum Flow Minimum Cut Theorem ]
Maximum flow from vs to vt is equal to Minimum cut capacity which divides vs and vt.

Maximum Flow Problem

We can calculate only the value of Maximum flow by using “Maximum Flow Minimum Cut Theorem ”. But we can not calculate the route of the Maximum flow.

This problem can solved by only Heuristic algorithm.

Minimum Cost Flow Problem

・α(vi, vj) : Cost per unit flow of branch (vi, vj) ・Problem
　Total cost = Σ α(vi, vj) f(vi, vj) → Minimum

[ Theorem ]
The necessary and sufficient condition of minimum cost flow is that here are no loops with negative cost.

AtCoder ABC056 C - Go Home

問題

時刻0に直線上の0地点にカンガルーがいる。時刻i - 1から時刻iにかけてカンガルーは現在地点pとするとp - i, p, p + 1のどれかに移動することができる。カンガルーが位置Xに到達する最短時間を求める問題。

C: Go Home - AtCoder Beginner Contest 056 | AtCoder

解法

X = 12に場合を考える。毎時刻、右に進むとき以下のようになる。(p = 位置(t = 時間)と表す)

0(0) →１(1) →３(2) →６(3) →１０(4) →１５(5)

この時、時刻t = 5の時の現在地はp = 15となりXとの差は3である。上の進み方の内、時刻２から３に変わる時に「動かない」という選択をすると最終地点は３だけマイナスとなりt = 5の時p = 12となりXに到達することができる。これは動きをしていないので最短時間での到達となる。

上記の移動方法をまとめると以下のようになる。

0(0) → 1(1) →3(2) → 3(3)→ 7(4) → 12(5)

全ての時刻で右に進んでいくと、p(position)がXを超えるときが来る。この位置の差をdiff = p - X (p >= X)と置くと、diffはこれまでのどこかの時刻で「動かない」という選択をすればpをXと一致させることができる。これは移動の仕方が、+1, +2, +3, ,,,, + tとなっているからである。

まとめると、時刻tまで全て右に進んだ時の位置はp = (1 + 2 + 3 +, ... + t)となり、(p >= X)となる最小のｔが答えとなる。

等差数列の和の公式

今回の移動方法は、全て右に進んだ場合{1, 2, 3, 4, 5, 6, …., t}となる。これは等差数列であり、この数列の項の総和は等差数列の和の公式によってO(1)で求めることができる。

等差数列の和の公式
sum = (項の数 * (初項 + 末項) / 2) = (t * (t + 1)) / 2

ソースコード

AtCoder ABC057 D - Maximum Average Sets

問題

D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder

N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、その最大の平均値となるように品物を選択する通り数を出力する問題。

解法

まずは、全列挙できるか考え見る。

全列挙による解法

品物を選択する方法を全列挙し、平均値を計算するという方法を考えてみる。全列挙の通り数は、N個の中からi(A <= i <= B)個選択する場合の数の総和となる。N個の中からi個選択する場合の数は、NCi (nCk: combination)と表す事ができる。よってΣ(A <= k <= B) nCkとなり、最大で計算量はO(2^N)なる。この場合、N = 50の時に間に合わない。よって別の解法を考える。

ソート済みの配列からA個取る解法

この問題のポイントは平均値を出すということだ。価値の配列を昇順のソートすると、先頭から後方にかけて値は小さくなる。この時、先頭からA個取った場合が平均値が最大となる。これは平均の計算方法が分母に選択した要素数を当てるからである。

次に、平均値が最大となるような品物のとり方の場合の数を考えてみる。具体的に、以下のような場合を考える。

N = 4, A = 2, B = 3
values = {20, 10, 10, 10}

上記の例では、先頭からA個、つまり２個取った場合、選択した品物の価値は{20, 10}となる。これらの値で平均値を計算したものが最大の平均値となる。しかし、A番目である10という数字はA番目以外にも存在する。つまり、平均値を計算するので、A番目以外の10を選択しても最大の平均値となる。今回はA番目と同じ数はvaluesの中に合計で３つ存在する。また、先頭からA番目までの範囲で10は１つ存在するので、平均値が最大となるには選択する品物の中に10は１つ含める必要がある。10の合計数は３つなので、平均値が最大となる選びからは、3C1通り存在することが分る。

今度は以下の例を見てみる

N = 5, A = 2, B = 3
values = {1, 1, 1, 1, 1}

この例の場合では、先頭の数字とA番目の数字が一致している。つまり、選択する全ての数字が同じ数字の場合を考える。A番目の数をVaと置いた時にvaluesの中でVaと一致する数の個数をCountVaとすると、CountVa個の中からi個選択する場合の数CountVa C iの総和(A <= i <= min(CountVa, B))となる。これは、平均値の性質で全て同じ数字であれば、選択する数を増やしても平均値は変わらないからだ。

パスカルの三角形によって組合せを求める

nCkなどのコンビネーションはパスカルの三角形によって求める事ができる。パスカルの三角形は動的計画法を使うことで計算量O(N²)で作る事ができる。

詳しくは以下を参照。

パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する - マツシタケイタの技術ブログ(勉強中)

全体の計算量

後者の解法の計算量を考える。

• 配列をソートする → O(NlogN)
• A番目の数と同じ数字を探す → O(N)
• パスカルの三角形を作る → O(N²)

よって全体の計算量はO(N²)となる。Nの最大は50なので間に合う。

ソースコード

AtCoder ABC057 C - Digits in Multiplication

問題

C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder

整数N(1 <= N <= 10¹⁰)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値する関数と定義されている。

解法

約数を全列挙する方法を考えてみる。整数iを1 ~ Nの範囲でforループさせ、Nがiで割り切れる時、A = i, B = N / iとなりA, Bを求める事ができる。F(A, B)は計算量１で求める事ができるので、全列挙した場合の計算量はO(N)となる。今回の問題ではNは最大で10¹⁰なので間に合わない。そこで計算量を減らす工夫を考える。

N = A * B = B * A という性質に注目する

N = A * B = B * Aという性質に着目することで計算量を大幅に減らす事ができる。N = 20の時を考えてみると、A = 4, B = 5の時とA = 5, B = 4の時のF(A, B)は同じ値を返す。つまり、Nの約数A, Bに関してA > Bとなる範囲は計算しなくて良いことが分る。

この条件でiの範囲を再定義すると、1 <= i <= sqrt(N) となる。(sqrt(N)はNの平方根)

これによって計算量はO(sqrt(N))となり、この問題を解くことができる。

ソースコード

【グラフ理論とネットワーク理論】Matrix Expression of Graphs and Paths #2

Introduction

Here is the article of the last time class.

keita-matsushita.hatenablog.com

Matrix Expression of Graphs and Paths

Graphs can be expressed by matrixes. Below matrixes express above the graph.

Incidence matrix (接続行列)

Cols represents branches and rows represents nodes.

+1 means that the node has outdegree from the node and -1 means that the node has indegree from the node.

Path matrix (経路行列)

Cols represents branches and row represents path.

So in above matrix means that the first path is through a1, a3 and a5.

Adjacency matrix (隣接行列)

Both cols and rows represent nodes. 1 means that there is a branch between the nodes. Adjacency matrix can express the loop of V3 node. So this matrix is very useful.

Adjacency matrix has an important theorem.

[ Theorem ]
The element of A^l represents the number of paths with l branches.

In A² matrix, the matrix has 2 in 0th row and 2nd col. This means that There are two paths from V1 to V3 with two hops. The one path is through a1 and a3. another paths is through a2 and a6. The both paths hops with 2 branches. In A³ matrix case, the number of hops become 3 as well. So, the index of power corresponds with the number of hops.

Search for Shortest Path

The distance in graph can define as below.

Distance: Sum of the length of the branch of a path
Distance graph (距離網): Graph in which distance is defined

Shortest path tree

Below graph G, T is the shortest path tree from V0 to V1, V2, V3, and V4

If T covers G, the T is called Maximum shortest path tree.

Search methods of shortest path

We want to know the shortest path in graphs whose branch have distance. The distances are not just 1. Any number can be the distance of the branches. So we can not find the shortest path by just counting the number of branches between the nodes.

There are some methods to find the shortest path

1. Heuristic method
2. Dijkstra Algorithm

【Deep Learning お勉強 #3】ニューラルネットワークとは

はじめに

前回の記事はこちら

【Deep Learning お勉強 #2】パーセプトロンを実装してみよう - マツシタケイタの技術ブログ(勉強中)

今回はニューラルネットワークについて触れる。

パーセプトロンからニューラルネットワークへ

復習も兼ねてパーセプトロンの特徴は以下の通りだった。

• 重みとバイアスを設定することで意図した出力をする関数を定義する
• パーセプトロンは計算した値が閾値を超えた時に発火しある値を出力する
• 単体のパーセプトロンでは非線形の領域は表現できないが、多層のパーセプトロンによって非線形の領域を表現することができる

また、これまでのパーセプトロンの話では、重みやバイアスは実現したいものによって手動で値を設定していた。 ANDゲートを表現する場合には、どのように重みとバイアスを設定すれば、２つの入力値をパラメータとして受け取った時にANDゲートと同じ挙動をするかを人間が考え設定する必要があった。

ANDゲートのような単純なものであれば難はないが、より複雑な処理をさせたい時に重みやバイアスのを適切に設定することは難しい。

ニューラルネットワークは重みの設定を自動化できる

ニューラルネットワークはコレを解決することができる。適切な「重み」をデータから自動で学習できるというのが、ニューラルネットワークの重要な性質の１つとなる。

つまりニューラルネットワークを用いれば、ある入力値をデータとして入れた時に、こちらが意図するような値を出力するような関数を自動で生成することができるということ。(だと認識している)

ニューラルネットワークの形態

ニューラルネットワークは以下の３つの層(入力層、中間層、出力層)に分ける事ができる。

パーセプトロンと同じような構造になっていることが分る。 それぞれのニューロンで計算された値をまた次のニューロンの入力値として受け取りさらに計算させるような構造だ。

また、ニューラルネットワークを説明する用語として「活性化関数」というものがある。

活性化関数

パーセプトロンの計算方法を思い出してみると以下のように書ける。

このh(x)のような関数と活性化関数と呼ぶ。入力信号の総和がどのような活性化(発火するか)するか決定する役割があるからだ。

つまり、これまで見てきたパーセプトロンの内部では、入力として受け取った値と設定された重み、バイアスを活性化関数によって計算され、その計算結果の値を用いて出力の内容を決定させていたと言える。

活性化関数は種類がある

活性化関数にはいくつか種類がある。代表的なものは以下の３つだ。

• ステップ関数
• シグモイド関数
• ReLU関数

ステップ関数

ステップ関数はパーセプトロンで採用されていた活性化関数だ。計算結果がある閾値を超えたらある値を出力する。

実装すると以下のようになる。

また、ステップ関数をグラフにすると階段上になる。

シグモイド関数

シグモイド関数は、ニューラルネットワークでよく用いられる関数の１つである。

実装すると以下のようになる。

シグモイド関数をグラフにすると、ステップ関数を滑らかにしたような曲線を描かれる。

ニューラルネットワークでは非線形関数を用いる

ニューラルネットワークの性質を変えるものはどの活性化関数を選ぶかということだ。 活性化関数は非線形関数で無ければならない。

ニューラルネットワークは活性化関数を何層も重ねて複雑な処理している。もし、活性化関数がh(x) = cx (cは定数)のような線形関数の場合、層を重ねる意味がなくなってしまう。仮にy(x) = cxを３層に重ねてみるとy(x) = c^3xと表現できてしまい、層を重ねる事に意味がなくなってしまう。

層を重ねることの恩恵を受けるために、活性化関数に非線形関数を使う必要がある。

ニューラルネットワークの計算には行列の内積を使う

ここまでで、ニューラルネットワークの内部ではどのような計算が行われているかが分かった。まとめると以下のようになる。

1. 入力層で受け取った入力データを活性化関数によって計算する
2. 活性化関数で計算した値を中間層のニューロンの入力値として、受け取り、活性化関数によって再び計算される。(中間層は複数の層になる場合もある)
3. 中間層によって計算された値を出力層によって出力する。

※出力層の挙動は後述する。

つまり、最終的な出力を得るまでに、かなりの量の計算をする必要がある。入力データの量、ニューラルネットワーク内のニューロンの数が膨大になれば計算時間がすごいことになってしまう。

しかし、行列の内積を用いることで計算量を大幅に減らすことができる。

出力層の設計

出力層の設計の仕方も何パターンかあるようだ。出力層の設計を決定させるためには、どんな問題を解きたいかによる。機械学習の問題は大きく以下の２つに分ける事ができる。

• 「分類問題」：データがどのクラスに属するかを解く問題
• 「回帰問題」：入力データから数値の予測を行う問題

どの問題を解くかで、出力層にどの関数を設定するべきか決める事ができる。分類問題を解くためには、よくソフトマックス関数が用いられる

ソフトマックス関数

k番目のニューロンのソフトマックス関数によって出力される値は、出力層の１つ手前の層の全てのニューロンからの計算結果の和を分母として、k番目のニューロンの計算結果を分子として計算される。

この性質は確率分布として表現できる

ソフトマックス関数は確率分布を表現する

ソフトマックス関数によって出力された値は、上記の性質により0.0 ~ 1.0の間の少数値を取る。そして、出力層から得られた全ての出力値の総和は１となる。これは確率の性質と同じである。

つまり、ソフトマックス関数を使うことで確率分布を表現することができる。

最後に

ここまでで、ニューラルネットワークの構造や内部での計算方法などを知ることができた。しかし、まだ重みの設定を自動化する話は登場していない。次の章をちら見すると「ニューラルネットの学習」とある。おそらくこの学習によってニューラルネット内のパラメータを設定しているのだろう。