Τμήμα Μαθηματικών | Πανεπιστήμιο Πατρών


Αλγόριθμοι και Πολυπλοκότητα
Περιγραφή

Η έννοια του αποδοτικού υπολογισμού - υπολογιστικοί πόροι - χρόνος, μνήμη. Πολυπλοκότητα αλγορίθμων, βέλτιστοι αλγό­ριθμοι. Βασικές τεχνικές στην ανάλυση και σχεδιασμό αλγορίθ­μων. Αλγόριθμοι Greedy. Η τεχνική και οι αλγόριθμοι “Διαίρει και Βασίλευε”. Παραγόμενα δέντρα ελάχιστου κόστους: οι αλγόριθμοι των Kruskal και Prim. Μη κατευθυντικά γραφήματα: Αναζήτηση κατά βάθος. Εύρεση σημείων διαμέρισης και δισυ­νεκτικών συνιστωσών. Το πρόβλημα του Matching σε διμερή γραφήματα. Κατευθυντικά γραφήματα: Εύρεση ισχυρά συνε­κτικών συνιστωσών. Αναζήτηση κατά βάθος. Ελάχιστα μονο­πάτια: Dijkstra, Bellman-Ford, τοπολογική διάταξη και ελάχιστα μονοπάτια σε DAG (Directed Acyclic Graphs). Πολυπλοκότητα προβλημάτων. Παραδείγματα. Υπολογιστικά μοντέλα. Η μηχανή Turing. Μη ντετερμινιστική μηχανή Turing. Καθολική μηχανή Turing. Κλάσεις πολυπλοκότητας και γενικές σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Οι έννοιες της αναγωγής (λογαρι­θμικού χώρου - πολυωνυμικού χρόνου) και της πληρότητας και η σημασία τους. Οι κλάσεις P και NP. Ορισμοί. NP-πληρό­τητα. Το Θεώρημα του Cook. Μερικά NP-πλήρη προβλήματα (ικανοποιησιμότητα και παραλλαγές, γραφοθεωρητικά προ­βλήματα, ακέραιος προγραμματισμός). Ισχυρή και ασθενής NP-πληρότητα.

Τομέας: Υπολογιστικών Μαθηματικών και Πληροφορικής
Συγγράμματα:

Πρόγραμμα Σπουδών:
Προπτυχιακό Πρόγραμμα Σπουδών
Εξάμηνο: Η
Πιστωτικές Μονάδες (ECTS): 6
Ωρες Διδασκαλίας (Θ/Φ/Ε): 2/2/0
Κωδικός: IC438
Τύπος Μαθήματος: Επιλογής
Κατεύθυνση ΓΝΜ: Βασικό
Κατεύθυνση ΘΡΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΕΦΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΠΛΗ: Υποχρεωτικό Κατεύθυνσης
Κατεύθυνση ΣΠΕ: Ελεύθερης Επιλογής
Φοιτητές Erasmus: Όχι




keyboard_arrow_up