Ώρες διδασκαλίας: Τρίτη 9:00-11:00 Αίθουσα Ζ.
Πέμπτη 9:00-11:00, Αίθουσα Ζ.
Διδάσκων: Γ. Καραγιώργος
Γραφείο:
Ι21 (’ Τομέας)
E-mail:
greg@di.uoa.gr
Αποτελέσματα εξέτασης Σεπτεμβρίου
[.ps]
1η ’σκηση (Παράδοση: 30/11/2004 Την ώρα του μαθήματος ): Το πρώτο σύνολο ασκήσεων βρίσκεται στο [.ps]
Για ερωτήσεις σχετικές με την άσκηση 1 μπορείτε να απευθύνεστε στον Χρίστο Σόφη:
E-mail:
ch.sofis@di.uoa.gr
2η ’σκηση (Παράδοση: 13/01/2005 Την ώρα του μαθήματος ): Το δεύτερο σύνολο ασκήσεων βρίσκεται στο [.ps]
(Παράδοση περίληψης άρθρου: 21/12/2004 ή 11/01/2005 Την ώρα του μαθήματος )
Ερωτηματολόγιο αξιολόγησης του μαθήματος
(Παράδοση: 11/01/2005 ή 13/01/2005 Την ώρα του μαθήματος ):
Παρακαλώ να συμπληρώσετε το ερωτηματολόγιο που βρίσκεται στο [.ps]
Το βιβλίο διατίθεται από τις
εκδόσεις Νέων Τεχνολογιών, Στουρνάρα 49Α, 3ος όροφος, Δευτέρα έως Παρασκευή και ώρα 9:00-17:00
Σύγγραμμα:
ΤΙΤΛΟΣ: " ΜΑΘΗΜΑΤΑ θΕΩΡΙΑΣ ΓΡΑΦΩΝ, Θεμελιώσεις-Αλγόριθμοι-Εφαρμογές ", Γ. Μανωλόπουλος
’λλες πηγές είναι τα παρακάτω βιβλία:
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein "Introduction to algoritmhs", 2nd Edition, MIT-Press, 2001. :
Chapter VI - Graphs Algorithms
και επιπλέον τα εισαγωγικά στις σελίδες :1080 - 1093
Β. Ζησιμόπουλος, "Σημειώσεις-Θεωρία Γράφων, 2003-2004"
Βασικοί παράμετροι σε γράφους - προβλήματα που μπορούν να μοντελοποιηθούν με τη βοήθεια γράφων.
προσανατολισμένοι γράφοι - απλοί γράφοι, ειδικοί γράφοι.
εφαρμογές.
υπογράφοι, παράγων γράφος, ισομορφισμοί γράφων.
αλυσίδες, κύκλοι, μονοπάτια, κλειστά μονοπάτια, συνεκτικότητα.
κύκλοι Euler, κύκλοι Hamilton.
αναπαράσταση γράφων, πίνακας γειτνίασης, πίνακας πρόσπτωσης, λίστες γειτνίασης.
Δένδρα και κατευθυνόμενα δένδρα.
δένδρα επικάλυψης ελαχίστου (μεγίστου) κόστους, θεώρημα βελτιστοποίησης
ο αλγόριθμος του Prim, ο αλγόριθμος του Kruskal.
πολυπλοκότητα, έλεγχος ακυκλισμού.
εφαρμογές.
κάτω φράγμα για το πρόβλημα του πλανόδιου πωλητή.
Αλγόριθμοι διάσχισης.
γενικός αλγόριθμος.
κατά πλάτος, κατά βάθος, πολυπλοκότητα.
Αλγόριθμοι βελτίστων μονοπατιών.
αλγόριθμος Dijkstra, αλγόριθμος Bellman.
γράφοι χωριζόμενοι σε επίπεδα και αλγόριθμος Bellman, αλγόριθμος Floyd.
Ροές σε δίκτυα.
μέγιστη ροή, θεώρημα max flow-min cut, αλγόριθμος μεγίστης ροής.
δίκτυα με άνω και κάτω φράγματα χωρητικότητας.
Διασχίσεις Euler.
συνθήκες ύπαρξης, κατευθυνόμενη και μη κατευθυνόμενη περίπτωση.
πολυπλοκότητα αλγορίθμων.
Το πρόβλημα του κινέζου ταχυδρόμου.
κατευθυνόμενη και μη κατευθυνόμενη περίπτωση, πολυπλοκότητα αλγορίθμων.
Αλγεβρική θεωρία γράφων.
Εισαγωγή, Ορισμοί, Βασικές φασματικές ιδιότητες των γράφων
Φάσματα Expander graphs, Πίνακες γειτνίασης γράφων, Ιδιοτιμές και οι σχέσεις με τυχαίους περιπάτους.
Προβλήματα matching.
Το πρόβλημα της μεταφοράς.
Προβλήματα NP-complete.
Το πρόβλημα του μέγιστου ανεξαρτήτου συνόλου σ'ένα γράφο.
Το πρόβλημα ελαχίστης επικάλυψης των πλευρών σ'ένα γράφο.
Το πρόβλημα χρωματισμού.
Θα έχουμε 2 σύνολα ασκήσεων (5% το καθένα), ένα άρθρο για παρουσίαση+3 σελίδες περίληψη (10%) και ένα τελικό διαγώνισμα (80%). Για να περάσετε όμως το μάθημα πρέπει να έχετε τουλάχιστον 4 στο τελικό διαγώνισμα.