노트정리/알고리즘
병렬 알고리즘 - 병렬 컴퓨터
병렬 알고리즘- 여러 대의 컴퓨터를 사용하여 빠르게 처리하기 하기 위한걸 병렬 처리라고함. 병렬 컴퓨터에서 실행하도록 고안됨.병렬 컴퓨터병렬 컴퓨터는 CPU와 메모리 ,입출력 장치 등을 포함한 여러 개의 시스템들을 하나로 묶어서 구성하여 마치 하나처럼사용할 수 있는 컴퓨터를 말한다. 이러한 병렬 처리 구현을 위해 파이프라인 방식, 배열 프로세서, 다중 연산 기법 등을 사용한다. 구분 내용 SISD 일반적인 컴퓨터 구조( 폰 노이만 방식)단일 명령어 흐름에 따른 단일 데이터 흐름 컴퓨터하나의 명령에 따른 하나의 자료를 처리하는 구조병렬 처리는 파이프라인 구조로 구현 SIMD 단일 명령어 흐름에 따른 다중 데이터 흐름 컴퓨터하나의 명령에 따른 여러 자료를 동시에 처리하는 구조병렬 처리는 배열 처리와 벡터 처..
노트정리/알고리즘
확률적 알고리즘 과 유전 알고리즘
확률적 알고리즘알고리즘의 근본적인 부분에서 확률이 관계하고 있는 것을 확률적 알고리즘이라 함. 하지만 주어진 문제를 해결하는 알고리즘은결정론적 알고리즘으로 기술. 이는 항상 같은 결과를 출력하고 처리하기 때문이다. - 확률적 알고리즘은 항상 같은 결과를 출력하지 않음. 경우에 따라서 틀린 결과를 출력하거나 최적해가 아닌 근사해를 출력함.- 원하는 결과를 얻지 못할 확률이 매우 낮다는 조건하에서 주어진 문제를 해결하는데 활용함.- 난수를 필요로 함. 암호학 분야에서 매우 중요. 몬테카를로 , 라스베이거스 알고리즘이 있음. 몬테카를로 알고리즘 - 물리적, 수학적 시스템의 행동을 시뮬레이션하기 위한 계산 알고리즘이다.- 통계학적이며 일반적으로 무작위의 숫자를 사용한 비결정적인 방법. - 스타니스와프 울람이 모..
노트정리/알고리즘
NP - 완전 문제 근사 알고리즘
NP-완전 - NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합 , 모든 NP 문제를 다항시간 내에 NP-완전 문제로 환산 가능.- NP-완전 문제 중 하나라도 P에 속한다는 것을 증명하면 모든 NP 문제가 P에 속하기 때문에 P-NP 문제가 P=NP의 형태로 풀림.- 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어서 P-NP 문제는 P#NP 가됨. 쉬운 문제와 어려운 문제 판정 문제와 최적화 문제 가 있다.쉬운 문제 다항식 시간 알고리즘이 존재하는 문제 어려운 문제 다항식 시간을 초과하는 문제 판정 문제 문제의 해가 '예/아니오'로 나오는 문제 최적화 문제 최소치나 최대치를 구하는 형태의 문제 NP-완전성과 변환성 결정론적 알고리즘모..
노트정리/알고리즘
최단경로 - 다익스트라 , 플로이드 알고리즘
최단 경로는 어떤 정점 A에서 정점 Z까지의 최단 경로란 A에서 Z까지의 경로 중 간선의 가중치의 합이 가장 작은 경로 입니다. 단일 출발점 최단 경로- 단일 시작점에서 최단 경로 구하기 문제는 임의의 시작점을 1개 정하고 다른 노드들 사이의 최단 경로를 구하는데 사용.- 노드 사이의 거리가 모두 양수인 경우, 가장 널리 사용하는 것 다익스트라 알고리즘 다익스트라 알고리즘- 한 출발점에서 다른 모든 정점으로 최단 경로를 구하는 문제로 가중치를 갖는 간선은 없음. 모든 쌍 최단 경로- 모든 정점쌍 간의 최단 경로를 구하는 방법, 경로의 길이가 음인 사이클이 그래프에 존재하지 않을 것을 가정, 단일 출발점으로하여서 반복적으로 적용해 구할 수 있음.O(|V|s)- 경로의 길이가 음인 사이클이 그래프에 존재 X..
오늘도 삽질
