컴공생의 발자취

분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 선택 문제(Selection Problem) : k번째 작은 수를 찾는 문제 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k번째 작은 수가 들어 있는 부분을 순환적으로 탐색한다. unsorted array : 최소 숫자를 k번 찾는다. -> 최악 시간복잡도 : O(kn) ** 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거한다. sorted array : 숫자들을 정렬한 후, k번째 숫자를 찾는다. -> 최악 시간복잡도 : O(nlogn) pseudo code Selection(A, left, rig..

7.1 진동수는 물체가 단위시간 동안 진동하는 횟수를 의미하며 1Hz는 1초동안 물체가 1번 진동하는 것을 의미한다. 따라서, 시스템 버스의 대역폭 = 버스 클록 × 데이터 버스의 폭 = 300MHz × 64bit = 300MHz × 8Byte = 2.4GByte/sec 7.2 동기식 버스는 인터페이스 회로가 간단하다. 비동기식 버스는 각 버스 동작이 완료되는 즉시, 연관된 다음 동작이 발생되므로 동기식 버스에서와 같이 낭비되는 시간이 없다. 7.3 병렬 중재 방식은 각 버스 마스터들이 독립적인 버스 요구 신호와 버스 승인 신호를 가지고 있어 직렬 중재 방식보다 버스 마스터들이 버스를 균등하게 사용할 수 있도록 해준다. 직렬 중재 방식은 요구 및 승인 신호 선이 각각 한 개씩만 있어 하드웨어 구현이 간단..

6.1 원형 평판 1개의 저장 용량 = {(트랙의 수 × 섹터의 수) × 섹터의 용량} × 2 = {(100000 × 500) × 512Byte} × 2 = 10^8 × 512Byte = 10^8 × 2^(-1) × 2^10Byte = 50GByte (2^10 ≒ 10^3)이므로 디스크 드라이브의 저장 용량 = 50GByte × 5 = 250GByte이다. 6.2 (1) 표면 당 저장 용량 = 표면당 트랙 수 × 트랙당 섹터 수 × 섹터당 데이터 필드의 길이 = 4800 × 200 × 512Byte = 491520000Byte = 491.52MByte (2) 탐색 시간 = 현재 트랙에서 액세스 요구한 트랙까지의 거리 × 트랙당 탐색 시간 = (4800 – 3250 + 450) × 0.0024ms = 4...

5.1 평균 기억장치 액세스 시간 = ML1의 액세스 시간 × ML1의 적중률 + ML2의 액세스 시간 × (100 - ML1의 적중률) = 20ns × 90% + 200ns × 10% = 20ns × 0.9 + 200ns × 0.1 = 18ns + 20ns = 38ns 5.2 식 = ML1의 액세스 시간 × ML1의 적중률 + ML2의 액세스 시간 × (100 - ML1의 적중률) ML1에 대한 적중률 식 평균 기억장치 액세스 시간 0% 10ns × 0 + 100ns × 1 100ns 20% 10ns × 0.2 + 100ns × 0.8 82ns 40% 10ns × 0.4 + 100ns × 0.6 64ns 60% 10ns × 0.6 + 100ns × 0.4 46ns 80% 10ns × 0.8 + 100n..

4.1 제어 기억장치의 용량이 256단어이므로 사상 함수는 8비트이다. 또한 실행 사이클 루틴이 제어 기억장치의 절반 후반부에 저장되므로 최상위 비트는 1이고, 실행 사이클 루틴이 최대 8개의 마이크로-연산들로 구성되어 있으므로 사상 함수는 1XXXX000이다. 4.2 제어 기억장치의 용량이 128단어이므로 사상 함수는 7비트이다. 또한 실행 사이클 루틴이 제어 기억장치의 처음 절반 부분에 저장되므로 최상위 비트는 0이고, 실행 사이클 루틴이 최대 4개의 마이크로명령어들로 구성되어 있으므로 사상 함수는 0XXXX00이다. 4.3 (1) 실행 사이클 루틴이 제어 기억장치의 절반 하반부에 저장되므로 최상위 비트는 1이고, 연산 코드가 5비트이고 최대 8개의 마이크로명령어들로 구성되어 있으므로 사상 함수는 1..

3.1 부호화 크기는 맨 좌측 비트가 부호비트이고, 나머지 비트들은 수의 크기를 나타낸다. 어떤 양수에 대하여 1의 보수와 2의 보수로 표현한 결과는 동일하다. (1) 8-비트 길이의 부호화-크기 : 0001 0011 1의 보수 : 0001 0011 2의 보수 : 0001 0011 (2) 8-비트 길이의 부호화-크기 : 1001 0011 1의 보수 : 1110 1100 2의 보수 : 1110 1101 (3) 8-비트 길이의 부호화-크기 : 0111 1100 1의 보수 : 0111 1100 2의 보수 : 0111 1100 (4) 8-비트 길이의 부호화-크기 : 1111 1100 1의 보수 : 1000 0011 2의 보수 : 1000 0100 3.2 부호-비트를 확장하는 경우 부호화-크기 표현에서는 부호 비..

2.1 인출 사이클의 마이크로 연산 : t0 = MAR ← PC t1 = MBR ← M[MAR], PC ← PC + 1 t2 = IR ← MBR 실행 사이클의 마이크로 연산 : t0 = MAR ← IR(addr) t1 = MBR ← M[MAR] t2 = AC ← MBR 따라서 총 6 클록이 소요되고 주기가 0.5ns 이므로 명령어를 인출하고 실행하는데 걸리는 시간은 총 6 × 0.5ns = 3ns이다. 2.2 (1) (2) ‘SUB 301’명령어가 실행 되는 중이므로 PC는 202, AC는 0004, IR은 6301, SP는 0999가 저장되어 있다. 여기서 인터럽트 요구가 들어온다면 ① PC의 값이 SP가 가진 값의 주소에 저장되고 ② PC에는 인터럽트 서비스 루틴의 시작 주소가 저장되며 ③ SP에는 ..

분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 퀵 정렬(QuickSort) 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준 피봇보다 작은 숫자들은 왼쪽, 큰 숫자들은 오른쪽으로 위치하도록 분할 분할된 부분문제들에 대해서도 위와 동일한 과정으로 재귀적으로 수행 개념 설명 ** 해당 설명에서 pivot은 무작위로 정해짐 ** pseudo code QuickSort(A, left, right) 입력 : 배열A[left] ~ A[right] 출력 : 정렬된 배열A[left] ~ A[right] if(left < right){ 피봇을 A[left] ~ A[right] 중에서 선택하고 피봇을 A[left..

분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 합병정렬(MergeSort) : 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 n개의 숫자들을 n/2개의 부분문제로 분할(Divide) 각각의 부분문제들을 해결(Conquer) 재귀적으로 합병 정렬(Merge) 개념 설명 Pseudo code MergeSort(A, p, q) 입력 : A[p] ~ A[q] 출력 : 정렬된 A[p] ~ A[q] if(p < q){ // 배열의 원소의 수가 2개 이상이면 k = [(p+q)/2] // k : 반으로 나누기 위한 중간 원소의 인덱스(내림으로) MergeSort() // 앞부분 재귀..

1.1 1)시스템 버스 : cpu와 다른 요소들 간의 정보교환 통로. 주소 버스, 데이터 버스, 제어 버스로 나누어져 있다. 2)VLSI : Very Very Large Scale IC. 수백만 개 이상의 트랜지스터들이 집적되는 32-비트급 이상의 마이크프로세서 칩들과 수백 메가바이트 이상의 반도체 기억장치 칩들 및 앞으로 출현할 고밀도 반도체 칩들을 지칭하기 위한 용어이다. 3)폰 노이만 아키텍쳐 : 폰 노이만이 제안한 컴퓨터 구조 설계 개념. 기억장치에 저장된 프로그램을 프로그램 카운터가 지정하는 순서대로 실행시킨다. 4)기억장치 엑세스 : 기억장치에 데이터를 쓰거나, 저장된 내용을 읽는 동작이다. 기억장치들은 액세스 되는 방식에 따라 여러가지로 분류될 수 있다. 1.2 1) 2의 7승= 128 가지..