과정 안내
알고리즘의 기초 (2017)
- 알고리즘을 개발하기 위해서 이용되는 여러 가지 기법을 소개한다.
- 본 과목에서 다루는 주요 내용은, 주어진 알고리즘(프로그램)의 수행시간과 사용 공간의 계산, incremental 알고리즘, divide-and-conquer 알고리즘,
dynamic programming 알고리즘 그리고 greedy 알고리즘에 관하여 공부한다. Graph에 관한 이론과 알고리즘에 대해서 공부한 후에 마지막으로 NP-Complete과
Approximate 알고리즘에 대해서 공부한다.
-
강좌 정보 및 소개
차시
차시명
학습 모듈
1
Introduction to Algorithms
Introduction to Algorithms
Growth of Functions
2
Divide And Conquer
Solving Recurrence Equations
Maximum Subarray Problem
3
Heapsort
Heapsort 1
Heapsort 2
Heapsort 3
4
Quicksort
Quicksort 1
Analysis Of Quick Sort Algorithm
5
Sorting In Linear Time
Sorting In Linear Time 1
Sorting In Linear Time 2
6
Median And Order Statistics
Median And Order Statistics 1
Median And Order Statistics 2
7
Dynamic Programming I
Rod Cutting 1
Rod Cutting 2
Rod Cutting 3
8
Dynamic Programming II
Matrix Multiplication 1
Matrix Multiplication 2
Matrix Multiplication 3
9
Dynamic Programming III
Optimal Substructure Property
Longest Common Sequence 1
Longest Common Sequence 2
10
Dynamic Programming IV
Optimal Binary Search Tree 1
Optimal Binary Search Tree 2
Optimal Binary Search Tree 3
11
Greedy Algorithms I
Activity Selection 1
Activity Selection 2
12
Greedy Algorithms II
Knapsack Problem
Huffman Codes
13
Elementary Graph Algorithms I
Representation Of A Graph
Breadth-First Search 1
Breadth-First Search 2
14
Elementary Graph Algorithms II
Depth-First Search
Topological Sort
Strongly Connected Components
15
Minimum Spanning Trees
Data Structures for Disjoint sets
Minimum Spanning Trees 1
Minimum Spanning Trees 2
16
Single Source Shortest Paths I
Single Source Shortest Paths
Bellman-Ford Algorithm
17
Single Source Shortest Paths II
DAG Shortest Path Algorithm
Dijkstra's Algorithm 1
Dijkstra's Algorithm 2
18
All Pair Shortest Paths I
All Pair Shortest Paths
A Dynamic Programming Algorithm Similar to Repeated Matrix Multiplication
19
All Pair Shortest Paths II
Floyd-Warshall Algorithm
Johnson's Algorithm
20
NP-Completeness I
NP-Completeness 1
NP-Completeness 2
21
NP-Completeness II
NP-Completeness 3
NP-Completeness 4
22
Approximation Algorithms
Approximation Algorithms 1
Approximation Algorithms 2
Approximation Algorithms 3
-
교수 정보
-
교수진 소개
- 과정명: 알고리즘의 기초
- 교수(소속): 서울대학교 공과대학 전기정보공학부
- 학력: 서울대학교 전기공학 (학사)
미국 메릴랜드 주립대학교(College Park) 컴퓨터과학 (석사, 박사) - 주요 경력: IBM Almaden Research Center
Bell Laboratories
KAIST 전산학과 조교수
- 강좌코드 : 2019_80_C_2017_2_SKS_2019_2
- 과정 : 알고리즘의 기초
- 주수 : 22
- 수강가능수 : 100000
- 학점 : 0
- 언어 : 한국어 (ko)
- 태그 :