Greedy Algorithm

• Dynamic programming?
  • recursive property(재귀함수)로 풀 수 있는 문제를 DP로 풀 수 있음
• Greedy approach
  • 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택
  • simple is best
  • local에서는 최적, 최적을 모아서 최종답을 만들어도 검증까지 해야함

Greedy Approach 설계 절차

• Selection procedure (선정 과정)
  • 현재 상태에서 가장 좋다고 생각되는 해답을 찾음
• Fesibility check(적정성 점검)
  • 적절한지 결정
• Solution check(해답 점검)
  • 최적의 해인지 결정

Spanning Tree (신장 트리)

• 그래프의 모든 vertex G를 가지고 있는 트리
• 비방향성 그래프 G에서 순환 제거, 연결된 부분 그래프가 되도록 이음선 제거
• G안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분그래프

Minimum Spanning tree(최소비용 신장트리)

• 가중치의 합이 최소가 되는 신장트리
• 그래프는 트리형태(cycle없는)여야함

브루트포스 방식

• 모든 신장트리를 다 고려해보고, 그중에서 최소비용을 고름

• 분석:

  • 최악의경우, 지수보다 나쁨

Prim’s Algorithm

• v1에서 vi까지 모든 정점을 돌면서 가장 가까이 있는 vnear찾음

  • nearest[i]: vi에서 가장 가까운 정점
  • distance[i]: 거리

Every-case Time Complexity Analysis

• 단위연산: repeat 루프 안에 있는 두개의 for루프 안의 명령문

• inputSize: 마디개수, n

• 분석: repeat-루프가 n-1번 반복

  • T(n) = 2(n-1)(n-1)

최적여부 검증 (Optimality Proof)

• Definition

  • 만약 E의 부분집합 F에 MST가 되도록 이음선을 추가할 수 있으면 (MST에 F가 포함되어있으면) F는 Promising(유망하다) 하다고 함

• Lemma (*중요)

  • F는 E의 유망한 부분집합, Y는 F안에 있는 이음선 들에 의해서 연결된 정점의 집합.
  • 이때 Y에 있는 어떤 정점과 V-Y에 있는 어떤 정점을 잇는 이음선 중에서 가중치가 가장 작은 이음선을 e라고 하면..
  • F + e는 유망하다

Prim’s Algorithm 특징?

• 특정 v1을 기준으로 뻗어나감

Kruskal’s Algorithm

• edge그래프를 기준으로

1. Edge List를 sorting해줌
2. 순서대로 추가해도 되면 연결
3. subset을 merge해줌
4. 다연결될 때까지 반복

Worst-Cast Time Complexity Analysis

(시험출제)

• 단위연산: 비교문
• 입력크기: 정점의 수 n과 이음선의 수 m

1. 정렬하는데 걸리는 시간 O(m lg m);
2. n개의 서로소인 집합 set을 초기화 시간 O(n)
3. 루프 m번 수행, 서로소인 집합 자료구조 사용, find, equal, merge등 포함하면 O(m lg n)

• 여기서 m >= n-1, 1과 3은 2를 지배
  W(m, n) = O (m lg m);

• 최악의 경우 모든 정점이 다른 모든 정점과 연결,
  M = n(n-1) / 2 = O(n^2), 최악의 경우 시간복잡도는 W(m, n) O(n^2 lg n)

Dijikstra’s Algorithm

• 한 정점에서 다른 모든 정점으로 가는 최단경로 문제
• Single-Source Shortest Paths: 시작점v1

1. v1에서 갈수있는 경로로 table을 만듬
2. table에서 가장 짧은 거리를 선택해서 그지역을 경유하는 경로까지 비교
3. 모든 정점을 경유하는 거리를 비교함

Define touch & length

• touch[i]: I까지 가는 경로의 마지막 노드
• length[i]: 현재까지 구해진 최단거리

length[vnear] = -1로 만들어주는 이유?

• 현재 선택된 노드를 다시 선택하는걸 방지

The Knapsack Problem

• 배낭에 넣을 수 있는 최대 가치(Array)를 구하는 문제

The Knapsack Problem: Greedy

