(방송통신대 이산수학 기말시험)1. 2019학년도 이산수학의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 교재 제10장의 연구과제 14번 15번 RSA 암호화와 복호화 과정에 대해

소개글

과제물의 문제에 적합한 형식과 내용으로 정성을 다해 작성했습니다.
여러 참고자료를 바탕으로 주요내용을 최대한 이해하기 쉽고 알차게 정리했습니다.
리포트를 효율적으로 작성하시는 데 작은 도움이라도 되시기를 진심으로 바랍니다.^^

문단 모양(왼쪽 여백 0, 오른쪽 여백 0, 줄간격 160%)
글자 모양(바탕체, 장평 100%, 크기 11 pt, 자간 0%)

<과제 작성 시 지시사항>
(1) 본 시험의 평가 기준은 수학적 사고 능력과 합리적인 논리 전개 능력입니다. 따라서 반드시 풀이 과정을 함께 작성하셔야 합니다.
(2) 답안은 반드시 펜으로 종이에 작성하되, 매 쪽마다 학번과 이름을 상단 우측에 적으십시오.
(3) 작성된 답안은 스캔하여 반드시 5MB 이하의 pdf형식 화일 1개로 만들어 제출하십시오. (예상하는 적정한 답안의 분량은 A4로 6매 정도임).

행복하세요, Now!

목차

1. 2019학년도 『이산수학』의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 풀이를 해설하시오. 단, 문제에서 다루는 주요 용어에 대해 설명하고, 정답은 왜 정답인지, 오답은 왜 오답인지를 상세히 설명할 것. (참고: 이산수학 워크북의 해설) [30점]
1)55번 문제 2)56번 문제 3)57번 문제 4)58번 문제 5)59번 문제 6)60번 문제

2. 교재 제10장의 연구과제 14번(교재 p.268)을 푸시오. [10점]

3. 교재 제12장의 연구과제 15번(교재 p.325)을 푸시오. [10점]

4. RSA 암호화와 복호화 과정에 대해 다음 순서에 따라 설명하시오. [20점]
(1) 암호화를 위한 공개키를 임의로 정하고 왜 적합한지 밝히시오.
(2) 학생의 영문 성과 학번의 끝 3자리를 암호문으로 만드는 과정을 설명하시오. (예를 들어 학생 홍길동의 학번이 ******-***123이면 HONG123이 평서문임. 필요한 경우 space를 26번으로 정함).
(3) 복호화를 위한 비밀키를 임의로 정하고 왜 적합한지 밝히시오.
(4) 단계(2)번에서 구한 암호문을 평서문으로 복호화하는 과정을 설명하시오.

본문내용

1. 2019학년도 『이산수학』의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 풀이를 해설하시오. 단, 문제에서 다루는 주요 용어에 대해 설명하고, 정답은 왜 정답인지, 오답은 왜 오답인지를 상세히 설명할 것. (참고: 이산수학 워크북의 해설) [30점]

1)55번 문제
다음 그래프 G와 관련된 서술 중 옳은 것은?

①G는 방향 그래프이다. ②G는 이분 그래프이다.
③G는 완전 그래프이다. ④G의 차수는 3이다.

설명
①그래프 G의 edge에 방향을 의미하는 화살표가 없으므로 방향 그래프가 아니다.
②그래프 G의 꼭지점 a, b, c를 두 개의 집합으로 분리했을 때 적어도 어느 한 집합 내부에는 edge가 존재하므로 이분 그래프가 아니다.
③그래프 G의 각 꼭지점에서의 차수(각 꼭지점에서 붙어 있는 선들의 수)는 모두 2이다.
④그래프 G에서 3개의 꼭지점 사이에 edge가 있으므로 그래프 G는 완전 그래프 K3이다.

2)56번 문제
다음 그래프 G에 관한 설명으로 부적절한 것은?

①G는 완전 그래프로서 K4 이다.
②G는 3-정규 그래프로서 큐빅 그래프라고 부른다.
③G에는 오일러 투어가 존재한다.
④G에는 해밀턴 사이클이 존재한다.

설명
①각 꼭지점은 자신을 제외한 나머지 점들과 모두 인접하여 edge를 가지므로 G는 완전 그래프로서 K4 이다.
②그래프 G 내에 있는 모든 꼭지점의 차수가 3이므로 3-정규 그래프가 된다.
③오일러 순환(회로)이 존재하는 그래프, 즉 오일러 그래프 존재의 필요충분조건은 그래프 G의 모든 꼭지점의 차수가 짝수이다. 그런데 문제의 그래프 G의 모든 꼭지점의 차수는 3으로 홀수다. 따라서 그래프 G에는 오일러 순환이 존재하지 않는다.
④그래프 G에서 하나의 꼭지점에서 시작해 나머지 모든 꼭지점을 꼭 한 번씩만 지나 다시 돌아오는 경로 즉, 해밀턴 순환의 예로 a-b-c-d-a의 경로를 들 수 있다.

참고 자료

손진곤(2021). 이산수학. 한국방송통신대학교출판문화원.
Kenneth H. Rosen(2019). 이산수학 8판. McGraw-Hill Education.
박주미(2017). 컴퓨팅 사고력을 키우는 이산수학 . 한빛아카데미.