🖥 Computer Science

프로그램의 내부 응용 프로그램을 실행하기 위해서는 응용 프로그램이 필요로 하는 여러가지 기능을 구현하는 복잡한 소프트웨어 라이브러리를 사용하게 됩니다. 반면 컴퓨터의 하드웨어는 아주 단순한 저수준의 명령어(인스트럭션)를 실행할 수 있을 뿐입니다. 따라서 응용 프로그램을 컴퓨터에서 실행하기 위해서는 작성된 복잡한 작업들을 아주 단순한 명령어로 번역하는 과정이 필요합니다. 이러한 과정을 여러 계층의 소프트웨어 추상화(Abstraction)를 통해 가능하게 만들었습니다. 소프트웨어 계층은 아래와 같이 구성됩니다. 응용 소프트웨어(Application software, 응용 프로그램)가 계층의 가장 바깥쪽에 위치하며, 여러가지 시스템 소프트웨어(System software)가 하드웨어와 응용 프로그램 사이에 존..

컴퓨터의 워드 길이 모든 컴퓨터는 워드(word) 크기를 규격으로 가지게 되는데, 이는 메모리에서 레지스터로 데이터를 옮기거나, ALU을 통해 데이터를 조작하거나 할 때, 하나의 명령어로 실행될 수 있는 데이터 처리 단위입니다. 하나의 가상주소는 한 개의 워드로 인코딩됩니다. 즉 이 워드 크기를 결정하는 가장 중요한 시스템 변수가 가상 주소공간의 최대 크기입니다. $\omega $ 비트 워드 크기를 갖는 컴퓨터에서, 가상주소는 0에서 $2^\omega - 1$ 의 범위를 가지며, 프로그램은 최대 $2^\omega$ 바이트에 접근할 수 있게 됩니다. 예를 들면 32비트 컴퓨터에서 주소 범위는 4GB로 제한되며, 64비트 워드 컴퓨터는 16 엑사바이트(EB), x86-64 컴퓨터는 48비트 주소를 지원하므로..

컴퓨터 시스템 컴퓨터 시스템은 하드웨어와 시스템 프로그램(시스템 소프트웨어)으로 구성되며, 이들이 함께 작동하여 응용 프로그램(응용 소프트웨어)을 실행합니다. (프로그램과 소프트웨어는 동일한 의미의며, 앞으로 두 단어를 번갈아가며 사용하여도 차이는 없다는 것을 미리 말씀드립니다.) 하드웨어는 프로세서, 메인 메모리, 입출력 장치들로 구성되어 있습니다. 시스템 소프트웨어는 컴파일러와 운영체제 등으로 구성됩니다. 응용 프로그램은 고급 언어로 작성됩니다. 정보는 비트와 컨텍스트로 이루어집니다 소스 프로그램은 0과 1로 표시되는 비트들로 구성되어 있습니다. 프로그램의 텍스트 문자는 바이트로 나타내어지는데, 바이트는 8비트 단위로 구성됩니다. 대부분의 컴퓨터 시스템에서 텍스트 문자는 아스키(ASCII) 표준을 사..

🧐 분할 정복이 뭐예요? 일반적으로 어떠한 문제를 더 작은 문제로 분할하고, 분할한 문제들을 해결한 후 조합하여 큰 문제를 해결하는 알고리즘을 의미합니다. 과정을 나열하자면 다음과 같습니다. 1. 주어진 문제를 더 작은 문제(Subproblem)으로 나눕니다. 이때 작아진 문제는 본질적으로 큰 문제와 동일하나 단지 입력(input)의 크기만 작아진 문제를 의미합니다. 2. 1번 과정에서 나눈 Subproblem 들을 재귀적으로(더 작은 문제로 나누며) 해결합니다. 3. 2번에서 해결한 Subproblem들의 답을 적절하게 조합하여, 기존 큰 문제의 답을 도출합니다. 1번의 과정은 Divide 2, 3번의 과정은 Conquer 과정에 해당합니다. 🧐 분할 정복의 일반적인 패턴 분할 정복은 일반적으로 다음과..

