Παρουσίαση/Προβολή
Θεωρία Γραφημάτων και Εφαρμογές
(CEID1130) - Σταύρος Κοσμαδάκης
Περιγραφή Μαθήματος
ΣΗΜΑΝΤΙΚΗ ΑΝΑΚΟΙΝΩΣΗ Το μάθημα θα εξεταστεί, το 2023 - 24, με ανοιχτά βιβλία και σημειώσεις. Οι φοιτητές θα μπορούν να έχουν μαζύ τους ΜΟΝΟ τα βιβλία και τις σημειώσεις του μαθήματος, και δικές τους χειρόγραφες σημειώσεις.
Το μάθημα αποτελεί εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων. Δίνεται έμφαση στην περιγραφή και χρήση των εννοιών με μαθηματικά ακριβή τρόπο. Εξετάζεται η εφαρμογή της θεωρίας (i) στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και (ii) στην επαλήθευση της ορθότητας αυτών των αλγορίθμων. Καλύπτονται: Συνεκτικότητα, ισχυρή συνεκτικότητα, δισυνεκτικότητα, επαγωγή και αναδρομή για γραφήματα, βασική θεωρία δέντρων, στοιχειώδεις κύκλοι.
Το κύριο σύγγραμμα του μαθήματος είναι οι διδακτικές σημειώσεις: Εισαγωγή στα Γραφήματα, Θεωρία - Ασκήσεις, του Σ. Κοσμαδάκη. Όλη η απαιτούμενη ύλη, καθώς και η ορολογία που χρησιμοποιείται στις παραδόσεις, καλύπτεται στις διδακτικές σημειώσεις.
Το δεύτερο σύγγραμμα είναι το βιβλίο: Διακριτά μαθηματικά και εφαρμογές τους, 8η Έκδοση, του Kenneth H. Rosen. Υπάρχει στον Εύδοξο. Περιέχει επιπρόσθετα παραδείγματα και ασκήσεις, αλλά μόνο για ένα μέρος της απαιτούμενης ύλης. Μπορεί να χρησιμοποιηθεί για εμπέδωση των μαθηματικών δεξιοτήτων που χρειάζονται στο μάθημα.
Ημερομηνία δημιουργίας
Παρασκευή, 16 Σεπτεμβρίου 2016
-
Διδακτικό Υλικό
Στο πεδίο "Έγγραφα" καταχωρούνται:
(i) Τα συγγράμματα του μαθήματος.
(ii) Συμπληρωματικό υλικό (άλλα βιβλία, σημειώσεις κοκ), που μπορεί να χρησιμοποιηθεί ως επιπλέον βοήθημα - για ορισμένα από τα θέματα που καλύπτει το μάθημα.
(iii) Μια σειρά από "Συνοπτικά Μαθήματα" και "Προτεινόμενες Ασκήσεις".
Τα "Συνοπτικά Μαθήματα" είναι καταγραφές παραδόσεων του μαθήματος - η σειρά τους δεν είναι χρονολογική. Περιέχουν αναλυτικές λεπτομέρειες της ύλης που έχει παρουσιαστεί στις παραδόσεις, μαζύ με επιπλέον παραδείγματα, παρατηρήσεις κλπ. Δίνονται παραπομπές σε σχετικά μέρη του άλλου διδακτικό υλικού, για επιπλέον μελέτη.
Οι "Προτεινόμενες Ασκήσεις" είναι ενδεικτικές του αναμενόμενου επιπέδου κατανόησης, της σχετικής ύλης.