집밖은 위험해

회귀 분석 regressioni analysis

- 변수들 간의 함수적인 관련성을 규명하기 위해 수학적 모형(통계 모형)을 가정하고, 관측된 자료로 이 모형을 추정하는 통계 분석 방법으로 주로 예측에 사용

- 주어진 데이터를 가장 잘 나타낼수 있는 수식을 찾아내는 방법

데이터 예시

회귀식 예시

- 위 데이터를 가장 잘 나타낼수 있는 다항식을 구함 -> 회귀 분석

- 1차 : y = ax + b

- 2차 : y = ax^2 + b x + c

- 3차 : y = ax^3 + b x^2 + c x + d

NP-hard

- Non-deterministic Polynomial-time hard

- 결정 문제의 분류로 모든 경우의 수를 확인해보는것 이외에는 답을 찾을수 업슨ㄴ 문제

NP-complete

- NP 중에서 가장 어려운 문제

NP-complete 해결을 위한 접근 방법

- 근사 approximation : 적절한 범위 내 차선의 suboptimal 해결책을 빠르게 찾는 알고리즘. 모든 np-complete 문제가 좋은 근사 알고리즘을 가진것이 아니며, 발견하더라도 문제 자체를 해결하기엔 충분치 않음

- 확률 probabilistic : 문제의 인스턴스에 대한 확률분포에 대해 좋은 평균 런타임 동작을 낳는다고 입증된 알고리즘

- 휴리스틱 : 많은 경우 잘 동작하지만, 항상 빠르다는 증명은 없는 알고리즘

- 스페셜 케이스 : 문제의 인스턴스가 특별한 경우라면 빠르다는 것이 입증된 알고리즘

새로운 문제의 NP-complete 증명 방법

- 이미 알려진 NP-complete 문제를 새로운 문제로 환원 reduce

NP-complete 문제 종류

- Boolean statisfiability problem SAT

- Fifteen puzzle

- 배낭 문제

- minesweeper

- tetris

- 해밀턴 사이클 문제

- 순회 판매원 문제

- subgraph isomorphism problem

계산 복잡도 이론

- 주어진 문제를 풀기 위해 계산 과정에 필요한 자원을 다루는 계산 이론의 일부

자원의 종류

- 시간 : 문제를 풀기 위해 얼마나 많은 단계를 거치는가

- 공간 : 문제를 풀기 위해 얼마나 많은 메모리가 필요한가

- 이외 : 얼마나 많은 병렬 프로세서가 필요한가 등

하나의 문제

- 관련 질문들의 전체 집합. 질문은 유한 길이의 문자열

계산 이론의 인스턴스

- 인스턴스 : 어느 특별한 질문

인스턴스의 예시

- "15의 인수를 해라"

시간 복잡도 time complexity

- 가장 효율적인(bit로 측정) 알고리즘으로 한 문제의 인스턴스를 푸는데 걸리는 단계 수

시간 복잡도의 예시

- n 비트 길이의 인스턴스가 n^2 단계 내에 풀린다면 n^2의 시간복잡도를 가짐

 -> 빅오 표기법 : 최악의 경우 시간 복잡도 -> O(n^2)

- 잡초 깍기는 두배의 면적을 깍는데 두배의 시간이 걸린다 -> 선형 복잡도

- 사전에 어떤것을 찾을때 두배 크기의 사전을 한번더 열어봐야한다. -> 지수 복잡도

P 문제와 NP 문제

- P 문제 (polynomial, 다항식) : 알고리즘의 속도가 다항식으로 표현되는 문제

- NP 문제 (nondeterministic polynomial, 비결정 다항식) : 다항식으로 표현될수 있는지 알려지지 않은 문제

=> P 문제는 컴퓨터로 적당한 시간내 해결가능한 쉬운 문제, NP는 어려운 문제

NP hard와 NP 완전 문제(NP complete)

- NP-hard : 모든 경우의 수를 확인해보는 방법 이외에는 정확한 답을 구할수 있는 방법이 없는 문제

- NP-complete : NP-hard 이면서 다항식 시간으로 표현될수 있는지 알려지지않은 문제

튜링 머신 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라고도 함

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