• 탐욕적알고리즘: n개의 물건에 대해 모든 부분집합 고려
• 부분집합의 수는 2^n개

The 0-1 Knapsack Problem

• 일반 Fractional Knapsack problem: 남은공간 물건을 잘라서 꽉채울수있음

• 0-1 Knapsack problem: 물건을 못자름

• Fractional Knapsack: Greedy로 구할 수 있음(무게당 가치가 가장 높은순)

Dynamic Programming Approach

• i > 0, w > 0 최대무게: w

• i번째 항목중에서 얻어진 최고의 이익(optimal profit) = P[i][w];
  if w[i] <= w:
  max(P[i-1][w], p[i] + P[i-1][w-w[i]]);
  else:
  p[i-1][w];

여기서 P[i-1][w]는 i번째 항목을 포함시키지 않은 경우의 최고 이익,
p[i] + P[i-1][w-w[i]]는 i번째 항목을 포함시키는 경우 최고 이익

최대이익 P[n][W]는?

• intP[0..n][0..W]의 2차원배열을 만든 후 각 항을 계산해서 넣음
• P[0][w] = 0, P[i][0] = 0이므로 O(nW);

DP방법 보완

• 임의로 W = n!이라 한다면 수행시간은 O(n*n!)이 되므로 무작정 알고리즘보다 나을게 없음

• 최악을 O[n^2]로 만드는법? 무작위보다 빠르게하는법?

  • **P[n][W]를 계산하기 위해 (n-1)번째 행을 모두 계산할 필요 없음)

  P[n][W] = max(P[n-1][W], p[n] + P[n-1][W-w[n]]]);
  따라서 (n-1)번째 항은 P[n-1][W]와 P[n-1][W-w[n]]만 필요
  i번째항에 필요한 항목만 결정해서 계산함

• Worst case

  • O(2^i)

• O(min(2^n, nW));

Greedy vs. Dynamic Programming

Transport-layer services

Transport vs. Network layer

• Network: hosts 사이
• Transport: processes 사이

Internet transport-layer protocols

• Reliable in-order delivery -> Transmission Control Protocol(TCP)
• Unrealiable, unordered delivery -> User Datagram Protocol (UDP)

Principles of network applications

Application architectures

• client-server
• peer-to-peer

Client-server architecture

• server:

  • always-on host
  • permanent IP address

• clients:

  • communicate with server
  • may be intermittently connected
  • do not communicate directly

P2P architecture

• No always-on server

Processes communicating

• Process: program running within a host
  • 같은 host 에서, inter-process communication을 통하여 두개의 프로세스가 통신

Sockets

• Process sends/receives messages to/from its socket
• Socket analogous to door

Addressing processes

• Identifier includes both IP address and port numbers associated with process on host.

Example port numbers:

• HTTP server: 80

• mail server: 25

• to send HTTP message to usaint web server:

• IP address: 203.253.31.114

• port number: 80

App-layer protocol defines

• Types of messages exchanged,
  • E.g., request, response
• Message syntax
  • 구역 나누기

2020-1:
Host A 와 Host B 가 30,000 km 떨어진 곳에 위치하고 있고 R=5Mbps 의 속도의 네트워크 링크로
연결되어져 있다 해당 네트워크의 propagation delay 는 𝟐.𝟓×𝟏𝟎^𝟖 meters/sec 이다
Host A 에서 Host B 로 1,000,000 bits 의 파일을 분할없이 한번에 보낸다고 가정했을 경우 파일을
보내는 시간동안 네트워크 링크에 존재하는 최대 비트 수는 얼마인가
(네트워크 링크는 H ost A 와 Host B 만 사용하는 링크임 , Mega = 10^6)

transmission delay: 0.2s
prop delay: 0.12s
600,000 bits

2020-2:
네트워크를 통해 사이즈가 큰 데이터를 보낼 때 일반적으로 해당 데이터를 작은 사이즈의
패킷으로 쪼갠 후 보내게 된다 해당 패킷들을 받는 수신자는 수신한 패킷들을 재조합 하여
데이터 원본을 수신한다 이러한 과정을 message segmentation 이라고 부르기도 한다
아래 그림은 message segmentation 이 없는 데이터 전송과 message segmentation 이 적용된
데이터 전송을 나타내고 있다 Source 에서 Destination 사이에는 스위치가 2 개가 존재하고 ,
Source 가 Destination 으로 보내려는 데이터 의 크기는 𝟏.𝟐×𝟏𝟎^𝟖 bits 이다 네트워크 링크 전송
속도는 R=4Mbps 일 때 아래 물음에 답하시오 propagation, queuing, and processing delays 는
무시한다

