9.1 Intractability : 다룰 수 없음 tractability: 다룰 수 있음 Polynomial-Time Algorithm 다항함수와 로그함수만큼의 시간복잡도를 갖는 알고리즘 Polynomial-Time Algorithm으로 풀 수 없는 문제를 An Intractable Problem이라 한다. 9.3 문제의 3가지 카테고리 1. Polynomial-Time algorithm으로 풀 수 있는 문제들 ex) Sorting, Shortest Paths Problem, Minimum Spanning Tree Problem etc... 2. intractable 하다고 증명된 문제들 polynomial-time이 아닌 걸 증명할 수 있는 문제 ex) printing all Hamiltonian C..

1계층 연결장비: Hub 2계층 연결장비: Switch 3계층 연결장비: Router 허브만 쓰면 신호를 다 보내줌 스위치를 쓰면 B번으로만 신호를 보내줌 * Learning switch 학습기능으로 스위칭테이블을 작성 LAN 2에 같은 프레임 2개가 도착함 LAN1에 2개에 대한 프레임을 보냄 LAN2에 2배인 4개의 같은 frame이 도착함. -> 2배씩 증가하는 loop problem이 발생함. * 루프 문제 해결방법

1. Standard Ethernet 이더넷 주소는 6 bytes(48 bits) * 모든 digit이 F라면 broadcast * 10Mbs인 표준 이더넷을 더 높은 속도의 LAN으로 * collision domain: 충돌한 프레임이 전파되어 영향을 받게되는 영역 -> collision domain이 많아질 수록 충돌 확률이 낮아진다. * repeater: 1계층 대표장비 bridge, hub(a multiport repeater), switch(a multiport bridge) : 2계층 대표장비

HeapSort Heap: 각 노드의 값이 자식보다 크거나 같은 complete binary tree 어떻게 초기 힙을 구성할까? 1. 배열구성 2. 마지막 level서부터 올라가며 힙 만들기 어떻게 힙을 유지하며 루트 key를 제거할까? 1. 루트를 삭제한 후에 마지막 키를 루트로 올려준다. 2. 루트가 된 키를 힙이 될 때까지 아래로 내려준다. Worst Case Time Complexity of HeapSort Basic Operation: siftDown에서 키의 값 비교 Input Size: n(키의 개수) n= 2^d라고 가정 (d는 마지막 깊이의 값) 1. makeHeap에서의 siftDown -> shiftDown의 비교횟수를 계산할 때 마지막 레벨 d에서의 노드 1개는 무시하고 계산한다...

* 정렬 알고리즘은 시간복잡도가 세타(n)이 될 수 없다. lower bound를 찾아서 이것보다 낮아질 수 없음을 보이기 -> computational complexity analysis * key값의 비교만으로 정렬하기 예) lower bound : n lg n Insertion 정렬 : 이미 정렬된 배열에 원소 하나씩 추가하며 정렬하는 알고리즘 자기보다 작은 원소를 발견할 떄까지 앞으로 보내고 앞 원소는 뒤로 이동 Worst case 시간 복잡도: Basic Operation: s[j]와 x 비교 Input Size: n(key의 개수) -> 역순으로 정렬되어있을 때 worst case가 발생한다. -> 이 때 원소 i마다 i-1번의 비교가 발생한다. (2 n개의 원소가 배치되어있는 경우의 수는 n..

The Traveling SalesPerson Problem 1. 접근 [i1, i2, … , ik] : i1에서 i2,i3,...를 통해 ik로 가는 경로 최소화 문제라 lower bound 구해야 한다. 2. 각 노드의 bound를 계산하는 방법을 어떻게 정의 할까? -> state space tree의 깊이 k에서, 각 노드는 (k+1)개의 정점이 방문된 상태이다. 루트 노드의 lower bound = 남아있는 Vm 중 가장 낮은 edge 가중치들의 합 (Vm은 V의 원소들) 루트 노드가 아닌 경우[1,i2,...,ik]의 lower bound = V1부터 Vik까지 선택된 실제 weight의 합 + 남아있는 Vm 중 가장 낮은 edge 가중치들의 합 (Vm은 V의 원소들) -> 방문했던 곳으로 돌..