오전 1（午前１）
문제 1
ATM이 1대씩 설치되어 있는 2개의 지점을 통합하고, 통합 후의 지점에는 ATM을 1대 설치한다. 통합 후의 ATM의 평균 대기시간을 구하는 식은 무엇인가. 여기서 대기시간은 M/M/1 대기행렬모델을 따르고, 평균 대기시간에는 서비스 시간을 포함하여 ATM을 1대에 통합해도 충분히 처리 가능한것으로 한다.
해석
- ATM의 평균 서비스 시간 = 한 고객이 ATM을 사용하는 평균 시간
- 이용률 = 단위 시간당 ATM이 사용되는 비율
- 통합 전, 각 지점의 ATM의 평균 서비스 시간과 이용자 수는 동일
따라서 이용률은 단순히 2배인 2ρ가 됨
모형식의 평균 대기시간 공식은 이용률/1-이용률 x 평균 서비스 시간
### 대기행렬이론(Queueing theory) M/M/1 모형
가장 단순한 형태의 모형.
서버의 수가 1명이고 시스템 내 수용 인원과 고객 모집단에 한계가 없는 모형. -> 현금 지급기
이 모형은 현재 시스템 내에 몇명의 고객이 존재하든지 도착률과 서비스율이 일정.
문제 3
각 노드가 가진 데이터를 출력하는 재귀처리 f(노드 n)을 정의했다. 이 처리를 그림의 2진 트리의 뿌리(최상위 노드)에서 시작했을 떄의 출력은 무엇인가
f(노드 n)의 정의
- 노드 n의 오른쪽에 자식 노드 r이 있다면 f(노드 r)를 실행
- 노드 n의 왼쪽에 자식 노드 l이 있다면 f(노드 l)를 실행
- 재귀처리 f(노드 r), f(노드 l)을 미실행한 자식 노드, 혹은 자식 노드가 없다면 노드 자신이 가진 데이터를 출력
- 종료
해석
f(노드 n)의 순서는 오->왼->중 으로 진행됨
자식 노드가 사라진 시점에서 자신의 데이터를 출력하는 방식을 후행 순서의 깊이 우선 탐색이라고 함
DFS(Deep-First-Search) 깊이 우선 탐색
그래프 순회 방식의 일종
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트를 탐색하는 방식.
일반적으로 재귀호출을 사용하여 구현, 단순한 스택 배열로도 구현 가능.
구조상 스택 오버플로우에 유의하여야함.
단순 검색 속도는 BFS(Breadth-First-Search)보다 느림.
순회(Traversal) 할 경우에 많이 쓰임.
리프 노드에만 데이터를 저장하는 정렬 트리 구조에서 항상 순서대로 데이터를 방문한다는 장점 존재.
자동 미로 생성에 많이 사용됨.
장점
- 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다
단점 - 해가 없는 경로에 깊이 빠질 가능성.
- 얻어진 해가 최단 경로가 아닐 가능성.
- DFS는 해에 다다르면 탐색을 끝내기 때문에, 경로가 다수의 경우 최적의 해를 구하질 못할 가능성 존재
문제 4
양자 게이트 방식의 양자 컴퓨터의 설명으로 적절한 것은?
해석
양자 게이트 방식은 0과1이 확률적으로 공존하는 양자 비트를 준비하여 그것을 양자 게이트에 통과하는 것으로 계산하는 방식
문제 5
시스템의 신뢰성설계에 관한 기술로 적절한 것은?
해석
フェールセーフ(Fail Safe): 고장이 발생할 경우, 더 위험한 상황이 되는 것이 아니라 더 안전한 상황이 되도록 하는 설계
フォールトトレランス(Fault Tolerance): 시스템을 구성하는 부품의 일부에서 결함이나 고장이 발생해도 정상/부분적으로 기능 수행이 가능
フォールトアボイダンス(Fault Avoidance): 설계를 잘 해서 장애 발생확률 자체를 낮추는 것
ファールソフト(Fail Soft): 장애가 발생했을 때, 다소의 기능 제한과 성능 저하를 허용해서, 시스템 전체의 운전 지속에 필요한 기능을 유지하는 설계 방식