🖥 Computer Science

배열로 구현한 Queue의 문제점 Queue는 배열로 구현하였을 때, 삽입과 삭제를 여러번 진행할 경우 배열의 위치가 점점 오른쪽으로 이동하게 됩니다. 즉 이렇게 구현하게 된다면, 붉게 표시된 배열의 빈 공간은 사용되지 않지만 메모리를 계속 차지함으로, 메모리 낭비를 발생시킵니다. 이를 해결하기 위한 방법으로 Circular Queue를 사용합니다. Circular Array Queue 기존의 Queue와 대부분 비슷하지만, 배열의 끝이 배열의 처음과 붙어 있는 것으로 생각합니다. 즉 다음과 같은 반지 형태를 생각하시면 이해하기 좋습니다. Circular Queue의 삽입과 삭제 즉 위와 같이 Circular Queue를 사용하면 배열의 모든 공간을 효율적으로 사용할 수 있습니다. 배열로 구현한 Circ..

Biased(편의) 편의는 다음과 같이 정의됩니다. 편의 = 추정량의 기댓값 - 모수 예를 들어 대표적인 추정량인 표본평균에 대한 편의를 구해보겠습니다. 표본평균의 기대값은 다음과 같습니다. 표본평균은 다음과 같으므로 $$\overline{X_n} = \frac{1}{n}\sum^{n}_{i=1}X_i$$ 표본평균의 평균은 다음과 같습니다. $$E(\overline{X_n})=\frac{1}{n}\cdot E(X_1+X_2+\cdots +X_n) $$ $$=\frac{1}{n}\cdot (E(X_1)+E(X_2)+\cdots +E(X_n ))$$ $$=\frac{1}{n}\cdot n \cdot E(X_1)$$ $$= \frac{1}{n} \cdot n \cdot \mu = \mu $$ 즉 표본평균(추정..

지금까지 저희가 배운 카이제곱분포와 t분포를 통해, 모수(모평균, 모분산)을 추정할 수 있다고만 하였지 실제로 하는 방법은 모른 체 넘어갔습니다. 이제부터는 이 두 분포를 사용하여 모평균과 모분산을 추정하는 방법에 대해서 알아보겠습니다. 그전에 우선 지금까지 배웠던 카이제곱분포와 T분포에서 중요한 것을들 정리하고 넘어가겠습니다. T 분포 모평균을 추정할 때 사용합니다. 정규분포를 따르는 확률변수를 정규화할 때, σ(모분산) 대신 σ'을 사용하여 정규화한다면 U와 같아지며, 따라서 정규화된 분포는 SND에서 자유도가 n-1인 t 분포로 바뀝니다. $$Z = \frac{(\overline{X}_n-\mu)}{\frac{\sigma}{\sqrt{n}}} \; \sim \; N(0, 1^{2})$$ $$\fra..

이전 글에서 순서회로(무어기계와 밀리기계)의 분석방법, 더 이전 글에서 카운터의 설계법에 대하여 알아보았습니다. 앞으로는 카운터를 포함한 일반적인 순서회로의 설계법에 대하여 알아보겠습니다. 순서회로의 설계과정 1. 설계해야 하는 회로(혹은 주어진 문제)에 대하여, 입력과 출력순서 사이의 관계를 정하고 상태표를 유도합니다. 대부분의 경우 상태그래프(상태도)를 먼저 완성한 뒤 이를 상태표로 옮기는 것이 가장 쉽습니다. 2. 표를 최소상태수로 간략화합니다. 표에 옮기기 전 상태그래프에서 상태를 간략화한 후 옮겨도 상관없습니다. 간략화 하는 과정에서는 여러 상태가 앞으로의 모든 입력에 대하여 동일한 출력을 발생시킬 경우, 이를 간략화 할 수 있습니다. 3. 간략화된 표를 통해 필요한 플립플롭의 개수를 구합니다...

밀리기계의 분석 밀리기계도 무어기계와 동일한 과정을 거칩니다. 1. 회로를 통해 플립플롭의 입력식과 출력식을 결정합니다. 2. 주어진 플립플롭의 특성식을 작성합니다. D FF (D 플립플롭) : $Q^+ = D$ D-CE FF (클럭 인에이블을 가진 D 플립플롭) : $Q^+ = D(CE) + Q(CE)'$ T FF (T 플립플롭) : $Q^+ = QT' + Q'T = Q \bigoplus T$ S-R FF (S-R 플립플롭) : $Q^+ = S + Q'R$ J-K FF (J-K 플립플롭) : $Q^+ = Q'J + QK' $ 3. 특성식을 사용하여 각 FF의 차기상태식을 작성합니다. 4. 이를 통해 전이표(차기상태표)와 전이그래프를 그립니다. 5. 주어진 입력열(Sequence)에 대해 전이그래프를 따..

CYK 알고리즘 문법이 Chomsky 정규형인 경우에만 제대로 작동하며, 다음과 같이 문제를 작은 문제로 나누어 해결하는 알고리즘입니다. Chomsky 정규형민 문법 G = (V, T, S, P)에 대하여, 문자열 w = $a_1...a_n$이 주어졌다고 하겠습니다. 문자열 w의 i번째 심벌부터 j번째 심벌까지의 부문자열을 $w_{ij}$라 하겠습니다. 즉 아래와 같습니다. $$w_{ij} = a_i...a_j$$ 또한 V의 부분집합 $V_{ij}$를 다음과 같이 정의합니다. $$V_{ij} = \left\{ A \in V \;: \; A \; \overset{*}{\Rightarrow}\; w_{ij} \right\}$$ 이때, 문자열 w는 L(G)에 속하므로, $$S \in V_{1n}$$ $V_{i..

Chomsky 정규형 Chomsky 정규형은 생성규칙의 우변에 있는 심벌들의 수를 2개 이하로 엄격하게 제한한 형태입니다. 문맥 자유 문법 G에서 모든 생성규칙이 다음의 형태를 만족하면 G를 Chomsky 정규형이라 합니다. $$A \to BC$$ 혹은 $$A \to a$$ 단 여기서 A, B, C ∈ V 이고 a ∈ T 입니다. 아래는 Chomsky 정규형의 예시입니다. $$S \to AS \;|\;a$$ $$A \to SA \;|\;b$$ 아래는 Chomsky 정규형이 아닙니다. $$S \to AS \;|\;AAS$$ $$A \to SA \;|\;bb$$ Chomsky 정규형으로 변환하기 주어진 문법 G는 람다 생성규칙과, 단위 생성규칙을 가지고 있지 않아야합니다. (가지고 있는 경우 이를 제거한 뒤..

문맥 자유 문법의 생성규칙의 우측에 나오는 문자열의 형태에는 어떠한 제약도 없습니다. 그러나 오히려 이런 제한으로 인해 복잡성이 증가하는 단점을 가집니다. 이제부터 저희는 이러한 제약 없는 문법 대신, 제한된 형태를 만족하는 동치인 문법으로 변형하는 방법을 살펴볼 것입니다. 문법의 변형 방법 빈 문자열(λ)이 나타나는 문법이나 언어는 다소 바람직하지 못합니다. 이는 많은 정리와 증명에서 별개의 역할을 하며, 특별히 주의하여야 합니다. 저희는 이러한 빈 문자열을 고려대상에서 제거하여 오직 λ를 포함하지 않는 언어만을 살펴보려 합니다. L을 문맥 자유 언어라 하고, G를 L-{λ}(L 에서 빈 문자열 제거)을 생성하는 문맥 자유 문법이라 하겠습니다. 여기서 V에 새로운 시작 심벌을 추가하고 다음의 새로운 생..