🧐 곱하기 알고리즘 성능 분석 우리가 흔히 곱하기 계산을 할 때 사용하는 방법을 통해 n-bit 이진수 곱하기 알고리즘의 시간 복잡도를 구해보도록 하겠습니다. 우선 일반적인 계산 과정은 아래와 같습니다. 곱하기의 계산에서는 곱하는 수(y)의 각 bit에 대하여, 이동 연산(주항색 화살표로 표시)을 진행하게 됩니다. 첫 과정에서는 0번, 두번째 과정에서는 1번, 세번째 과정에서는 2번, .... n번째 과정에서는 n-1번의 이동 연산이 필요합니다. 즉 이를 빅오 표기법을 통해 나타내면 다음과 같습니다. $$O(1) + O(2) + \cdots + O(n-1) = O(n^{2})$$ 이동 연산을 모두 진행한 후에는, 최대 2n bit로 이루어진 숫자 n개에 대하여 add 연산을 진행해야 합니다. 이때 한번의..

🧐 알고리즘? 어떤 문제를 풀기 위한 유한한 절차와 방법을 의미합니다. 위 정의에서의 '문제'는 보통 입력값이 동일한 경우 출력값이 동일한(= 수학적으로 엄밀히 정의된) 문제를 의미합니다. 절차와 방법? 저희는 계산 문제를 풀 때 숫자와 사칙연산을 이용하여 문제를 풀이하는 것 처럼 컴퓨터로 계산 문제를 풀기 위해서는 컴퓨터에 주어진 명령어 집합(instruction set)을 이용하여 풀이합니다. 🧐 알고리즘의 성능 분석 알고리즘의 성능을 분석하는 방법으로는 실제로 시작시간과 종료시간을 측정하여 분석하는 실험적 분석과, 이론적으로 기술하여 성능을 측정하는 이론적 분석 방법이 있습니다. 실험적 분석은 때때로 유용하지만, 다양한 외부 요인들(예를 들어, 컴퓨터의 하드웨어 사양)에 의해 성능을 정확하게 분석할..

서론 앞서 배운 유한 오토마타와 푸시다운 오토마타를 비교해보면, 임시 저장장소의 특성이 둘 사이의 차이를 만들어냄을 알 수 있습니다. 만약 저장장소가 없다면 유한 오토마타이며, 저장장소가 스택이라면 유한 오토마타보다 더 강력한 푸시다운 오토마타를 갖게 됩니다. 만약 오토마타에 좀 더 유연한 저장장소를 더해준다면, 더욱 강력한 언어군을 발견할 수 있을 것입니다. 예를 들어 두 개, 세 개의 스택, 큐, 또는 다른 저장 장치를 사용한다면 어떤 결과가 나올까요? 각각의 저장장소는 새로운 종류의 오토마타를 정의하고, 그것을 통하여 새로운 언어군을 정의할 수 있을까요? 이러한 접근은 대부분의 경우 흥미로운 결과를 이끌어내지는 못했습니다. 가장 강력한 오토마타와 계산의 한계에 대하여 무엇을 이야기할 수 있을까요?..

문맥-자유 문법은 유한 오토마타로는 인식될 수 없으며, 푸시다운 오토마타에 의해서 인식될 수 있습니다. 푸시다운 오토마타는 오토마타와 비슷한 생김새를 지녔으나, 스택(Stack)을 추가로 사용합니다. 비결정적 푸시다운 오토마타 (NFDA) 푸시다운 오토마타는 다음과 같이 표현됩니다. 제어 유닛의 각 움직임은 입력 파일로부터 하나의 심벌을 읽고, 동시에 스택 연산을 통하여 스택의 내용을 바꿉니다. 제어 유닛의 각 움직임은 현재의 입력뿐 아니라, 현재 스택의 Top에 있는 심벌에 의하여 결정됩니다. 움직임의 결과는 제어 유닛의 새로운 상태와 스택의 톱에서의 변화입니다. 비결정적 푸시다운 인식기 (nondeterminisitc pushdown acceptor, npda)는 다음과 같이 정의됩니다. $$M = ..