계산 가능성

컴퓨터 과학의 핵심 개념

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

계산 가능성이란?

계산 가능 문제

• 알고리즘 존재: 명확한 절차가 존재함.
• 유한 시간: 제한된 단계 내에 결과를 산출함.

비계산 가능 문제

• 알고리즘 부재: 모든 입력에 대해 해결할 수 없음.
• 무한 계산: 결론에 도달하지 못할 수 있음.

¹ 알고리즘을 찾거나 알려진 알고리즘이 유한 시간 내에 끝나게 만들면, 비계산 가능 문제가 계산 가능 문제가 될 수 있습니다.

오토마톤

오토마톤의 정의

• 가상의 기계
• 계산 작동 원리 이해에 도움
• 상태를 가짐
• 상태 전이 규칙을 가짐

유한 오토마톤(FA)

유한 오토마톤(FA)

• 단순한 _기계_
• 고정된 상태 수
• 현재 상태 외 메모리 없음

푸시다운 오토마톤(PDA)

푸시다운 오토마톤(PDA)

• 더 강력함
• 상태를 가짐
• 더 복잡한 결정을 위한 스택 기반 메모리 보유

요약

유한 오토마톤(FA)

• 단순 작업에 유용

푸시다운 오토마톤(PDA)

• 더 복잡한 문제에 더 강력

중요성

• 문제가 오토마톤으로 모델링되면, 해결 알고리즘을 구현할 수 있음

연습해 봅시다!

컴퓨터 과학의 핵심 개념