메타 스터디 그룹

제129회 예상문제(토픽)

정보관리 118회 3교시

6. 당신은 어느 한 프로젝트의 PM이다. 아래 사항을 참조하여 다음을 설명하시오.(문경숙)
-----------------------------------------------------------------------------------------------
1. 프로젝트 수행기간의 목표는 25일이다.
2. A 액티비티는 소요기간이 10일이다.
3. B 액티비티는 A 액티비티가 완료된 후에 시작할 수 있으며, 소요기간이 13일이다.
4. C 액티비티는 소요기간이 12일이다.
5. D 액티비티는 C 액티비티 완료된 후에 시작할 수 있으며, 소요기간이 15일이다.
-----------------------------------------------------------------------------------------------
가. 네트워크 다이어그램을 작성하시오.
나. 주경로의 수행기간을 계산하시오.
다. 목표 수행기간을 맞추기 위해서 수행기간을 단축할 수 있는 방법을 설명하시오.
라. 일정을 단축하기 위해 기존팀원 5명에 더해 팀원 1명을 추가로 투입하였다. 의사소통 수(커뮤니케이션 통로의 수)가 기존보다 얼마나 더 늘어나는지 계산하시오.
마. 프로젝트 획득가치관리(Earned Value Management)보고서에 EV=95백만원, PV=110백만원, AC=100백만원, BAC=950백만원이다. CV와 CPI를 구하고 현재까지의 작업효율이 유지될 경우의 EAC를 계산하고 설명하시오.
(단, EV : Earned Value, PV : Planned Value, AC : Actual Cost, BAC : Budget At Completion,
CV : Cost Variance, CPI : Cost Performance Index, EAC : Estimate At Completion이다.)

문6) 1)네트워크다이어그램, 2)주경로 수행기간계산, 3) 수행기간단축방법, 4) 의사소통수증가량계산 5) CV, CPI, EAC 계산, 설명

답)

I. 네트워크 다이어그램

[활동 표현방법 예]

여유시간=늦은종료일(LF)-빠른종료일(EF)=늦은 개시일(LS)-빠른 개시일(ES)

II. 주경로의 수행기간 계산

- 주공정법(Critical Path Method)은 프로젝트의 최소 기간 결정에 사용되는 일정 네트워크 분석 기법

- 주공정 경로(Critical Path)는 여유시간(float)이 '0'인 활동을 연결한 최소 경로

-. 프로젝트 목표는 25일이나 현재 프로젝트 주경로 수행기간은 27일. 프로젝트를 성공적으로 수행하기 위해서 2일의 일정단출이 필요함

-. 일정 단축기법인 공정압축법(Crashing)과 공정중첩 단축법(Fast Tracking) 활용하여 기간 단축 수행

III. 목표 수행기간을 맞추기 위해서 수행 기간을 단축할 수 있는 방법 설명

IV. 기존 팀원 5명에 더해 팀원 1명 추가 투입, 의사소통수 증가량 계산

-. 의사소통채널수=N*(N-1)/2

기존대비 추가 인력 1명 투입시 의사소통채널수는 6증가함

프로젝트 관리자는 의사소통의 복잡성을 나타내는 의사소통 채널수를 고려해야함

의사소통채널 수를 계산할 때 프로젝트관리자를 포함하여 채널 수 계산

V. CV, CPI, EAC 계산, 설명

- EV=95 백만원, PV=110 백만원, AC=100 백만원, BAC=950 백만원

- EV : Earned Value, PV : Planned Value, AC: Actual Cost, BAC: Budget At Completion, CV : Cost Variance, CPI: Cost Performance Index, EAC : Estimate At Completion

CP < 1 비효율적인 지출과 SPI <1 프로젝트 일정도 지연되고 있음

현재 상태로 프로젝트가 진행될 경우, 예산의 초과와 일정의 초과가 예상됨

제129회 예상문제(토픽)

정보관리 117회 4교시
4. 운영체제에서 페이지 교체 알고리즘을 사용한다.
가. 페이지 교체 알고리즘을 사용하는 이유에 대하여 설명하시오.
나. 페이지 교체 알고리즘의 종류를 나열하고, 각 종류별 동작 과정에 대하여 설명하시오.

문제4) 1) 페이지교체 알고리즘 사용 이유, 2) 페이지 교체 알고리즘 종류, 3) 각 종류별 동작과정

