알고리즘의 정의

1. 알고리즘이란  

일반적으로 알고리즘은 튜링머신과 동치이다. 튜링머신은 함수이므로 알고리즘을 함수라고 생각해도 무방하다. 그리고 처치 튜링명제에 의하면 튜링머신과 람다대수, 자바 프로그램 그리고 기타 계산 모델의 표현력은 동일하므로, 자바 프로그램이나 튜링머신으로 표현되는것은 수학적으로 알고리즘 이다. 일반적인 의미에서 알고리즘은 문제를 해결하는 방법 정도라고 하면 되겠습니다.

2. 계산이론 : 계산 복잡도 vs 계산 가능성

계산이론에는 계산 복잡도 이론과 계산 가능성이론이 있다. 전자는 빅오표기법, np문제 와 같은 주제를 다루고, 후자는 촘스키 계층, 오토마타, 정규표현식과 같은 주제를 다룹니다. 계산 이론은 힐베르트의 21가지 문제중 알고리즘과 관련된 문제가 있었는데, 이를 연구하며 생긴 학문이다.

3. 알고리즘의 요건과 평가

알고리즘은 입력/출력(io), 명확성, 유한성, 효율성을 갖춰야 한다.

알고리즘은 시간복잡도(TC), 공간복잡도을 이용해 평가할 수 있다. 컴공에서도 trade-off 라는 많이 쓰는데, 저장공간을 아끼면 처리 시간이 길어지고/ 시간 효율성에 비중을 두면 저장공간이 낭비된다. 간단히 제로섬이라 생각하면 편하다. 일반적으로는 저장공간 보다는 시간 효율성을 추구하는 편이 좋다고 보면되고, tc를 평가할때 데이터의 이동이 데이터의 연산보다 오래걸리는 것도 고려하면 좋다.