Jump to navigation Jump to search
컴퓨터 과학에 필요한 논리 이론 및 조합적 분석 방법을 배우고, 이산 구조와 관련된 효율적인 알고리즘을 구성하는 법을 배운다.
- Logic and set theory: Syntax and semantics of propositional and first-order logic, Normal forms (CNF, DNF), Semigroups & Monoids, Lattices, Relations, partial orders, and scheduling
- Combinatorics: Counting techniques, Permutation groups, Partition, Permanent, Generating functions
- Graph theory: Graph, tree, Colorings and matching, Breadth-first and depth-first searches, Algorithms, and applications of algebraic structures
- Modeling computation: Elements of computability theory and computational complexity, Discussion of the P=NP problem, Introduction to the Gödel completeness and incompleteness theorems.
- Coding and information theory: Error-detecting and error-correcting code: Hamming codes, Huffman codes, Entropy and Shannon’s first theorem, Channel capacity, Shannon’s main theorem