답)

I. 페이지 교체 알고리즘 사용 이유

페이징기법으로 메모리를 관리하는 운영체제에서 페이지 부재가 발생했을 경우 가상 기억장치의 필요한 페이지를 주기억장치의 어떤 페이지 프레임을 선택/교체하는지 결정하기 위해 사용

II. 페이지 교체 알고리즘의 종류

III. 오래된 페이지 교체 알고리즘 동작 과정

가 FIFO

각 페이지가 주기억 장치에 적재될 때마다 그 때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

(FIFO Page Fault: 6회 발생)

나. LRU

최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법으로 시간적인 오버헤드가 발생함

LRU Page Fault: 5회 발생

IV. 최소 호출 예정 페이지 교체 알고리즘

가. LFU

사용빈도가 가장 적은 페이지를 교체하는 기법

LFU Page Fault: 5회 발생

나. OPT

페이지 부재횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

OPT Page Fault: 4회 발생

-OPT 알고리즘이 페이지 부재횟수가 가정 적게 발생, 현실에서는 앞으로 사용되지 않을 페이지를 알 수없으므로 비현실적

제129회 예상문제(토픽)

정보관리 117회 3교시
3. MST(Minimum Spanning Tree)를 구하는 알고리즘인 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘을 설명하시오

문3) MST(Minimum Spanning Tree) 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘

답)

I. MST(Minimum Spanning Tree) 개요

- 각 간선에 가중치(비용, 거리, 시간, 교통량 등)가 있는 무방향 그래프 G에서 모든 정점들을 연결하는 가중치의 합이 최소가 되는 신장 트리

- 특징: 모든 정점 연결, 가중치 최소, 간선의 개수 n-1개, cycle 제거

II. 크루스칼(Kruskal) 알고리즘 

가. 크루스칼 알고리즘 개념 

-사이클 생성여부는 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사(union-fid 알고리즘 활용)

나. 크루스칼 알고리즘 절차

순서	도식	상세설명
1		- 초기상태 - 간선의 가중치 오름차순으로 정렬 수행
2		AD 와 CE 가 가장 짧은(가중치가 가장 작은) 간선 임의로 AD 선택
3		CE 가 가중치가 5 로서, Cycle 을 생성하지 않는 가장 짧은 간선이므로 CE 선택
4		가중치 6 인 DF 선택
5		다음으로 가장 짧은 간선은 AB 와 BE 인데 임의로 AB 선택 - BD 선택시 ABD 를 연결시키면 Cycle 이 형성되기 때문에 제외
6		- 가중치 7 인 BE 선택 - Cycle 을 형성하는 BC,EF,DE 제외
6		- EG 선택하면 모든 노드들이 연결되므로 알고리즘 수행 종료

- 간선의 개수를 E, 정점의 개수를 V 라고 할때 O(ElogV)의 시간복잡도를 가짐

II. 프림(Prim) 알고리즘

가. 프림알고리즘 개념 

- 정점을 기준으로 간선을 선택 후 하나의 집합으로 보고 인접한 정점중 최소 간선을 선택

나. 프림 알고리즘절차

순서	도식	상세설명
1		초기상태  정점 D를 시작점으로 선택
2		- D 와 연결되어 있는 정점을 선택 - A, B, E, F 중 가중치가 가장 작은 A 선택
3		정점 D 또는 A 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B,E, F 중 가중치가 가장 작은 F 선택
4		정점 D, A, F 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B 선택
5		정점 D, A, F, B 와 연결되어 있는 간선 중 가중치가 가장 작은 것 E 선택
6		정점 D, A, F, B, E 와 연결되어 있는 간선 중 가중치가 가장 작은 것 C 선택
7		정점 G는 E, F와 연결가능하나 가중치가 작은 정점 E와 연결하면 모든 정점이 연결되어 알고리즘 수행 종료

간선의 개수를 E, 정점의 개수를 V라고 할 때, 이진힙 사용시 O(ElogV)의 시간복잡도를 가지며, 피보나치힙 사용시 O(E+VlogV)의 시간 복잡도를 가짐

IV. 크루스칼 알고리즘과 프림 알고리즘 비교

- MST 는 정보통신, 건설분야 등에서 배선의 최소길이, 최단 통신선로, 가장 짧은 도로구간, 최단 배관길이 구성 등에 사용됨