1 - Message segmentation 이 없는 데이터 전송 (위 그림의 (a)) 를 고려했을 때 Source 에서 Destination 까지 전체 데이터를 보내는데 걸리는 시간은 얼마인가?
3*L/R = 3 * 1.2 * 10^8 / 4 * 10^6 = 3 * (1.2 * 10^2 / 4) = 3 * 0.3 * 10^2 = 3 * 30 = 90s

2 - 전체 데이터가 1200 개의 패킷으로 나누어지고 각 패킷의 길이는 100,000bit 라고 가정해보자 Message segmentation 가 적용된 데이터 전송 (위 그림 의 (b)) 를 고려했을 때 Source 에서 Destination 까지 첫번째 패킷을 보내는데 걸리는 시간은 얼마인가?
100,000 / 5,000,000 = 1/50 = 0.02s,
0.02s * 3 = 0.06s

3 - 전체 데이터가 1200 개의 패킷으로 나누어지고 각 패킷의 길이는 100,000bit 라고 가정해보자 Message segmentation 가 적용된 데이터 전송 (위 그림 의 (b)) 를 고려했을 때 Source 에서 Destination 까지 전체 패킷 총 1200 개의 패킷 을 보내는데 걸리는 시간은 얼마인가?
하나의 패킷이 걸리는 시간 0.6s, 하나의 구간을 통과하는 시간 0.2s, 3개를 동시에 하므로 1200 * 0.2s = 240s - 0.4s = 239.6s

4 - message segmentation 장단점
장점: message를 나눠서 보내면 중간에 라우터에서도 동시에 전송을 할 수 있어서 시간이 짧아짐
단점: 패킷이 중간에 없어질 수 도있음

What’s the Internet

“nuts and bolts” view

billions of connected computing devices:

• hosts = end systems
• running networks apps

communication links

• fiber, copper, radio, stellite
• transmission rate: bandwidth

packet switches: forward packets (chunks of data)

• routers and switches

Internet: “network of networks”

protocols control sending, receiving of message

• e.g., TCP, IP, HTTP, …

Internet standards

• Internet Engineering Task Force (IETF) 에서 Request for comment (RFC)라는 표준 문서들을 개발함

A service view

infrasturcture that provides services to applications:

• Web, VoIP, email, games, e-commerce, social nets, …

Socket interface

• allows sending and receiving app programs to “connect” to Internet
• provides service options, analogous to postal service

What’s a protocol?

network protocols:

• machine rather than humans
• three way handshaking

protocols define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt

Network edge

A closer look at network structrue

Network edge (종단 시스템)

• hosts: clients and servers

Access networks

• Home, Enterprise, Mobile, …

  Physical media

• wired, wireless communication links

Access networks and pysical media

How to connect end systems to end router?

• residential(Home) access networks
• institutional access networks
• mobile access networks

keep in mind:

• bandwidth (bits per second) of access network? (속도)
• shared or dedicated? (나만쓰는가?)

Home Access

Home Access: DSL

Digital Subscriber Line (DSL)

• 전화선을 이용한 통신

Home Access: Cable Internet Access

HFC: hybrid fiber coax (동축 케이블)

Coaxial and fiber cables attach homes to ISP router

• fiber와 Coaxial 동시에 사용

Home Access: FTTH

Fiber to the home

• fiber만 사용

Home Access: A typical home network

Enterprise access

Enterprise access: Ethernet

Physical media

Physical media: Twisted-Pair Copper Wire

• Unshielded twisted pair (UTP)
• Shielded twisted pair (STP)

Pysical media: Radio

• no physical “wire”

Network core

• Mesh of interconnected routers

Packet-switching

• Message는 application이 원하는 데이터를 포함
• Message를 잘게 쪼갠게 packets

