emzei

Part 2. Tuple Relational Calculus & Domain Relational Calculus 관계대수는 기호의 순서에 따라, 절차에 맞게 처리해야하기 때문에 순차적이다. 하지만 6장의 관계대수 부분 다음에 나오는 아래 이야기들은 표현의 절차를 없앰으로써, 비절차적으로 수행할 수 있음을 보여준다.관계 대수에 비하여 큰 비중을 차지하지 않으나, 어떤 개념인지 파악하고 넘어가면 좋을 것 같다. Tuple Relational Calculus (튜플 관계 해석) 비절차적 쿼리 언어로서, 각 쿼리는 다음과 같은 형태를 지닌다.(db1)이 것은 조건 P를 만족하는 모든 t에 대한 집합을 나타낸다.t는 튜플변수로서, t[A]는 속성 A에 대한 튜플 t의 값을 나타낸다T[ID], t[dept_name..

ch 6. Formal Relational Query Languages Relational Algebra (관계 대수) Procedural Language (순차적 언어)Six Basic Operators (기본 연산자)연산자는 1개 혹은 2개의 릴레이션을 입력으로 받아서, 새로운 릴레이션을 결과로 출력한다.질의를 R,A로 표현 Select (선택)표기 및 정의 :p는 selection predicate p는 과 같은 기호(term)로 연결되어 구성된 명제 대수에 해당하는 식 selection 예시 Project표기 및 정의A1, A2는 속성 이름이고, r은 릴레이션 이름언급된 속성에 한하여 (언급되지 않은 속성을 제외) 해당 릴레이션의 K개의 열(columns)이 결과로 나타냄중복되는 행은 결과에서 제..

계산 복잡도 (Çomputational Complexity)알고리즘의 분석특정 알고리즘의 효율 efficiency측정시간 복잡도 time complexity공간 복잡도 space/memory complexity문제의 분석일반적으로 계산복잡도 분석이라 하는 경우,어떤 문제에 대해 그 문제를 풀수 있는 모든 알고리즘의 하한(lower bound)을 결정 힙정렬 (Heapsort) 알고리즘완전 이진 트리 ( complete binary tree)트리 내부의 모든 노드에는 2개의 자식 노드가 존재하는 이진 트리모든 잎의 depth는 동일실질적 완전 이진트리depth(깊이) d-1까지는 완전이진트리이고,d의 노드는 왼쪽 끝애서부터 채워진 이진 트리힙의 성질 (heap property) : 어떤 마디에 저장된 값은..

Branch and bound ; “ 분기한정법 "공통점 w/ backtracking (되추적법) 문제 해결을 위해 상태공간트리(state space tree)가 사용됨차이점 w/ backtracking트리를 탐색하는 방법에 제한이 없음최적화 문제에서만 사용됨설계 전략노드가 유망한지 결정하기 위해 한 노드에서의 bound 값을 계산해야한다 (bound값 - 미래의 가치를 예측한 값)그 숫자는 해결책의 값의 bound(한정값)으로서, 해당 노드를 넘어 확장하면서 얻을 수도 있는 값만약에 해당 bound값이 현재 최적의 해결책보다 낫지 않은 경우에, 해당 노드는 non-promising(유망하지않음) ; 즉, 더 나은 경우 promising(유망함) Breath-first search (너비 우선 검색)검색..

Backtracking (되추적법) (사전 설명) Depth-First Search (깊이우선 탐색)Root 노드 선 방문 후, 그 후 자식 노드를 차례대로 방문 (Pre-order tree traversal) n-Queen problem(n=4) 4-Queens Problem : 4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스판에 두는 문제. 4-queen 문제에 대한 상태 공간 트리 (모든 경우를 표시) 서로 상대방을 위협하지 않기 위해서, 같은 행/열/대각선 상에 위치하지 않아야 함.Brute-force Approach : 각 Queen을 각각 다른 행에 할당한 후, 차례로 점검.State Space Tree (상태공간트리) 를 이용root 노드에서 leaf 노드까지의 경로를 cand..

다이나믹 프로그래밍의 단점 --> 인스턴스를 더 작은 인스턴스로 쪼개어 재귀적으로 무제 해결최적화 문제를 푸는데 적합. 최적화 원칙이 적용되는지를 점검해보기만 하면 됨그러나 때로는 불필요하게 복잡. 0-1 Knapsack 해결 가능. ★ 탐욕적 접근법: 해당 단계에서 최적의 해를 구함 (locally optimal) 결정해야 하는 단계마다 최적의 해를 구하여, 최종적으로도 해답에 도달하고자 함허나, 반드시 local에서의 최적의 해가 global 에서의 최적의 해라고 보장할 수 없음 (항상 최적의 해답인지 검증이 필요함)최적화 문제를 푸는데 적합. 알고리즘이 존재할 경우 효율적. 알고리즘이 최적인지 증명해야함. Knapsack 문제는 풀지만, 0-1 Knapsack 문제는 풀 수 없음. 탐욕적 접근법의 ..

운영체제의 교착상태에 대처하는 방법은 크게 3가지가 있다.교착상태를 발생시키지 않는 것교착상태 발생 후 회복하는 것교착상태를 방지하는 것 이 중에서도, 발생시키지 않는 것은 다시 예방과 회피의 방법으로 나뉜다.예방 --> 교착상태의 발생 조건이 만족되지 않도록 함cf. 교착상태 발생 조건상호배재 (mutual exclusion)점유/대기 (hold and wait)비선점 (no preemption)순환대기 (circular wait)회피 --> 현재 및 미래에 교착상태가 발생하지 않도록 자원할당을 함 은행가 알고리즘은 교착상태 회피 방법 중 하나이다. (deadlock avoidance)교착 상태를 회피하는 것은, 미래의 자원 사용을 파악하여 순환대기 조건이 만족되지 않도록 하는 것이다. 참고 링크 - ..

> 난수를 사용하여 함수의 값을 확률적으로 계산하는 알고리즘.> 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 근사적으로 계산할 때 사용 참고 링크 - https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%EB%B0%A9%EB%B2%95- http://statphys.ssu.ac.kr/monte/

동적 프로그래밍 (dynamic programming)분할 정복법과 유사문제를 더 작은 단위로 분할작은 단위를 먼저 해결하고, 결과를 저장하고, 후에 결과가 필요할 때 재계산 하지 않고 결과를 찾아다 씀 상향식 (Bottom Up)작은 단위로 나뉘어진 것들이 상관관계가 있는 경우 적합 (Ex. 반복적 피보나치)재귀적 관계식을 세워서 상향식으로 해결! 이항계수 구하기 (Binomial Coefficient)기본공식 관계식으로 표현된 식 분할정복법으로 구하게 되면 재귀 호출을 수행해야함동적 프로그래밍 설계 전략1단계 : 재귀 관계식 정립 2차원 배열을 만들어서 각 인덱스에 해당하는 값을 저장하여 그 다음 관계식에서 활용2단계 : 상향식 방법으로 문제 해결알고리즘 int bin2(int n, int k) { ..

분할 정복법 (divide-and-conquer)분할 => 해결하기 쉽도록, 문제를 여러개의 작은 부분으로 나눔정복 => 작게 나뉘어진 문제를 해결통합 => 필요에 따라 해결된 답을 모음==>> 하향식(Top-down) 접근법 Binary search using recursive method (이분검색, 재귀알고리즘)문제 : 크기가 n인 정렬된 배열에서 x가 있는지 결정하기입력 : 비내림차순으로 정렬된 배열(1~n), 찾고자하는 항목(x)출력 : x가 존재할 경우 해당 위치, 없는 경우 0 #include int goal; int array[10]={1,2,3,4,5,6,7,8,9,10}; int location(int start, int end) { int mid; if(start > end) retu..