Mathematics ΙΙI

General

Educational goals

The course aims to introduce the students to the basic ideas of discrete mathematics such as basic formal logic, counting techniques, graph theory and their applications in computer science. The main goal of the course is to provide students with a good understanding of the basic theory and some applications of discrete mathematics.

  • Understand the basic concepts of naive set theroy and be able to apply set theoretic operations.Γνωρίζει τις βασικές έννοιες της απλοϊκής θεωρίας συνόλων και να εφαρμόζει πράξεις με αυτά. Understand the concepts of set cardinality and distinguish fininte - infinite, enumerable and non-enumerable sets. Be able to apply the pigeonhole principle in practical problems. Comprehend the concept of binary relations and particularly partial orders, total orders and equivalences.
  • Underastand the syntax and the semantics of the language of Propositional Logic. Be able to establish logical consequenses using the semantic tools of PL. Be able to distinguish tautologies and contradictions.
  • Be able to apply the inductive method in order to establish the validity of arguments dependent on natural numbers.
  • Comprehend the principles and models of combinatorial analysis and be able to employ them in a varierty of real life problems.
  • Realize the connection between sequences and generating functions. Be able to apply generating functions in the solution of combinatorial problems and problems involving linear recursive sequences.
  • Get familiar with graph theory terminology and concepts. and particularly to the ones related to trees. Be able to detect the presence of key features in a graph such as connectivity and Euler/Hamilton cycles, and compute its chromatic number. Apply well known algorithms (Dijkstra, BFS, DFS, Prim, Kruskal) and realize their applications in applications. Comprehend the concepts of tree graph, rooted tree and binary tree and be able to app;y pre-, in-, post-order traversal algorithms in binary trees.
General Skills
  • Work in multidisciplinary environement
  • Development of new research ideas
  • Improvement of open minded, creative and inductive thought

Course Contents

Elements of Set Theory: Introduction, Definition of Sets, Set operations, Powersets, Enumerable – non Enumerable Sets, Cardinality of a Set, Relations and Functions, Equivalence Relations, Partial Order Relations.

Propositional Logic: Propositions – Syntax, Connectives – Truth Tables, Tautology – Contradiction, Tautological Equivalence.

Mathematical Induction: Basic and Strong form of Mathematical Induction.

Combinatorial Analysis: Sum and Product Rules, Permutations, Combinations, Balls and Bins.

Generating Functions:  Ordinary Generating Functions, Properties, Exponential Generating Functions, Application to Combinatorial Analysis.

Recursive Relations: Recursive Sequences and Relations, Solution of Linear Recursive Relations using Generating Functions.

Elements of Graph Theory: Definitions – Terminology, Directed and Undirected Graphs, Vertex Degree , Paths , Connected Graphs, Subgraphs, Special types of Graphs, Isomorphic Graphs, Euler and Hamilton Cycles, Graphs and Matrices, Shortest Path and Dijkstra’s Algorithm, Trees, Rooted Trees, Weighted Trees, Minimum Spanning Tree, Binary Trees.

Teaching Methods - Evaluation

Teaching Method
  • Face to face teaching
Use of ICT means
  • Notes and slides available in electronic form (in greek).
  • Use of asynchronous learning platform (Moodle).
Teaching Organization
Activity Semester workload
Lectures52
Communication/Collaboration108
Self-study20
Total 180
Students evaluation

The final exam consists of 7-8 thought development exercises, on the following subjects:

- Propositional Logic
- Binary Relation
- Pigeonhole Principle
- Induction
- Combinatorics
- Recursive relations
- Generating Functions
- Graph Theory

The above examination scheme is communicated to the students through:

(a) The course web page
(b) The asynchronous learning platform Moodle
(c) Announcements at the begining of the semester and during the lectures.

Recommended Bibliography

Recommended Bibliography through "Eudoxus"
  1. EPP, SUSANNA S., Διακριτά Μαθηματικά με Εφαρμογές, 3η έκδοση, Εκδόσεις Κλειδάριθμος, 2010, ISBN 978-960-461-325-0, [Κωδ. Ευδόξου 13953].
  2. Κατωπόδης Κωνσταντίνος Σπ., Εισαγωγή στα διακριτά μαθηματικά, Εκδότης: Ζήτη Πελαγία & Σια Ι.Κ.Ε., 1η έκδ., 2015, ISBN: 978-960-456-446-0, [Κωδ. Ευδόξου 50658666].
Complementary greek bibliography
  1. LIU C., Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009, ISBN 978-960-524-072-1
  2. ROSEN K., Διακριτά μαθηματικά και εφαρμογές τους, 7η έκδοση, Εκδόσεις Τζιόλα & Υιοι Α.Ε., 2014, ISBN: 978-960-418-394-4.
  3. Κυρούσης Λ.Μ., Μπούρας Χ.Ι., Σπυράκης Π.Γ., Διακριτά μαθηματικά. Τα μαθηματικά της επιστήμης των υπολογιστών, Gutenberg, 1994, ISBN 978-960-01-0661-4.
  4. Αγγελής Ε.Σ.,Μπλέρης Γ.Λ., Διακριτά μαθηματικά, Εκδόσεις Τζιόλα, 2003, ISBN 960-418-009-6.
Complementary international bibliography
  1. EPP, SUSANNA S.: Discrete Mathematics with Applications, Wadsworth, 1990, ISBN 0495391328
  2. GRAHAM, R., KNUTH, D., PATASHNIK, O.: Concrete Mathematics, Addison Wesley, 1994.
  3. ROSEN K.H., Discrete mathematics and its applications. New York: McGraw-Hill, 2012.
  4. GRIMALDI, R.: Discrete and Combinatorial Mathematics. An Applied Introduction, Addison Wesley, 1994.
  5. HALL, M., Jr.: Combinatorial Theory, John Wiley & Sons, 1986.
  6. HARARY, F.: Graph Theory, John Wiley & Sons, 1986.
  7. LIPSCHUTZ, S.: Set Theory, McGraw Hill, 1964.
  8. LIU, C.: Introduction to Combinatorial Mathematics, McGraw Hill, 1968.
  9. LIU, C.: Elements of Discrete Mathematics, McGraw Hill, 1986.
  10. REINGOLD, M., NIERERGELT, J., DEO, N.: Combinatorial Algorithms Theory and Practice, Prentice Hall, 1977.
  11. ROSS, K. A., WRIGTH, C. R. B. : Discrete Mathematics, Prentice Hall, 1992.
  12. TOMESCU, I. And MELTER, R.: Problems in Combinatorial and Graph Theory, John Wiley & Sons, 1985.
  13. WITALA, S, A.: Discrete Mathematics. A Unified Approach, McGraw Hill, 1987.