Packet들이 Communication link로 이동할때 transmission rate기반으로 이동

• 패킷의 크기는 L bits, 전송 속도는 R bits/sec
  

Packet-switching: Store-and-Forward

• 저장하고 전달

Ex) L = 7.5 Mbits, R = 1.5 Mbps, one-hop transmisson delay = 5 s

• End to End Delay = 2L/R

• 3개의 패킷을 보내는 시간

  • L/R시간, 첫번째 패킷이 라우터에 도착
  • 2L/R시간, 첫번째 패킷이 목적지 도착, 두번째 패킷 라우터 도착
  • 3L/R시간, 두번째 패킷이 목적지 도착, 세번째 패킷 라우터 도착
  • 4L/R시간, 세번째 패킷이 목적지 도착

• 하나의 패킷을 N개의 링크가 있는 곳으로 보내는 End to End 딜레이 (N links (eash of rate R), N-1 Routers)

  • D_end-to-end = N X (L/R)

Queuing Delays and Packet Loss

Queuing and Loss:

• 도착하는 패킷보다 보내는 패킷이 느릴경우
• 딜레이 + 공간 꽉차면 Loss까지 생김
  

Forwarding and Routing

• Forwarding: input에서 output으로 움직이는것
• Routing: 어디로 갈지 정해주는것

Circuit switching

• 데이터 회선이 정해지고 회선단위로 데이터를 주고받음

frequency-division multiplexing (FDM) - 주파수분할

time-division multiplexing (FDM) - 시분할

Silend Period -> 네트워크 자원낭비로 이어짐

Packet Switching vs. Circuit switching

• Packet switching allows more user to use network

  • 1 Mb/s link
  • each user:
    • 100 kb/s when “active”
    • the probability that a specific user is active is 0.1

• circuit switching:

  • support only simultaneous 10 users (1 Mbs/ 100 Kbps)

• Packet switching:

  • With 35 users, probability > 10 active at same time is less than 0.0004
  • 35C11(0.9)24(0.1)11 < 0.0004

Packet switching이 좋지만, packet delay나 loss가 발생할 수 있음

• reliable한 데이터 전송이 필요

Network of networks

• End systems은 access ISPs (Internet Service Providers)

Delay, Loss, Throughput in Networks

Four sources of packet delay

• Total nodal delay (d_nodal)

  • nodal processing delay (d_proc),
  • queuing delay (d_queue),
  • transmission delay (d_trans),
  • propagation delay (d_prop)

  

d_proc: nodal processing

• check bit errors
• determine output link
• typically < msec

d_queue: queueing delay

• 라우터 개수에 의존
• 가장 중요

d_trans: transmission delay

• L: packet length (bits)
• R: link bandwidth (bps)
• d_trans = L/R

d_prop: propagation delay

• d: length of physical link
• s: propagation speed (통신매체에 따라 다름)
• d_prop = d/s

Transmission delay vs. Propagation delay

Caravan analogy

• cars “propagate” at 100 km/hr

• toll booth takes 12sec to service car (bit transmission time)

• 2번째 톨게이트까지 가는 시간?

  • 첫번째 톨게이트 12*10 = 120s
  • 100km 가는 시간 = 1hr
  • A: 62 min

Queueing delay

• R: link bandwidth (bits / sec)
• L: packet length (bits)
• a: average packet arrival rate (packets/sec)
• La/R: traffic intersity
  • La/R이 0에 가까우면: 딜레이가 거의 없음
  • La/R이 1에 가까우면: queueing delay가 커짐
  • La/R이 1보다 크면: 거의 무한대의 딜레이

Packet loss

• 버퍼가 가득 차면 loss 됨

End-to-End Delay

• N-1개의 라우터가 있을때
• End-to-End Delay = N x (d_proc+d_trans+d_prop)

Throughtput(처리량)

Networks under attack: Security

Network security

Dynamic programming

• Similar to divide-and-conquer
• small instances first, store the results, whenever we need a result, look it up instead of recomputing it.

알고리즘: Using Divide-and-Conquer

• 문제: 이항계수를 계산한다
  • 입력: 음수가 아닌 정수 n과 k, 여기서 k <= n
  • 출력: bin, [n k]

