Κ17 Αλγόριθμοι και Πολυπλοκότητα

• ΘΕΩΡΗΤΙΚΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ

• Κ09 - Διακριτά Μαθηματικά

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Πολυπλοκότητα κατά μέσο όρο και πολυπλοκότητα στη χείριστη περίπτωση. Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. Σωροί και ουρές προτεραιότητας. Τεχνικές αναζήτησης: δένδρα αναζήτησης, μετασχηματισμός κλειδιού (hashing)-πολυπλοκότητα κατά μέσο όρο, Union and Find. Τεχνικές διάσχισης σε γράφους: εξερεύνηση κατά πλάτος (Breadth First Search), εξερεύνηση κατά βάθος (Depth First Search). Τεχνικές σχεδίασης αλγορίθμων. Divide and conquer: αλγόριθμοι ταξινόμησης και επιλογής (πολυπλοκότητα κατά μέσο όρο), δυαδική αναζήτηση (binary search). ’πληστοι (greedy) αλγόριθμοι: ελάχιστου κόστους συνδετικό δένδρο (minimum cost spanning tree), βέλτιστα μονοπάτια σε γράφους (αλγόριθμος Dijkstra), το συνεχές πρόβλημα του σακιδίου (knapsack problem), 0-1 knapsack, επικάλυψη συνόλου (set cover). Δυναμικός προγραμματισμός: βέλτιστα μονοπάτια σε γράφους (αλγόριθμος Bellman), το πρόβλημα βέλτιστου τεμαχισμού (cutting stock problem). Δενδροειδείς αλγόριθμοι: το πρόβλημα των κ-βασιλισσών. Αυξητικοί αλγόριθμοι (incremental algorithms): εύρεση συνεκτικών συνιστωσών, ελάχιστου κόστους συνδετικό δένδρο. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και NP-hard.