필기용 블로그

○DFA from NFA

 ▷Set of L(M_DFA) ⊆ Set of L(M_NFA)

  ▷DFA는 NFA의 일종이다.

 ▷어느 한 NFA가 있으면 L(M_DFA) = L(M_NFA)인 DFA가 존재한다.

 ▶DFA - derivation from NFA

  ▷DFA -> D = (Q_D, Σ, δ, S_0, F_D)

  ▷NFA -> N = (Q_N, Σ, Δ, q_0, F_N)

  ▷1. Start State에 대한 λ-Closure 구하기 -> S_0

  ▷2. S_0에 대한 Reachable State Set -> S_1, S_2, ... (Set이 다르면 State도 다르다.)

  ▷3. 이전 State에 대한 Reachable State. -> S_n ...

  ▷4. NFA의 Final State를 포함하는 Set을 의미하는 State -> DFA의 Final State

○NFA from Regular Expression

 ▷Regular Expression에 대해 이를 의미하는 NFA가 존재한다.

 ▶Tompson's Algorithm

  ▷다음 NFA의 Recursive Contruction을 이용해서 Regular Expression을 표현할 수 있다.

  ▷State가 많아지지만, 매우 쉽게 만들 수 있다.

  ▶속성

   ▷Number of states ≤ 2×number of steps

   ▷N은 단 하나의 Start State와 Final State를 가진다. (Final State 에서는 나가는 State가 없다.

   ▷하나의 Outgoing edge를 가지거나, 최대 2개의 Outgoing λ-edges르 가진다.

◎(0 + 11)*

○Regular Expression from DFA

 ▷Language of DFA를 의미하는 Regular Expression이 존재한다.

 ▶Algorithm

  ▷DFA M = ( {q_1, q_2, ... , q_n}, Σ, δ, q_1, F)

  ▷R_ij^k : k보다 높은 State를 거치지 않고 q_i에서 q_j로 가는 String (도착은 OK)

  ▷L(M) = ∪_q_final∈F R_1f^n

○Memory Mountain

 ▷Spatial, temporal locality에 따른 Read throughput을 비교하기 위한 3차원 그래프

 ▷테스트 코드

 ▷결과

  ▷Spatial locality (Stride) : 읽는 간격이 커질수록 느려짐.

  ▷Temporal locality (Size) : 읽는 데이터 크기가 커질수록 상위 Cache에 데이터를 저장하지 못하고, 계단형식으로 느려지게 됨.

○Memory Performance Improvement

 ▶Spatial locality 개선

  ▷반복문의 순서/알고리즘을 바꿈으로 spatial locality를 개선할 수 있다.

  ▷열 접근 - 행 접근으로 바꿀수 있으면 spatial locality를 크게 개선 가능

  ◎Matrix Multiplication 알고리즘들

 ▶Temporal locality 개선

  ▷Block을 적게 읽어들이기 위해 Block 단위 Subloop를 만듬으로써 temporal locality를 개선할 수 있다.

  ◎Matrix Multiplication을 Block-Size로 subloop한 것.

   ▷cache miss : 2n/B × B²/8 = nB/4, nB/4 × (n/B)² = 1/(4B) × n³

   ▷일반적인 Matrix Multiplication과 비교 : 9/8 × n³

○Thread

 ▷프로그래밍을 돕기 위해 동시에 독립적으로 실행되는 단위

 ▷process보다 가볍다. (한 Process는 여러 Thread를 가질 수 있다.

 ▶Thread 생성

  ▶1. Runnable Interface를 implement

   ▷public void run() 함수를 가지고 있다.

   ▷해당 함수가 종료되면, Thread는 종료된다.

   ▷만든 Runnable을 Thread의 생성자에 넣는다.

   ▷t.start() -> Thread 시작

  ▶Thread 상속

   ▷상속받은 class에서 run()을 정의한다.

   ▷해당 클래스의 객체를 만들고, start() -> 시작

 ▶Sleep - Thread.sleep(int ms)

  ▷Thread의 동작을 일시적으로 멈출 수 있다. (ms단위)

 ▶Interrupt - thread.interrupt()

  ▷해당 thread에서 interrupt 신호를 전달한다.

  ▷보통 thread를 종료시킬 때 자주 사용한다.

  ▶interrupt 동작 정의

   ▶catch (InterruptedException e)

    ▷interrupted하면 catch한다. (try ~ catch문)

   ▶thread.interrupted()

    ▷interrupt 당했다면 true, 아니면 false

    ▷if문에 넣어서 주로 체크한다.

 ▶Join - thread.join(int ms)

  ▷해당 thread가 끝날 때 까지 기다린다 (ms단위)

  ▷인자가 없거나, 0이라면 무한히 기다린다.

  ▷thread.isAlive()를 통해 살아있다면, join을 더 추가할수도 있다.

 ▶ReeentrantLock

  ▷import java.util.concurrent.locks.*

  ▷lock = new ReentrantLock()

  ▷Race Condition을 방지하기 위해 사용함.

   ▷Thread들은 한 Process에서 위치를 공유하기 때문에, 동시에 같은 변수/메소드를 참조하면 예상치 못한 결과가 일어날 수 있다.

  ▶lock(), unlock()

   ▷하나의 Thread가 bankLock.lock() 메서드를 호출하면, 다른 Thread는 lock()에 접근해도 unlock()되기 전까지 대기한다.

   ▷try 전에 lock을, finally에 unlock을 두고 try 내에 Critical section을 놓는다.

  ▶Condition Object

   ▷다른 쪽에서 signal을 보낼 때 까지 lock을 반환하고 대기할 수 있다.

   ▷condition = reentrantLock().newCondition()

   ▷condition.await() : signal을 받을 때 까지 대기한다.

   ▷condition.signalAll() : 모든 기다리는 Thread를 깨운다.

   ▷condition.signal() : 해당 condition를 깨운다.

  ▶synchronized

   ▷reentrantLock을 간단하게 표현 가능하다

 ▶ThreadLocal<T>

  ▷Thread는 위치를 공유하기 때문에, 같은 Thread Class는 변수들을 공유한다.

  ▷ThreadLocal<T> : Local 변수처럼 사용 가능

 ▶기타 메소드

  ▷Thread.currentThread() : 현재 Thread의 정보.

○Process

 ▷실행중인 프로그램

 ▶생성 : Process 클래스로 또 다른 프로그램을 실행 가능하다.

  ▷Process proc = Runtime.getRuntime().exec("프로그램명");

  ▷Process proc = new ProcessBuilder("cmd", "\c", "dir").start();

 ▶Input/Output/Error 상호작용

  ▷만들어진 프로세스와 input/output/error steams를 주거나 받을 수 있다.

  ▶InputStream 선언 : InputStream in = proc.getInputStream()

   ▷읽기 : in.read(buffer, off, len) - buffer는 byte[], byte[off]부터 len개, return: 읽은 byte 수

   ▷닫기 : in.close

  ▶OutputStream 선언 : OutputStream out = proc.getOutputStream()

   ▷읽기 : out.write(buffer) - buffer는 byte[], byte[off]부터 len개

   ▷닫기 : out.close

○Non-determinstic Finite Automata

 ▶다음과 같은 5개의 요소들로 구성된 FSM (N = (Q, Σ, Δ, q₀, F))

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷Δ: Q×(Σ∪{λ})×Q - transition relation의 subset -> 라벨이 있는 directed edge

  ▷q₀: start state (q0 ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▷input character에 대해 하나 이상의 transition이 존재한다.

  ▷deterministic : 각 input에 대해 단 하나의 transition

 ▷λ-transition이 가능하다.

 ▷Final State에 도착하는 하나 이상의 길이 있다 -> Acceptable String

 ▶Transition function (Δ_f)

  ▷Transition relation을 Function으로 취급한 것

  ▷Δ_f : Q x ( Σ ∪ {λ} ) -> ρ(Q)

   ▷ρ(Q) : power set of Q

 ▶Extended Transition Function (Δ_s)

  ▷Transition relation의 집합

  ▷Δ_s = ρ(Q) x ( Σ ∪ {λ} ) -> ρ(Q)

  ▷Δ_s(P, a) = ∪_q∈p Δ_f(q,a)

 ▶λ-Closure ( E(q) / E_s(P) )

  ▷E(q) : 어떤 Symbol도 읽지 않고 도달 가능한 State들의 집합

  ▷원래 State + λ를 통해 이동가능한 State

  ▷E_s(P) : ∪_q∈P E(q)

 ▶Reachable State Function ( Δ^*(q, s) )

  ▷State q에서 String w을 읽었을 때 도달 가능한 State set

  ▷NFA를 해석하는 방법. (Update)

  ▷Δ^* : Q × Σ^* -> ρ(Q)

 ▶NFA Language

  ▷해당 NFA에서 Accepted되는 Language들

  ▷Δ^*(q₀, w)가 하나 이상의 Final State를 가진다.

 ▶NFA Design

  ▷일반적으로 DFA Design보다 쉽다.

 ◎Regex (010+01)* 허용하는 String

 ◎Regex (0+1)*1(0+1) 허용하는 String