ΘΕΩΡΙΑ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ ΓΡΑΦΩΝ - Εαρινό εξάμηνο 2016-17

Σύμφωνα με το πρόγραμμα οι παραδόσεις του μαθήματος θα γίνονται κάθε Τρίτη 12:00-14:00 και Πέμπτη 9:00-11:00 στην αίθουσα Α. Το μάθημα αυτό έρχεται ως συνέχεια των ήδη διδαχθέντων μαθημάτων: «Διακριτά Μαθηματικά», «Δομές Δεδομένων» και «Αλγόριθμοι» (παλαιότερα «Σχεδίαση και Ανάλυση Αλγορίθμων»). Η προσέγγιση του αντικειμένου είναι κυρίως αλγοριθμική αλλά η απόκτηση γνώσεων μερικών βασικών μαθηματικών θεμελιώσεων είναι απαραίτητη. Η παρούσα σελίδα αποτελεί ένα ημερολόγιο σχετικά με την πρόοδο του μαθήματος, το οποίο προοδευτικά θα ενημερώνεται. Το περιεχόμενο των διαλέξεων αντιστοιχεί περίπου σε κεφάλαια του ακολουθούμενου διδακτικού βοηθήματος. Στη σελίδα αυτή θα αναρτώνται σταδιακά νέες εκδόσεις των διαφανειών. Από την περσινή σελίδα (εδώ) είναι διαθέσιμες οι παλαιότερες εκδόσεις των διαφανειών. Επίσης, να προσεχθεί το ηλεκτρονικό βιβλίο "Αλγοριθμική Θεωρία Γραφημάτων", το οποίο έχει εκδοθεί από το πρόγραμμα Κάλλιπος και είναι ελεύθερα διαθέσιμο εδώ. Συνιστάται η μελέτη και αυτού του υλικού σε συνδυασμό με το κύριο σύγγραμα (το πρώτο της βιβλιογραφίας που ακολουθεί), το οποίο διατίθεται από τον Εύδοξο.

Η αξιολόγηση θα γίνει με την εξέταση του Ιουνίου-Σεπτεμβρίου. Συμπληρωματικά, για την πριμοδότηση όσων έρχονται στις παραδόσεις, θα δίνονται μικροασκήσεις κατά τη διάρκεια του μαθήματος με προθεσμία ωρών. Το bonus από την επίλυση αυτών των μικροασκήσεων μπορεί να φτάσει τη 1 μονάδα ή και περισσότερο (θα εξαρτηθεί στην πορεία, πάντως κανείς δεν θα χάσει). Απαιτείται εντός της ίδιας ημέρας του μαθήματος να αποστέλεται αρχείο pdf μίας (1) σελίδας αυστηρά, όπου επάνω να αναφέρεται ονοματεπώνυμο και ΑΕΜ. Εδώ η βαθμολογία των μικροασκήσεων.

Για κάθε ερώτηση απευθύνεστε στο διδάσκοντα καθ. Γιάννη Μανωλόπουλο (manolopo@csd.auth.gr). Για λόγους αρχής, δεν πρόκειται να δοθούν περαιτέρω εξηγήσεις σχετικά με την ύλη είτε δημοσίως (προφορικά ή με ανακοίνωση) είτε ιδιωτικώς με email κλπ.

Τα αποτελέσματα Ιουνίου εδώ.

Τα αποτελέσματα Σεπτεμβρίου εδώ.

Πρόγραμμα διαλέξεων

• Φεβ.14. Διάλεξη 1η. Τι είναι η Θεωρία Γράφων (slides).
• Φεβ.16. Διάλεξη 2η. Εισαγωγή-Ορισμοί (slides).
• Φεβ.21. Διάλεξη 3η. Εισαγωγή-Πράξεις (slides).
• Φεβ.28. Αργία
• Μάρ.2. Διάλεξη 4η. Αποστάσεις (slides).
• Μάρ.7. Διάλεξη 5η. Κεντρικότητα (slides).
• Μάρ.9. Διάλεξη 6η. Κεντρικότητα-Συγκεντρωτισμός.
• Μάρ.14. Διάλεξη 7η. Συντομότερα μονοπάτια (slides).
• Μάρ.16. Διάλεξη 8η. Συντομότερα μονοπάτια.
• Μάρ.21. Διάλεξη 9η. Euler (slides).
• Μάρ.23. Διάλεξη 10η. Euler. Κινέζος ταχυδρόμος.
• Μάρ.30. Διάλεξη 11η. Hamilton (slides).
• Απρ.6. Διάλεξη 12η. Περιοδεύων πωλητής (slides).
• Απρ.25. Διάλεξη 13η. Περιοδεύων πωλητής.
• Απρ.27. Διάλεξη 14η. Δένδρα (slides).
• Μάι.2. Διάλεξη 15η. Ελάχιστα Ζευγνύοντα Δένδρα.
• Μάι.4. Διάλεξη 16η. Συνδεσμικότητα (slides).
• Μάι.9. Διάλεξη 17η. Συνδεσμικότητα.
• Μάι.11. Διάλεξη 18η. Επιπεδικότητα (slides).
• Μάι.16. Διάλεξη 19η. Επιπεδικότητα.
• Μάι.18. Διάλεξη 20η. Αλγόριθμοι Επιπεδικότητας (slides).
• Μάι.23. Διάλεξη 21η. Χρωματισμός (slides).
• Μάι.25. Διάλεξη 22η. Χρωματισμός.
• Μάι.30. Διάλεξη 23η. Αντιστοιχίσεις και Καλύμματα (slides).
• Ιούν.1. Διάλεξη 24η. Αντιστοιχίσεις και Καλύμματα.

Βιβλιογραφία

• Μανωλόπουλος, Παπαδόπουλος, Τσίχλας:“Θεωρία και Αλγόριθμοι Γράφων”, Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 2014. Παροράματα.
• Νικολόπουλος, Γεωργιάδης, Παληός: “Αλγοριθμική Θεωρία Γράφων”, Κάλλιπος, Αθήνα, 2016.
• Τσίχλας, Γούναρης, Μανωλόπουλος: “Σχεδίαση και Ανάλυση Αλγορίθμων”, Κάλλιπος, 2016 (εδώ διαθέσιμο στον παγκόσμιο ιστό).
• Μανωλόπουλος: “Μαθήματα Θεωρίας Γράφων: Θεμελιώσεις-Αλγόριθμοι-Εφαρμογές”, Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 1996.
• Gross, Yellen: “Graph Theory and its Applications”, 2^nd edition, CRC Press, 2006.
• Gross, Yellen: “Handbook of Graph Theory”, CRC Press, 2003.
• www.graphtheory.com

Ενημέρωση 3/6/2017