- 활동 일시
일시 : 2022.12.04 (일) 13:00 ~ 15:00 (총 2시간)
- 오늘의 계획
- 알고리즘
- Adversary argument
- reduction
- 오늘의 활동
- Lower bound가 T이다 <-> 해당 문제를 T 시간보다 빨리 해결할 수 없다.-
Adversary argument (방해꾼 논법) : Lower bound를 증명할 수 있는 방법
- 방해꾼 논법은 스무고개 게임과 매우 비슷하다.- Solver와 Adversary 간의 일종의 game.
- Adversary 는 input 을 가지고 있고, solver 는 input 이 뭔지 확인할 수는 없지만 adversary 에게 질문을 할 수 있다.
- Adversary 는 solver 의 질문에 대해 대답을 해야하며 solver 가 최대한 늦게 문제를 해결하도록 input을 계속 바꿀 수 있음.
- 단, input 을 바꿀 때 일관성을 유지해야 한다.
(내가 대답한 내용은 언제나 참이어야 함.) - Algorithm 의 lower bound = solver 에게 필요한 최소한의 질문횟수
- Find_Max 문제, Find_MIN_MAX 문제 등에 사용 가능함.
-
Reduction
어떤 문제 X와 Y가 있다고 할 때 Y를 해결하는 algorithm 이 존재하고, 이 algorithm 을 이용하여 X를 해결하는 algorithm 을 디자인 할 수 있는 경우 X에서 Y로 reduction이 가능하다고 한다.
1) 특정문제를 해결하는 algorithm 을 디자인.
2) 어떤 문제를 해결하는 algorithm 이 존재하지 않는 것 (혹은 매우 해결하기 힘든 것) 을 증명.- ex) X : kth selecting / Y : sorting
- sorting문제를 해결하면 k번째 element를 select 가능
-> X에서 Y로 reduction이 가능하다.
- reduction이 존재하는지를 확인하려면 다음을 확인해야한다.
- 임의의 X 의 instance Ix -> Y의 instance Iy 로 변환 가능
- (x에 대한 답 == y에 대한 답) 을 만족
- 만약 X에서 Y로의 reduction이 존재하지 않지만, X를 해결하는 algorithm이 존재한다면, Y를 해결하는 것은 적어도 X를 해결하는 것 만큼 어렵다.
- 반대로 X에서 Y로의 reduction이 존재한다면, X를 해결하는 것은 Y를 해결하는 것보다 절대로 어려울 수 없다.
- ex) X : kth selecting / Y : sorting
- 활동 소감
이번학기 학습동아리 활동을 하면서 처음으로 비대면으로 해보았다. 각자 캠을 키고 서로 어떤것을 공부하는지 화면 공유도 하면서 같이 공부했다. 비대면으로 학교생활한지도 오래됐고, 많은 활동을 비대면으로 해봐서 그런지 하나도 안어색했고, 오히려 집에서도 공부가 잘 되었던 것 같다.
