컴퓨팅의 한계와 인공지능의 발전

## 컴퓨팅의 한계 - 하드웨어 - 산술 계산에서의 한계 e.g. 무리수, 파이, 분수 등을 컴퓨터에 저장하기, 부동소수점 오차 - 소프트웨어 - 소프트웨어는 에러가 발생하기 마련 - 컴퓨터로 풀 수 없는 문제, 풀 수 있지만 시간 상 풀기 어려운 문제 등이 존재함 #### Big-O 분석 ✨ - 알고리즘을 비교할 때는 주로 알고리즘 실행에 걸린 시간을 기준으로 효율성을 계산함 - 알고리즘의 기본이 되는 연산이 몇번 수행되었는지 횟수 세기 - Big-O 분석은 실행 횟수의 최고 차항만 고려해서 표현하는 수학적 표기법임 - 자주 사용되는 계산 차수(Orders of Magnitude) - **다항 시간(polynomial-time algorithm)** - O(1): 상수 시간 복잡도 - O(log2N): 로그 시간 복잡도, 처리할 데이터를 매 단계마다 절반으로 잘라내는 알고리즘들이 보통 여기에 속함 - O(N): 선형 시간 복잡도, 선형 알고리즘 - O(Nlog2N): 선형 로그 시간 복잡도, 보통 로그 알고리즘을 N의 배수만큼 적용하는 경우 - O(N^2): 제곱 시간 복잡도, 보통 선형 알고리즘을 N의 배수만큼 적용하는 경우 - **지수 시간(exponential-time algorithm)** - O(2^N): 지수 시간 복잡도, N의 크기에 따라 극적으로 증가함 - O(N!): 팩토리얼, 더 노답 ![[Orders_of_Magnitude 1.png|center|500]] #### Halting Problem(정지 문제) - 어떤 프로그램이 특정한 입력 값에 대해 결국은 정지할 것인지 판단한는 문제로서 **풀 수 없는 문제** - 어느 문제가 풀 수 없는 문제인지 혹은 이 문제에 대해 아직 해를 발견하지 못했을 뿐인지를 어떻게 증명합니까,,\ ###### P-NP Problem 1. **P (Polynomial Time):** - P는 다항 시간(polynomial time) 내에 **해결할 수 있는** 문제들의 집합 - 다항 시간 내에 해결할 수 있다는 것은 문제의 해결에 필요한 시간이 입력 크기에 대한 다항식으로 표현될 수 있다는 것을 의미함 2. **NP (Nondeterministic Polynomial Time):** - NP는 다항 시간 내에 **검증이 가능한** 문제들의 집합 - 만약 어떤 문제의 답이 주어진다면, 이 답을 다항 시간 내에 검증할 수 있는 알고리즘이 존재함 3. **P-NP 문제:** - P-NP 문제는 P와 NP 사이의 관계에 대한 미해결 문제로, 현재로서는 P와 NP가 동일한 집합인지 여부를 알 수 없는 문제 - P에 속하는 문제는 다항 시간 내에 효율적으로 풀 수 있지만, NP에 속하는 문제는 다항 시간 내에 검증은 가능하지만 풀기는 어렵다는 것을 의미함 - P와 NP가 같다면, P-NP 문제는 P에 속하는 모든 문제가 NP에 속한다는 것을 의미하며, 어떤 문제든 효율적으로 풀 수 있다는 것을 의미함 - 그러나 P와 NP가 같지 않다면, 일부 NP-난해(NP-hard) 문제는 P에 속하는 어떤 문제보다도 더 어려워 효율적인 해법이 없다는 것을 의미함 4. **NP-hard 및 NP-complete:** - NP-hard 문제는 NP에 속하지만, 어떤 문제든지 이 문제를 다항 시간 내에 환원할 수 있다는 보장이 없음 - NP-complete 문제는 NP에 속하면서, NP에 속하는 모든 문제를 다항 시간 내에 환원할 수 있는 문제 - NP-complete 문제 중 하나를 다항 시간 내에 풀면, 모든 NP에 속하는 문제를 다항 시간 내에 풀 수 있게 된다 ![[P-NP 1.jpg|center|600]] ## 인공지능 - Biological Neural Networks(생물학적 신경망) - 몇몇 인공지능 연구자들은 인간의 뇌가 어떻게 동작하는지에 집중함. 그리고 컴퓨팅 디바이스를 이와 비슷하게 설계하고자 했음 - 인공신경망은 뇌의 neural network를 복제하려고 시도한거임 - **Artificial Neural Networks(인공신경망)** - 인공신경망의 처리과정의 모든 요소는 생물학적 뉴런과 유사함 - 1개 이상의 input을 받아들이고 0 또는 1의 단일 output을 생성함 - input들은 네트워크 내의 다른 요소들의 output이므로, 0 아니면 1임 - 각 입력 값에는 가중치가 따라 붙고, 유효 가중치는 입력 값과 그것의 가중치를 각각 곱한 값의 합으로 정의됨 ![[Artificial_Neural_Networks 1.png|center|400]] #### 다양한 인공신경망 관련 용어 - 퍼셉트론(Perceptron) - 뉴런의 동작 방식을 모방하여 만든 수학적 모델 - 활성 함수(Activation Function) - 입력신호의 총합을 바탕으로 출력값을 0 또는 1로 결정하는 함수 - 다층 퍼셉트론(MLP, Multi-Layer Perceptron) - 입력층 + 은닉층 + 출력층으로 구성 - 순전파(Feed Forward) - 정보의 흐름이 입력층에서 출력층까지 순방향으로만 진행 - **역전파(Back-propagation)** - 출력값과 실제값의 오차(error)를 역으로 전달하여 학습하는 방법 - 피드백을 다시 학습함 → machine learning의 시작 - 강화 학습(Reinforcement Learning) - 행동에 대한 보상을 줌으로써, 보상을 극대화하기 위해 동적으로 학습을 하며 행동을 조정함 - 딥러닝(Deep Learning) - DNN(Deep Neural Network)을 이용한 강화 학습 방법 - DNN = MLP + Back-propagation ###### 퍼셉트론으로 AND 논리회로 만들기 ![[AND_operation_with_perceptron 1.png]] ###### 퍼셉트론으로 OR 논리회로 만들기 ![[OR_operation_with_perceptron 1.png]]