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

Από Wiki Τμήματος Μαθηματικών

Γενικά

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

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

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

Στο μάθημα περιλαμβάνονται ατομικές ασκήσεις, περιληπτική συγγραφή και παρουσίαση σχετικών ερευνητικών εργασιών. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:

  • να κατανοήσουν τη θεωρία γραφημάτων,
  • να επεκτείνουν την αλγοριθμική τους σκέψη σε προβλήματα σχετικά με τη θεωρία γραφημάτων, και
  • να αντιλαμβάνονται δύσκολα επιλύσιμα προβλήματα σε κλάσεις γραφημάτων.
Γενικές Ικανότητες
  • Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
  • Αυτόνομη εργασία
  • Εργασία σε διεπιστημονικό περιβάλλον

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

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

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

Τρόπος Παράδοσης Στην τάξη
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-class
Οργάνωση Διδασκαλίας
Δραστηριότητα Φόρτος Εργασίας Εξαμήνου
Διαλέξεις 39
Αυτοτελής Μελέτη 78
Επίλυση Ασκήσεων - Εργασίες 70.5
Σύνολο Μαθήματος 187.5
Αξιολόγηση Φοιτητών
  • Ατομικές Εργασίες (50%)
  • Συγγραφή Περιληπτικών Εργασιών (20%)
  • Παρουσιάσεις (30%)

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

  • M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, NORTH-HOLLAND, 2004
  • A. Brandstädt, J. Spinrad, and V. Lee, Graph Classes: A Survey, SIAM Monographs on Discrete Math. and Applications, 1999.
  • Nikolopoulos, S., Georgiadis, L., Palios, L., Algorithmic Graph Theory. Kallipos, 2015