[고려대학교][하이퍼텍스트와계산가능성][21-1][A+]기말고사 문제 + 답안

소개글

"[고려대학교][하이퍼텍스트와계산가능성][21-1][A+]기말고사 문제 + 답안"에 대한 내용입니다.

목차

없음

본문내용

문제 1. 30점
함수 f의 정의역 {0,1,2,3}, 공역 {0,1} 이고 f(0)=1, f(1)=f(2)=f(3)=0일 때 그로버 알고리즘이 어떻게 작동하여 0을 찾는지 서술 하시오

문제 2. 15점
NP의 시각으로 A와 B의 구조적 공통점을 서술하시오
A : 충족불가능성 문제
입력 : 임의의 논리식 h
출력 : h가 충족불가능하면 Yes, 가능하면 No

B : Graph nonisomorphism 문제
입력 : 무향그래프 x, y
출력 : x와 y가 isomorphic하지 않으면 Yes, 하면 no

문제 3. 5점
P=NP가 참인지 거짓인지 판별 후 이유 3개 이상 서술

참고 자료

없음