Αλγοριθμική Θεωρία Γραφημάτων (ΠΛ4)

Περιγράμματα Μεταπτυχιακών Μαθημάτων - Τμήμα Μαθηματικών

Γενικά

Σχολή	Σχολή Θετικών Επιστημών
Τμήμα	Τμήμα Μαθηματικών
Επίπεδο Σπουδών	Μεταπτυχιακό
Κωδικός Μαθήματος	ΠΛ4Α
Εξάμηνο	2
Τίτλος Μαθήματος	ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ
Αυτοτελείς Διδακτικές Δραστηριότητες	Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 7.5)
Τύπος Μαθήματος	Επιλογής
Προαπαιτούμενα Μαθήματα	Απαραίτητες γνώσεις από 641 - Σχεδίαση και Ανάλυση Αλγορίθμων
Γλώσσα Διδασκαλίας και Εξετάσεων	Ελληνική
Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus	Ναι (στην Αγγλική γλώσσα)
Ηλεκτρονική Σελίδα Μαθήματος (URL)	Δείτε το eCourse, το Σύστημα Διαχείρισης Μάθησης του Πανεπιστημίου Ιωαννίνων.

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

Μαθησιακά Αποτελέσματα	Ο κύριος σκοπός του μαθήματος είναι η εισαγωγή σε θεμελιώδεις αλγοριθμικές τεχνικές σχετικές με προβλήματα βελτιστοποίησης και μοντελοποίησης σε γραφήματα. Αλγοριθμική θεωρία γραφημάτων και θεμελιώδη γραφοθεωρητικά θέματα. Σχεδίαση αποτελεσματικών αλγορίθμων και ανάλυση πολυπλοκότητας παραμετροποιημένων αλγορίθμων για ΝΡ-πλήρη προβλήματα. Κλάσεις γραφημάτων: Τέλεια γραφήματα. Τριγωνικά γραφήματα. Μεταβατικά γραφήματα. Διαχωρίσιμα γραφήματα. Μεταθετικά γραφήματα. Γραφήματα διαστημάτων. Συμπληρωματικά παραγόμενα γραφήματα και κατωφλικά γραφήματα. Αλγοριθμικά θέματα σχετικά με γραφοθεωρητικές παραμέτρους. Στο μάθημα περιλαμβάνονται ατομικές ασκήσεις, περιληπτική συγγραφή και παρουσίαση σχετικών ερευνητικών εργασιών. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση: να κατανοήσουν τη θεωρία γραφημάτων, να επεκτείνουν την αλγοριθμική τους σκέψη σε προβλήματα σχετικά με τη θεωρία γραφημάτων, και να αντιλαμβάνονται δύσκολα επιλύσιμα προβλήματα σε κλάσεις γραφημάτων.
Γενικές Ικανότητες	Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών Αυτόνομη εργασία Εργασία σε διεπιστημονικό περιβάλλον

Περιεχόμενο Μαθήματος

Βασικά στοιχεία Θεωρίας Γραφημάτων
Αλγοριθμικά προβλήματα συνδυαστικής σε γραφήματα
Κλάσεις πολυπλοκότητας και παραμετροποιημένου-χρόνου αλγόριθμοι
Τριγωνικά γραφήματα. Μεταβατικά γραφήματα. Διαχωρίσιμα γραφήματα.
Μεταθετικά γραφήματα. Γραφήματα διαστημάτων. Συμπληρωματικά παραγόμενα γραφήματα και κατωφλικά γραφήματα.
Αλγοριθμικά θέματα σχετικά με γραφοθεωρητικές παραμέτρους.

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παράδοσης

Στην τάξη

Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών

Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-class

Οργάνωση Διδασκαλίας

Δραστηριότητα	Φόρτος Εργασίας Εξαμήνου
Διαλέξεις	39
Αυτοτελής Μελέτη	78
Επίλυση Ασκήσεων - Εργασίες	70.5
Σύνολο Μαθήματος	187.5

Αξιολόγηση Φοιτητών

Ατομικές Εργασίες (50%)
Συγγραφή Περιληπτικών Εργασιών (20%)
Παρουσιάσεις (30%)

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

Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press, 1990. (επίσης μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης)
Δομές δεδομένων, αλγόριθμοι και εφαρμογές c++, Sahnii Sartaj, Εκδόσεις α. Τζιόλα
Αλγόριθμοι σε C++, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
Αλγοριθμοι σε C, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
Mark Allen Weiss, Data Structures & Algorithm Analysis in Java, Addison-Wesley
Clifford A. Shaffer, Data Structures and Algorithm Analysis, ebook, http://people.cs.vt.edu/shaffer/Book/
A. Aho, J. Hopcroft, J. Ullman, (1983). Data Structures and Algorithms, Addison-Wesley.
Baase, S., Computer Algorithms - Introduction to Design and Analysis, Second Edition, , Addison Wesley, Reading, Massachusetts, 1988.
Knuth, D., The Art of Computer Programming - Vol. 1 Fundamental Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
Knuth, D., The Art of Computer Programming - Vol. 2 SemiNumerical Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
Knuth, D., The Art of Computer Programming - Vol. 3 Sorting and Searching, Addison Wesley, Reading, Massachusetts, 1973.