Παρουσίαση/Προβολή

(MATH1110) -  Δημήτρης Καββαδίας

Περιγραφή Μαθήματος

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

 

Σε περίπτωση που για οποιονδήποτε λόγο είναι αναγκαία η εξ' αποστάσεως επικοινωνία, αυτη θα γίνεται μέσω του συνδέσμου:

https://upatras-gr.zoom.us/j/96721227438?pwd=OFlDcjd4OHhWdDFNZWRONnZzUVBhdz09

Ημερομηνία δημιουργίας

Παρασκευή, 20 Μαρτίου 2020