MEM-241 Διακριτά Μαθηματικά

Κατεύθυνση	Μαθηματικών	Εφαρμοσμένων Μαθηματικών
Είδος	Επιλογής Κορμού (Κ4)	Επιλογής Κορμού
Έτος/εξάμηνο	3ο / Εαρινό
ECTS/Διδακτικές μονάδες	8 / 4
Ώρες διαλέξεων/εργαστηρίων	4 / 0
Προαπαιτούμενα μαθήματα	Κανένα
Συνιστώμενα μαθήματα	MEM-103
Μέθοδος διδασκαλίας	Διαλέξεις, εργαστήριο προβλημάτων
Μέθοδος αξιολόγησης	Τελική εξέταση, εξετάσεις προόδου

Μετά την επιτυχή ολοκλήρωση του μαθήματος οι φοιτητές:

Θα είναι εξοικειωμένοι με τις βασικές αρχές και θα μπορούν να χρησιμοποιούν βασικές και προχωρημένες μεθόδους συνδυαστικής απαρίθμησης.
Θα είναι εξοικειωμένοι με την έννοια του γραφήματος και βασικών σχετικών εννοιών, όπως η συνεκτικότητα, ο βαθμός, τα μονοπάτια Hamilton και Euler, ο χρωματικός αριθμός.
Θα γνωρίζουν ειδικές κατηγορίες γραφημάτων, όπως τα διμερή γραφήματα και τα δένδρα.
Θα γνωρίζουν βασικά υπολογιστικά προβλήματα σε γραφήματα, όπως αυτά της εύρεσης ελάχιστων μονοπατιών, της εύρεσης ελάχιστων συνδετικών δένδρων ή της διάσχισης γραφημάτων κατά βάθος και κατά πλάτος.

Βασικές αρχές απαρίθμησης:
- Αρχή γινομένου για ανεξάρτητες επιλογές (πλήθος υποσυνόλων ενός πεπερασμένου συνόλου, πλήθος συναρτήσεων με πεπερασμένα σύνολα ορσμού και τιμών).
- Αρχή γινομένου για ημι-ανεξάρτητες επιλογές (διατεταγμένες επιλογές, μεταθέσεις, μη διατεταγμένες επιλογές, συνδυασμοί)
Προχωρημένες αρχές απαρίθμησης:
- Διαμερίσεις, συνδυασμοί με επανάθεση.
- Πολυωνυμικοί συντελεστές, Δυωνυμικό Θεώρημα.
Γραφήματα:
- Ορισμοί: γράφημα, υπογράφημα, δένδρο, συνεκτικότητα, αποστάσεις, ισομορφισμός γραφημάτων.
- Αλγόριθμοί για ελάχιστα συνδετικά δένδρα και για εύρεση ελάχιστων μονοπατιών.
- Διμερή γραφήματα, ταιριάσματα σε διμερή γραφήματα, μέγιστα ταιριάσματα.
- Μονοπάτια Euler και Hamilton.
- Χρωματισμοί γραφημάτων