1
2
3
4
5
6

int bin(int n, int k) {
  if (k == 0 || n == k)
    return 1;
  else
    return bin(n-1, k-1) + bin(n-1, k);
}

시간복잡도 분석:

• 분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않음
  • 이유? 재귀호출(recursive call)할때 같은 계산을 반복해서 수행하기 때문
  • 예를 들면, bin(n-1, k-1)과 bin(n-1, k)는 둘다 bin(n-2, k-1)의 결과가 필요한데, 따로 중복 계산이 됨

[n: k]를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2[n: k]-1이다. (증명을 해보자)

증명: (n에 대한 수학적 귀납법으로 증명)

• 귀납출발점: 항의 개수 n이 1일 때 2[n: k]-1 = 2 x 1 - 1 = 1이 됨을 보이면 된다.

         [1: k]는 k=0이나 1일때 1이므로 항의 개수는 항상 1이다.
  

• 귀납가정: [n: k]를 계산하기 위한 항의 개수는 2[n: k] - 1이라고 가정한다.
• 귀납절차: [n+1: k]를 계산하기 위한 항의 개수가 2[n+1: k] - 1임을 보이면 된다.

       알고리즘에 의해서 [n+1: k] = [n: k-1] + [n: k] 이므로, [n+1: k]를 계산하기 위한 항의 총 개수는 [n: k-1]을 계산하기 위한 총 개수와 [n: k]를 계산하기 위한 항의 총 개수에다가 이 둘을 더하기 위한 항 1을 더한 수가 된다.
       그런데 [n: k-1]을 계산하기 위한 항의 개수는 가정에 의해서 2[n: k-1] -1이고, [n: k]를 계산하기 위한 항의 개수는 가정에 의해서 2[n: k] - 1이다.
  

동적계획식 알고리즘 설계전략

1. Establish a recursive property (재귀 관계식을 정립):

• 2차원 배열 B를 만들고, 각 B[i][j]에는 [i: j]값을 저장하도록 하면, 그 값은 다음과 같은 관계식으로 계산할 수 있다.
  

2. Solve an instance of the problem in a bottom-up fashion:
   • [n: k]를 구하기 위해서는 다음과 같이 B[0][0]부터 시작하여 위에서 아래로 재귀 관계식을 적용하여 배열을 채워 나가면 된다.
     결국 값은 B[n][k]에 저장된다.
     

• 문제: 이항계수를 계산한다.
  • 입력: 음수가 아닌 정수 n 과 k, 여기서 k <= n
  • 출력: bin, [n: k]

1
2
3
4
5
6
7
8
9

int bin2(int n, int k) {
  index i, j;
  int B[0..n][0..k];
  for(i = 0; i <= n; i++)
    for(j = 0; j <= minimum(i,k); j++)
      if(j==0 || j==1) B[i][j] = 1;
      else B[i][j] = B[i-1][j-1] + B[i-1][j];
    return B[n][k];
}

동적계획 알고리즘의 분석

• 단위연산: for-j 루프 안의 문장

• 입력의 크기: n, k
  i = 0일 때 j-루프 수행 횟수 : 1
  i = 1일 때 j-루프 수행 횟수 : 2
  i = 2일 때 j-루프 수행 횟수 : 3
  ……………
  i = k-1일 때 j-루프 수행 횟수 : k
  i = k일 때 j-루프 수행 횟수 : k + 1
  i = k+1일 때 j-루프 수행 횟수 : k + 1
  ……………
  i = n일 때 j-루프 수행 횟수 : k + 1

  따라서 총 수행횟수는:
  1 + 2 + 3 + … + k + (k+1) + … + (k+1) = k(k+1)/2 + (n-k+1)(k+1) = (2n-k+2)(k+1)/2 = O(nk)

그래프

그래프 용어

• 정점(vertex, node), 이음선(edge, arc)
• 방향 그래프(directed graph, or digraph)
• 가중치(weight), 가중치 포함 그래프 (weighted graph)
• 경로(path) - 두 정점사이에 edge가 있는 정점들의 나열
• 단순경로(simple path) - 같은 정점을 두 번 지나지 않음
• 순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로
• 순환그래프(cyclic graph) vs 비순환 그래프 (acyclic graph)
• 길이(length): the sum of weights on the path (weighted graph)

            the number of edges on the path (unweighted graph)
  

