[컴퓨터과학과] 2020년 1학기 알고리즘 기말시험 과제물(해설X)

소개글

@@@@ 순서대로 장과 절 구분 후, 1~100까지 번호를 부여했습니다.
과제물 작성 시, 참고용 자료이며 "해설"은 쓰지 않았습니다.
해설 작성 외에 모든 조건을 충족한 자료입니다.
본 자료를 수정하지 않고 그대로 제출하는 경우에 발생하는 모든 책임은 본인에게 있습니다.
꼭 참고하고 다운로드 부탁 드립니다 @@@

『알고리즘』 교과목의 2018학년도~2019학년도 기출문제(출석수업대체시험 및 기말시험 총4종의 100문제)를 다음 조건이 만족되도록 정리해서 제출하시오.
[조건]
① 각 문제는 교재 목차의 장과 절에 따라 분류해서 정리한다. 단, 문제의 내용/보기가 여러 장/절에 걸쳐 있는 경우에는 정답이 속한 장/절에서 정리한다. 각 문제의 원래 번호는 생략하는 대신에 모든 문제는 순서에 따라 1부터 100까지 차례대로 번호를 부여한다. 또한 각 문제의 뒷 부분에는 출제년도와 시험 종류(대체,기말)를 표시한다.
각 문제에 대한 적절한 해설과 풀이 과정을 반드시 제공해야 한다. 즉, 다른 학생이 해설과 풀이 과정을 통해서 해당 문제를 이해하고 해결할 수 있을 정도로 관련 내용을 상세하면서도 명확하고 깔끔하게 정리해야 한다.(문제의 보기 내용을 단순히 풀어쓰는 형태의 설명은 인정하지 않는다.)
②해당 문제와 관련된 내용을 참조할 수 있도록 교재의 쪽수 또는 강의 자료의 페이지 번호를 반드시 언급해야 한다.
③모든 문제는 워드프로세서를 이용하여 직접 입력한다. 단, 그림의 경우에는 기출문제의 그림을 캡쳐해서 사용할 수 있다.
④각 문제당 위의 조건을 반드시 충족해야 하며, 과제 작성 시 지시사항과 과목 질의응답 게시판의 기타 지시사항을 반드시 만족해야 한다.

목차

없음

본문내용

# 1장. 알고리즘 소개
1.다음 중 교재 및 강의에서 다루어지지 않은 부류의 알고리즘은? (2018기말)(1강-7쪽)
① 기하 알고리즘
② 정렬 알고리즘
③ 유전 알고리즘
④ 욕심쟁이 알고리즘
해설)

[1-1] 알고리즘의 개념
2.주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은? (2018기말) (1강-16쪽)
① 모든 명령은 컴퓨터에서 수행 가능해야 한다.
② 각 명령은 단순하고 명확해야 한다.
③ 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다.
④ 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다.
해설)

3. 다음 그래프에 대해서 오일러 경로를 찾으려고 한다. 이때 출발점이 되어야 하는 정점은? (2018출석) (1강-14쪽)
① (a) ② (b) ③ (c) ④ (d)
해설)

<중 략>

# 7장 근사 알고리즘
[7-3] NP-완전 문제
96. 다음 중 NP-완전 문제가 아닌 것은? (2018기말) (13강-12쪽)
① 무방향 그래프에서 모든 정점을 한 번씩만 지나가는 사이클의 존재 여부를 확인하는 문제
② 하나의 정점에서 다른 모든 정점으로의 가장 짧은 경로를 구하는 문제
③ 정규곱형으로 주어진 논리식을 참으로 만들 수 있는 지 판단하는 문제
④ n개의 양의 정수가 주어졌을 때, 각 집합에 포함된 수의 합이 동일하도록 n개의 정수를 두 개의 집합으로 나눌 수 있는지 판정하는 문제
해설)

97. 어떤 문제 A가 NP-완전 문제라는 설명으로 적합한 것은? (2018기말) (13강-12쪽)
① 클래스 NP의 모든 문제가 문제 A로 지수 시간 변환되며 A가 클래스 NP에 속하는 경우
② 클래스 NP의 모든 문제가 문제 A로 다항식 시간 변환되며 A가 클래스 NP에 속하는 경우
③ 클래스 NP의 모든 문제가 문제 A로 지수 시간 변환되는 경우
④ 클래스 NP의 모든 문제가 문제 A로 다항식 시간 변환되는 경우
해설)

참고 자료

방통대 알고리즘 교재