Discrete Mathematics - Overview
Discrete Mathematics - Overview
Text : Discrete Mathematics and Its Application(8th ed.)
by Kenneth H. Rosen
University of Seoul
Department of Mathematics
Jaechul Sung
(jcsung@[Link])
Dept. of Mathematics, Jaechul Sung
Discrete Mathematics - Overview
What is this class about?
Discrete : composed of distinct, separable parts
- discrete : separate, distinct
- discrete vs. continuous
Structures : objects built up from simpler objects according to some
definite pattern
Discrete Mathematics - the study of discrete, mathematical objects
and structures.
Four famous problems in discrete mathematics
- Magic card problem
- Pigeonhole principle
- Hanoi tower problem
- Lattice polygon problem
Dept. of Mathematics, Jaechul Sung 2
Discrete Mathematics - Overview
What we will study?
Discrete structures
Propositions, Predicates, Proofs, Sets, Functions, Algorithms,
Integers, Summations, Sequences, Strings, Permutations,
Combinations, Relations, Graphs, Trees, Logic Circuits,
Automata . . .
Relations between structures
Some notations
p pq pq pq pq x P ( x)
x P( x) {a1 , , an } Z, N, R {x | P( x)} xS
n
S T |S| A B A A i
i 1
n
f :A B f 1 ( x) f g x a
S
a
i 1
i
O, , min, max a /| b gcd, lcm mod a b (mod m)
n
( a k a0 ) b [aij ] AT B
AΟ A[ n ]
r
C (n; n1 , , nm ) p( E | F ) R [a ]R deg (v)
Dept. of Mathematics, Jaechul Sung 3
Discrete Mathematics - Overview
Why study discrete mathematics?
The basis of all of digital information
processing is: Discrete manipulations of
discrete structures represented in memory.
It’s the basic language and conceptual
foundation for all of computer science.
Discrete math concepts are also widely used
throughout math, science, engineering,
economics, biology, etc., …
A generally useful tool for rational thought!
Dept. of Mathematics, Jaechul Sung 4
Discrete Mathematics - Overview
Discrete math in computer science
Advance algorithms and data structures
Programming language complier & interpreters
Computer networks
Operating systems
Computer architecture
Data management systems
Cryptography
Error correcting codes
Graphic &animation algorithms, game engines, ...
Dept. of Mathematics, Jaechul Sung 5
Discrete Mathematics - Overview
Course outlines
This course (2/1)
Chap 1. The Foundations : Logics and Proofs
Chap 2. Basic Structures : Sets, Functions, Sequences, Sums, and Matrices
Chap 3. Algorithms
Chap 4. Number Theory and Cryptography
Chap 5. Induction and Recursion
Chap 6. Counting
Chap 7. Discrete Probability
Chap 8. Advanced Counting Techniques
Chap 9. Relations
수학과컴퓨터 (2/2) 수학캡스톤디자인 (3/1 or 3/2)
- C/PYTHON 언어 기초 배우기 - 알고리즘/자료구조 기초
- PYTHON을 활용한 알고리즘 실습 - 코딩테스트 기초 이론 실습
Dept. of Mathematics, Jaechul Sung 6
Discrete Mathematics - Overview
Course objectives
Upon completion of this course, the student
should be able to:
Check validity of simple logical arguments (proofs).
Check the correctness of simple algorithms.
Creatively construct simple instances of valid
logical arguments and correct algorithms.
Describe the definitions and properties of a variety
of specific types of discrete structures.
Correctly read, represent and analyze various types
of discrete structures using standard notations.
Dept. of Mathematics, Jaechul Sung 7
Discrete Mathematics - Overview
Q&A
Course materials are available at [Link] (온라인강의실)
Dept. of Mathematics, Jaechul Sung 8