Shortest Path

• Shortest Path: 한 도시에서 다른 도시로 직항로가 없는 경우

             가장 빨리 갈 수 있는 항로를 찾는 문제
  

• 문제: 가중치 포함, 방향성 그래프에서 최단경로 찾기

• Optimization problem (최적화 문제)의 정의

  • 주어진 문제에 대하여 하나 이상의 많은 해답 후보가 존재할 때, 이와 연관된 값이 최소 또는 최대인 해답(optimal solution)을 찾아야 하는 문제
  • 에너지 최소화 문제라고도 함.

• shortest Path는 Optimization problem에 속함

Brute-force algorithm(무작정 알고리즘)

• 한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소길이를 찾는다.

동적계획식 설계전략 - 자료구조

• 그래프의 인접행렬(adjacent matrix)식 표현: W

동적계획식 설계절차

1. Establish a recursive property

   • D(k-1)을 가지고 D(k)를 계산할 수 있는 재귀 관계식을 정립
     • D(k)[i][j] = minimum(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
   • 경우 1: {v1, v2,…, vk}의 정점들 만을 통해서 vi에서 vj로 가는 최단 경로가 vk를 거치지 않는 경우,

         보기: D(5)[1][3] = D(4)[1][3] = 3
     

   • 경우 2: {v1, v2,…, vk}의 정점들 만을 통해서 vi에서 vj로 가는 최단 경로가 vk를 거치는 경우,

         보기: D(2)[5][3] = D(1)[5][2] + D(1)[2][3] = 4 + 3 = 7
         보기: D(2)[5][4]
     

2. 상향식으로 k=1부터 n까지 다음과 같이 이 과정을 반복하여 해를 구한다.
   D(0), D(1),……,D(n)

Floyd’s Algorithm I

• 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산

1
2
3
4
5
6
7
8

void floyd(int n, const number W[][], number D[][]) {
  int i, j, k;
  D = W;
  for(k=1; k <= n; k++)
    for(i=1; i <= n; i++) 
      for(j=1; j <= n; j++)
        D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);
}

Floyd’s Algorithm II

• 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산, 각각의 최단경로를 구하라.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void floyd2(int n, const number W[][], number D[][], index P[][]) {
  index i, j, k;
  for(i=1; i <= n; i++)
    for(j=1; j <= n; j++)
      P[i][j] = 0;
  D = W;
  for(k=1; k <= n; k++) 
    for(i=1; i <= n; i++) 
      for(j=1; j <= n; j++)
        if(D[i][k] + D[k][j] < D[i][j]) {
          P[i][j] = k;
          D[i][j] = D[i][k] + D[k][j];
        }
}

최단경로의 출력

1
2
3
4
5
6
7

void path(index q,r) {
  if(P[q][r] != 0) {
    path(q, P[q][r]);
    count << "v" << P[q][r];
    path(P[q][r], r);
  }
}

최적의 원칙

• 어떤문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적 해를 항상 포함하고 있으면 그 문제는 최적의 원칙(the principle of optimality)이 적용된다 라고 한다.

Optimal Binary Search Trees

• definition
  • binary search tree
    • Ordered set
    • Each node contain one key
    • The keys in the left subtree are less than or equal to the key in that tree
  • Depth - number of edges from the root
  • balanced - if the depth of the 2 subtrees of every node never different by more than 1
  • optimal - the average time it takes to locate a key is minimized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void optsearchtree(int n, const float p[], float& minavg, index R[][]) {
  index i, j, k, diagonal;
  float A[1...n+1][0..n];
  for(i=1; i<=n; i++) {
    A[i][i-1] = 0; A[i][i] = p[i]; R[i][i] = i; R[i][i-1] = 0;
    A[n+1][n] = 0; R[n+1][n] = 0;
    for(diagonal=1; diagonal <= n-1; diagonal++)
      for(i=1; i<=n-diagonal; i++) {
        j = i + diagonal;
        A[i][j] = minimum(A[i][k-1] + A[k+1][j]) + 
        R[i][j] = a value of k that gave the minimum;
      }
      minavg = A[1][n];
  }
}

