이산수학

From Course@DGIST
Jump to navigation Jump to search
SE223 이산수학
과목번호 SE223
학점/이론시수/실습시수 3/3/0
교과구분 교선필수
이학/공학 이-공
대분류 기초과학
소분류 수학
최초개설연도
교수자
개설학년 3
개설학기 1
교재

[[file:|100px]]

선수과목

개요

컴퓨터 과학에 필요한 논리 이론 및 조합적 분석 방법을 배우고, 이산 구조와 관련된 효율적인 알고리즘을 구성하는 법을 배운다.

주차별계획

  • 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

평가방법

기타정보