집밖은 위험해

튜링 머신 turing machin

- 앨런 튜링이 소개한 실제 기계가 아닌 추상적 수학 개념의 오토 마타

- 임시 저장소가 테이프인 오토마타 

 -> 테이프는 셀로 나눠짐. 각 셀은 한개의 심볼을 저장

 -> 테이프와 관련하여 읽기 쓰기 헤드가 있음. 왼쪽/오른쪽으로 이동하여 하나의 심볼을 읽고 쓸수 있음

튜링 머신과 간단한 컴퓨터 비교

- 간단한 컴퓨터 : 유한 메모리를 갖는 프로세서 유닛을 가짐 -> 컴퓨터가 수행 가능한 명령어가 극히 제한됨

- 튜링 머신 : 테이프에 무한한 양의 보조 저장소를 가짐

튜링 머신의 기원

- 힐베르트의 열한번째 문제 : 모든 수학 문제를 풀 수 있는 알고리즘을 찾아라 -> 그런 알고리즘(기계가) 존재할수있는가?

- 기계적 프로그램의 정의

 -> 튜링은 기계 동작을 기본적인 식으로 나누어 정형화하여 기계라는 개념을 수식으로 표현하려고함

 -> 튜링은 사람의 뇌도 하나의 기계로 간주

 => 수학 문제를 푸는 수학자의 행동이 기계적 프로그램으로 묘사가능

튜링 기계와 형식 체계

- 튜링 기계는 알고리즘 or 프로그램이라 불러도 됨

- 우리 주위 모든 컴퓨터들은 튜링기계라 볼 수 있음

- 튜링 기계화 형식 체계는 다음음의 일대일 대응일 이룸

* 튜링 머신과 재귀 하수, 람다 계산법, 포스트 시스템 등 모두 같은 개념

계산 가능성 이론 computability theory

- 어떤 문제를 알고리즘(또는 튜링 머신)으로 해결할수 있는지 다룸

계산 가능성 이론의 주요 의문 4가지

- 어떤 문제를 튜링 머신이 해결할수 있는가?

- 어떤 다른 시스템이 튜링 머신과 동등한가?

- 어떤 문제들이 더 강력한 기계들을 필요로 하는가?

- 어떤 문제들이 덜 강력한 기계로 풀수 있는가?

여러 계산모델

1. 튜링 기계 turing machine

- read, write head가 스캐닝 하는데로 사각형 무한 길이의 테이프 상에 문자를 저장

2. 재귀 함수 recursive function 

- 수에 관한 연산을 위해 함수와 함수의 조합 사용 

3. 람다 계산법 lambda calculus

4. 마르코브 알고리즘 markov algorithm

5. 포스트 시스템 post systems

처치-튜링 명제 church-turing thesis

- 위 형식 모델 formalisms들은 계산 능력에서 동등한것으로 봄

- 한 모델에서 수행가능한 계산을 다른 모델로도 수행 가능

- 그 모델들은 컴퓨터가 무한 메모리를 가진다면 보통 컴퓨터에서 동등한 능력을 보임

=> 처치-튜링 명제 : 알고리즘 개념이 적절히 형식화되면 모든 알고리즘은 튜링 머신에서 수행될수 있음

=> 계산 가능성 이론 : 어떤것이 기계로 계산될수 있는지 다룸

계산 이론의 연구

- 일반적인 계산 모델과 컴퓨팅 한계 연구

-> 어떤 문제가 컴퓨터로 해결 불가능한가? 

-> 컴퓨터로 해결 가능하지만 해법이 비현실적이여서 오랜 시간이 필요한가?

-> 주어진 해법을 확인하는 것 보다 문제 해결이 더어려울 수 있는가?(P와 NP)

계산 이론 theory of computation

- 컴퓨터 과학의 한 분야

- 어떤 문제를 컴퓨터로 풀수있는지 -> 계산 가능성 이론 computability theory