The Traveling Salesperson Problem

• Problem Definition

  • Determine a shortest route that starts at the salesperson’s home city, visits each of the cities once, and ends up at the home city

• Adjacent matrix W
  

  • V = set of all the vertices
  • A = a subset of V
  • D[vi][A] = length of a shortest path from vi to v1

            passing through each vertex in A exactly once
    

• Length of an optimal tour = minimum(W[1][j] + D[vj][V - {v1, vj}])

```C
void travel(int n, const number W[][], index P[][], number& minlength) {
index i, j, k;
number D[1..n][subset of V-{v1}];
for(i=2; i<=n; i++)
D[i][0] = W[i][1];

for(k=1; k<=n-2; k++)
for(all subsets A V-{v1} containing k vertices)
for(i such that i!= 1 and vi is not in A) {
D[i][A] = min(j:vj A)(W[i][j]+D[j][A-{vj}]);
P[i][A] = value of j that gave the minimum;
}
D[1][V-{v1}] = min(2<=j<=n)(W[1][j] + D[j][A-{v1,vj}]);
P[1][V-{v1}] = value of j that gave the minimum;
minlength = D[1][V-{v1}]
}

조원: 허주미, 홍지윤

발표 주제 선택

Loss Function, Cost Function

• 모델의 예측값과 실제 값의 오차

Example of Loss Function

Mean Squared Error: 에러의 제곱 이용

• 계산 간편
• 크기에 의존적

Cross Entropy: 확률의 불확실성 수치

• 실제 분포를 모를때 예측가능
• 0일수록 출력이 확실함

Quicksort

• 분할교환정렬(patition exchange sort)라고 불린다.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  void quicksort(index low, index high) { index pivotpoint; if (high > low) { partition(low, high, pivotpoint); quicksort(low, pivotpoint-1); quicksort(pivotpoint+1, high); } } void partition(index low, index high, index& pivotpoint) { index i, j; keytype pivotitem; pivotitem = S[low]; //pivotitem을 위한 첫번째 항목을 고른다. j = low; for(i = low + 1; i <= high; i++) if(S[i] < pivotitem) { j++; exchange S[i] and S[j]; } pivotpoint = j; exchange S[low] and S[pivotpoint]; //pivotitem값을 pivotpoint에 넣는다 }

분석

• 단위연산: S[i]와 key와의 비교
• 입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1
• 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, T(n) = n - 1이다.

최악의 경우 시간복잡도 분석

• 단위연산: 분할 알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열 S가 가지고 있는 항목의 수, n
• 분석: 이미 비내림차순으로 정렬이 되어있는 배열을 정렬하려는 경우가 최악의 경우가 됨.

    비내림차순이면 첫번째(pivot)항목보다 작은 항목은 없으므로, 크기가 n인 배열은 크기가 0인 부분은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 하여 계속 쪼개진다. 따라서,
    T(n) = T(0) + T(n-1) - n - 1
    그런데 T(0) = 0이므로 재현식은 다음과 같이 된다.
    T(n) = T(n-1) + n - 1, n > 0이면
    T(0) = 0 
    
    이 재현식을 풀면,
    T(n) = T(n-1) + n - 1
    T(n-1) = T(n-2) + n - 2
    T(n-2) = T(n-3) + n - 3
    ...
    T(2) = T(1) + 1
    T(1) = T(0) + 0
    T(0) = 0
    
    T(n) = 1 + 2 + ... + (n-1) = n(n-1) / 2
  

평균의 경우를 고려한 시간복잡도 분석

• 단위연산: 분할알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열이 S가 가지고 있는 항목의 수, n
• 분석:

Divide-and-Conquer

• 분할정복식 설계전략
• 분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눔
• 정복(Conquer): 나눈 작은 문제를 각각 해결
• 통합(Convbine): 해결된 해답을 모음
• 이러한방식을 Top-Down(하향식) 접근 방법이라고 한다

Binary Search(이분검색): 재귀 알고리즘

• 분할: 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택
• 정복: 선택된 반쪽 배열에서 X를 찾는다
• 통합: 필요없음

재귀 알고리즘(recursive algorithm)에서 모든 재귀호출이 알고리즘의 마지막(꼬리) 부분에서 이루어 질 때 꼬리 재귀호출(tail recursion)이라고 함 - 그 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기 수월ㅋ

최악의 경우 시간복잡도 분석

• 단위연산: x와 S[mid]의 비교
• 입력 크기: 배열의 크기 n(= high - low + 1)
• 알고리즘에서는 단위연산으로 설정한 조건문을 while루프 내에서 2번 수행하지만, 사실상 비교는 한번만 수행
  (1) 어셈블리언어로는 하나의 조건 명령으로 충분히 구현 가능
  (2) x를 찾기 전까지는 항상 2개의 조건문을 수행하므로 하나로 묶어서 한 단위로 취급해도 됨

경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우

• 시간복잡도를 나타내주는 재현식(recurrence)는 다음과 같다
  W(n) = W(n/2)+1, n > 1이고, n = 2<sup>k</sup>(k>=1)
  W(1) = 1
  이식의 해는 다음과 같이 구할 수 있다
  W(1) = 1
  W(2) = W(1) + 1 = 2
  W(4) = w(2) + 1 = 3
  W(8) = W(4) + 1 = 4
  W(16) = W(8) + 1 = 5
  …
  W(2<sup>k</sup>)=k+1
  …
  W(n) = lg n + 1

  증명: 수학접 귀납법:

  귀납 출발점: n=1이면, W(1) = 1 = lg 1 + 1.
  귀납 가정: 2의 거듭제곱(power)인 양의 정수 n에 대해서, W(n)=lg n + 1라고 가정
  귀납 단계: W(2n) = lg(2n) + 1임을 보이면 된다. 재현식을 사용하면,
  W(2n) = W(n) + 1

    = lg n + 1 + 1
    = lg n + lg 2 + 1
    = lg(2n) + 1
  

경우 2: 일반적인 경우 - 반쪽 배열의 크기는 [n/2]이 됨

합병정렬(Mergesort)

1
2
3
4
5
6
7
8
9
10
11
12

void mergesort (int n, keytype S[]) {
  const int h = n / 2, m = n - h;
  keytype U[1..h], V[1..m];

  if(n>1) {
    copy S[1] through S[h] to U[1] through U[h];
    copy S[h+1] through S[n] to V[1] through V[m];
    mergesort(h,U);
    mergesort(m,V);
    merge(h,m,U,V,S);
  }
}

시간복잡도 분석

합병 알고리즘의 최악의 경우 시간복잡도 분석

• 단위연산: U[i]와 V[j]의 비교
• 입력크기: 2개의 입력 배열에 각각 들어있는 항목의 개수: h와 m
• 분석: i=h이고, j=m-1인 상태로 루프(loop)에서 빠져 나가는 때가 최악의 경우로서 (V에 있는 처음 m-1개의 항목이 S의 앞부분에 위치하고, U에 있는 h개의 모든 항목이 그 뒤에 위치하는 경우), 이때 단위연산의 실행 횟수는 h + m - 1이다. 따라서 최악의 경우 합병하는 시간복잡도는 W(h, m) = h + m - 1.

합병정렬 알고리즘의 최악의 경우 시간복잡도 분석

• 단위연산: 합병 알고리즘 merge에서 발생하는 비교
• 입력크기: 배열 S에 들어 있는 항목의 개수 n
• 분석: 최악의 경우 수행시간은 W(h,m) = W(h) + W(m) + h + m - 1이 된다. 여기서 W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는데 걸리는 시간, 그리고 h + m - 1은 합병하는데 걸리는 시간이다. 정수 n을 2<sup>k</sup>(k>=1)이라고 가정하면, h= n/2, m=n/2가 된다. 따라서 최악의 경우 재현식은:
  W(n) = 2W(n/2)+n-1 n>1이고, n=2<sup>k</sup>(k>=1)
  W(1) = 0 왜냐하면 합병이 전혀 이루어지지 않으므로 이 재현식의 해는 아래의 도사정리의 2번을 적용하면
  W(n) = O(n lg n)이 된다.