21년 방통대(방송통신대학교) 이산수학 기말

소개

21년 1학기 이산수학 기말 자료입니다.
답안 해설 테이블 내 오타가 있어서 수정한 버전으로 재업로드합니다.

목차

1. 기말시험 기출문제 풀이 (19년도 기말 55~60번 문제) - 정/오답 사유 기재
2. 교재 10장 연구과제 14번. (데이크스트라 알고리즘, 최단 경로 구하기) - 파이썬 코드 첨부, 코드는 자료 내 링크로 공유되어 있음
3. 교재 제12장 연구과제 15번. (피보나치 수열, 파스칼 삼각형, 일반항 증명)
4. RSA 암호화, 복호화

본문내용

1.2019년도 이산수학 기말시험 기출문제 풀이
55번 문제 정답: 3번
그래프 G의 모든 꼭짓점이 하나 이상의 간선으로 연결되어 있기 때문에 완전 그래프이다.
보기 1번: 방향 그래프는 모든 간선에 방향이 표시되어야 하므로 오답이다.
보기 2번: 이분 그래프는 그래프의 모든 정점을 두 개로 나눠 서로 다른 그룹의 점이 간선으로 연결되어야 한다. 만약 a가 빨간색이고 b가 파란색이라고 했을 때 c가 빨간색이면 a와 인접하게 되어 이분 그래프가 성립하지 않으며, c가 파란색이면 b와 인접하게 되어 이분 그래프가 성립하지 않게 된다.
보기 3번: 차수는 그래프에 한 정점에 연결된 간선의 수를 의미하는데 a의 차수는 2이며 마찬가지로, b/c의 차수 역시 2이므로 오답이다.

<중 략>

4. RSA 암호화와 복호화 과정에 대해 다음 순서에 따라 설명하시오.
(1) 암호화를 위한 공개키를 임의로 정하고 왜 적합한지 밝히시오.
공개키는 n, e 두 정수로 이루어져있다. n은 임의의 소수 p, q의 곱이고, e는 먼저 (p-1)와 (q-1)을 곱하여 Φ(n) 값을 구하고, 1<e<Φ(n) 이며 Φ(n)과 서로소인 e을 찾아준다. 예를 들어 두 개의 소수 17, 23을 선택한다고 했을 때 n = 17 * 23 = 391이다. Φ(n)은 (p-1)*(q-1) = 352 이다. 즉, e는 1보다 크고 352보다 작은 숫자이며 352와 서로소인 숫자를 찾으면 된다. 예로, 3이 있다. 즉, 공개키는 (391, 3)이다.

(2) 학생의 영문 성과 학번의 끝 3자리를 암호문으로 만드는 과정을 설명하시오. (예를 들어 학생 홍길동의 학번이 ******-***123이면 HONG123이 평서문임. 필요한 경우 space를 26번으로 정함).
암호화 C = Me mod n 을 이용해서 구한다. 식에서 M은 입력 받은 평서문을 의미한다. 평서문을 숫자로 치환하는 것은 문제에서 주어진 것처럼 테이블을 이용하면 된다.

참고자료

· 없음