3612 Ειδικά Θέματα Διακριτών Μαθηματικών

Μάθημα Επιλογής, Η’ εξάμηνο, 6 μονάδες ECTS

Διδάσκων: Καθηγητής Α’ βαθμίδας Παναγιώτης Κατερίνης

URL: https://eclass.aueb.gr/courses/INF238/

Περιεχόμενο

Θεωρία γραφημάτων: γραφήματα και υπογραφήματα. Γενικά περί δέντρων. Το πρόβλημα του βέλτιστου επικαλυπτικού δέντρου. Βέλτιστα επικαλυπτικά δέντρα και βέλτιστα μονοπάτια. Απαρίθμηση δέντρων. Δέντρα με ρίζες. Κώδικες προθέματος και αλγόριθμος του Huffman. Μονοπάτια και αποστάσεις σε γραφήματα. Εκκεντρικότητα κορυφών και κέντρο γραφήματος. Συνεκτικότητα γραφημάτων. Κατασκευή αξιόπιστων δικτύων με ελάχιστο αριθμό συνδέσεων. Κύκλοι του Hamilton. Το πρόβλημα του περιοδεύοντος πωλητή. Ίχνη του Euler. Το πρόβλημα του Κινέζου ταχυδρόμου. Σχεδιασμοί: γενικά περί σχεδιασμών. Το Θεώρημα του Fisher. Συμμετρικοί σχεδιασμοί. Σχεδιασμοί και κώδικες. Αλγεβρικά συστήματα: Ομάδες. Υποομάδες. Γεννήτορες και υπολογισμός δυνάμεων. Σύμπλοκα και το θεώρημα του Lagrange. Κώδικες και κωδικές ομάδες. Ισομορφισμοί και αυτομορφισμοί. Ομοιομορφισμοί και κανονικές υποομάδες. Δακτύλιοι.

Μαθησιακά Αποτελέσματα

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

  • Να περιγράφουν και να χειρίζονται τις θεμελιώδεις έννοιες και θεωρήματα των επιλεγμένων γνωστικών περιοχών των Διακριτών Μαθηματικών (Θεωρία Γραφημάτων, Θεωρία Σχεδιασμών, Θεωρία Κωδίκων).
  • Να συνδυάζουν τα βασικά συστατικά των άνω γνωστικών περιοχών προκειμένου να λύνουν πολυπλοκότερα μαθηματικά προβλήματα.
  • Να μοντελοποιούν και να επιλύουν προβλήματα που εμφανίζονται στην Πληροφορική με χρήση των άνω γνωστικών αντικειμένων των Διακριτών Μαθηματικών.

Προαπαιτούμενα Μαθήματα

Για να εγγραφεί στο μάθημα, ο φοιτητής πρέπει να έχει εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο στο μάθημα «Διακριτά Μαθηματικά».

Συνιστώμενη Βιβλιογραφία

  • Aspects of Combinatorics, V. Bryant, Cambridge University Press, 1993.
  • Graph Theory with Applications, J. A. Bondy, U. S. R. Murty, North Holland, 1976.

Διδακτικές και Μαθησιακές Μέθοδοι

Διαλέξεις (2 διαλέξεις των 2 ωρών εβδομαδιαίως).

Μέθοδοι Αξιολόγησης/Βαθμολόγησης

Ο τελικός βαθμός ισούται με τον βαθμό της τελικής εξέτασης.