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