SITE MAP | ΕΛΛΗΝΙΚΑ | ENGLISH Search:
###### Discrete Mathematics II

INSTRUCTOR:
COURSE_ID:
MYY302
WEEKLY HOURS:
4, 1, 0
SEMESTER:
3
COURSE UNITS:
5
ECTS CREDITS:
6.00
YEAR 2018/2019:
YES
PREREQUISITE:
-
DESCRIPTION:

Elements of number theory: Divisibility. Primality. Sieve of Eratosthenes. b-ary representations of numbers. Divisibility and primality criteria. Greatest common divisor and minimum common multiplier. Euclid’s algorithm. Chinese remainder theorem.

Graph theory: Degree, subgraph, handshaking lemma, special graphs, morphisms. Representation of graphs. Cut sets and separators, edge/vertex connectivity, Menger’s theorem. Trees, properties and characterization, counting, special trees (e.g., m-ary trees), pre-/in/post-order traversals. Breadth/Depth first search of a grap, minimum spanning trees. Lengths and distances in graphs, shortest paths, cycles of negative length. Euler circuits and trails. Hamilton cycles and paths. Planarity, Euler’s formula, Kuratowski’s theorem.

Recursive relations and recursively defined discrete structures: Sequences. Introduction to sums, computing techniques of sums. Recursions. Homogeneous / non-homogeneous linear recursive equations. «Divide and Conquer» algorithm and recurrence relations.

Generating functions: Ordinary and exponential generating functions of sequences. Generalized binomial theorem. Usage of generating functions as counting tools, for solving recurrence relationsand for proving identities.

First-order Logic: Laws of first-order logic. Usage of quantifiers. Tarski’s truth. Limitations of first-order logic.

Finite automata: Recognition of a language by an automaton, automaton simplification, deterministic / non-deterministic finite automata and their equivalence.
 ©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA created by data|SCIENCE ©2010 DEPARTMENT OF style="font-size: 0.1px;">COMPUTER SCIENCE style="font-size: 0.1px;">& ENGINEERING style="font-size: 0.1px;">UNIVERSITY style="font-size: 0.1px;">OF style="font-size: 0.1px;">IOANNINA