5. 데이터베이스의 병행제어(Concurrency Control)에 대하여 다음을 설명하시오.

가. 병행제어의 정의

나. 병행제어 기법의 종류

다. 병행제어의 문제점

1. 병행제어의 정의

 1) 병행제어의 정의

   - 트랜잭션이 동시에 수행될 때, 일관성을 해치지 않도록 병행 트랜잭션 간의 상호작용을 제어하는 DBMS의 기능

 2) 병행제어 미처리시 문제점

구분	현상	설명
갱신 손실 (Lost Update)		- 트랜잭션들이 동일 데이터를 동시에 갱신할 경우 발생
현황파악오류 (Dirty Read)		-ㅠ트랜잭션의 중간 수행결과를 다른 트랜잭션이 참조함으로써 발생하는 오류
모순성 (Inconsistency)		- 두 트랜잭션이 동시에 실행할 때 DB가 일관성이 없는 상태로 남는 문제
연쇄복귀 (Cascading Rollback)		- 복수의 트랜잭션이 데이터 공유시 특정 트랜잭션이 처리를 취소할 경우 다른 트랜잭션이 처리한 부분에 대해 취소 불가능

 - 경신손실, 현황파악오류, 모순, 연쇄복귀 발생으로 병행제어 필요

2. 병행제어 기법의 종류

 1) 병행제어 기법 종류

 2) 병행제어 기법 설명

기법	개념도	작동방식
Locking 기법		-트랜잭션이 사용하는 자원에 대하여 상호 배제 기능을 제공하는 기법 -공유 lock : 다른 트랜잭션도 읽기 실행 가능 -전용 lock : 다른 트랜잭션은 읽기, 기록 모두 불가
2PL (2 Phase Locking)		-확장단계 : 트랜잭션은 오직 lock만 수행 가능 -수축단계 : 트랜잭션은 오직 unlock만 수행 가능
Timestamp Ordering		-시스템 시계 : 시스템 시간을 타임스탬프 값으로 부여 -논리적 계수기 : 트랜잭션 발생시마다 카운터를 하나씩 증가시켜 타임스탬프로 부여
낙관적 검증기법		-트랜잭션 수행 동안 트랜잭션을 위해 유지되는 데이터 항목들의 지역 사본에 대해서만 갱신이 이루어짐 -트랜잭션 종료 시 동시성을 위한 트랜잭션 직렬화가 검증되면 일시에 DB에 반영함
다중버전 동시성 제어 (MVCC)		트랜잭션이 한 데이터에 접근하려 할 때, 그 트랜잭션의 타임스탬프와 접근하려는 데이터의 여러 버전의 타임스탬프를 비교하여, 현재 실행하고 있는 스케줄의 직렬 가능성이 보장되는 버전을 선택하여 접근하도록 하는 기법

3. 병행제어의 문제점

 1) 병행제어의 분류

   - 락킹과 해제 과정, 타임스탬프 부여에 따라 데드락, 롤백, 자원낭비등의 문제가 발생

 2) 병행제어 문제점

 - 문제점에 따라 선택적인 기법 적용

4. 병행제어시 발생 문제 해결

- 타임스탬프 적용시 wait-die, wound-wait 적용

문제

4.최근 정보통신의 발전으로 인해 도감청이 불가능한 양자암호통신에 대한 관심이 높아지고 있다. 양자암호통신에 대하여 다음을 설명하시오.

    가. 양자암호통신의 암호키 분배방식

    나. 양자암호통신의 주요 기술

    다. 양자암호통신의 취약점

출처 : https://itpewiki.tistory.com/234 

1. 완벽한 해킹 차단을 위한, 양자암호통신의 개념 

     1) 양자암호통신의 개념

- 양자원리를 이용하여 비밀키를 생성하고 이 비밀키로 Message를 암호화한후 Message는 일반채널로 , 비밀키는 양자채널로 전송하는 기술

     2) 양자원리 3가지

2. 양자암호통신의 암호키 분배방식 및 주요 기술

      1) 양자암호통신의 암호키 분배방식

      2) 양자암호통신의 주요 기술

3. 양자암호통신의 취약점

       1) 일반암호통신과 공통의 취약점

        2) 양자암호통신의 취약점