- 얼마나 효율적으로 풀수있는지 탐구 -> 계산 복잡도 이론 computational complexity theory

=> 계산 이론은 계산 가능성 이론과 계산 복잡도 이론 2분야로 나뉨

계산 computation

- 주어진 입력으로부터 문제의 해법을 찾는 것

- 수학자들이 수학 문제를 간단한 방법 simple method로 해결가능한지 알려고함

=> 계산의 형식 모델 formal model of computation 이 요구됨

이산수학의 응용 분야

- 게임 이론 game theory

- 큐 이론 queing thery

- 그래프 이론 graph theory

- 조합 기하학 combinatorial geomtry과 조합 위상학 combinatorial topology

- 선형 프로그래밍 linear programming

- 계산 이론 theory of computation

이산수학이 다루는 주제

- 논리 : 추론 ressoning, inference에 관한 연구

- 집합 이론 : 요소 모음 연구

- 수 이론 number theory

- 조합 combinatorics : 계산 computation에 관한 연구

- 그래프 이론 graph theory

- 알고리즘 : 계산 방법 연구

- 정보 이론 information theory

- 계산가능성 이론 computability theory와 계산복잡도 이론 computational complexity theory : 알고리즘의 이론적 한계에 대한 연구

- 확률 이론 probability theory와 마르코브 연쇄 markov chains

- 선형 대수 linear algebra

이산수학 discrete mathematics

- 이산적인 수학 구조에 대한 학문

- 연속성이 필요하지않는다는 의미로 유한 수학 finite mathematics라고도 함

- 유한 수학에서 연구 대상은 셀수 있는 수의 집합

1. 방정식의 근 찾기

f(x) = 0일때 x

2. 선형 대수 방정식

아래의 a, c가 주어질때 x에 대해서 풀기

3. 최적화 문제

최적의 f(x)를 구하는 x 찾기

4. 커브 피팅 curve fitting

5. 적분

함수 f(x)가 주어질때 아래의 넓이를 구하기

6. 상미분방정식 ordinary differential equation 풀기 

아래의 상미분 방정식이 주어질때 t에 대한 함수로 y를 구하기

7. 편미분 방정식 partial differential equation 풀기

- 다음의 편미분 방정식이 주어질때 x, y에 대한 함수로 u를 구하기

수치 해석

- 자연 과학, 공학, 의학, 사회과학 등에서 발생하는 문제들 중에서 수학적인 문제로 표현할 수 있는 문제들을 컴퓨터로 해결하고자 하는 수학의 응용분야

수치 해석에서 문제 해결 과정

1. 수학적 모형화

- 해결할 문제를 역학, 생물학 등의 기본 가설이나 법칙들로 상 및 편미분 방정식, 대수방정식 등의 수학적 문제로 변형

2. 수학적 분석

- 수학적 모형화와 과정을 거쳐 생성된 수학적 문제를 미분방정식, 함수해석학, 기하학 및 대수학 등 가능한 수학 이론들을 적용하여 해의 유일성, 존재성, 정착성 등 분석

3. 수치적 분석

- 좁은 의미의 수치해석

- 앞의 수학적 분석 단계에서 다루어진 문제의 해가 존재하면, 이 해를 어떻게 컴퓨터로 구할지 수치적 알고리즘을 개발

- 이 알고리즘을 적용하여 구한 해의 수렴성 판정 및 오차 분석 등을 수행

4. 수치 실험

- 실제로 가장 효율적인 수치 알고리즘을 프로그램으로 만들어 문제를 해결

문제의 해를 구하는 방법

- 직접 방법 direct method : 알고리즘을 사용하여 해를 구함

- 이산화 discretization : 연속 문제를 이산 문제로 바꾸어 시도하는 것

- 반복법 iteration method : 하나의 추측 guess에서 시작하여 해에 수렴하는 성공적인 근사치 approximation를 찾음

* 직접 방법이 존재하더라도 반복법이 더 효율적이라 선호되는 경우가 있음.