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

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Πολυπλοκότητα κατά μέσο όρο και πολυπλοκότητα στη χείριστη περίπτωση. Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. Σωροί και ουρές προτεραιότητας, Heapsort. Τεχνικές αναζήτησης: δένδρα αναζήτησης, μετασχηματισμός κλειδιού (hashing), union and find. Τεχνικές διάσχισης σε γράφους: κατά πλάτος (BFS), κατά βάθος (DFS), συνεκτικές συνιστώσες. Τεχνικές σχεδίασης αλγορίθμων. Divide and conquer: αλγόριθμοι ταξινόμησης και επιλογής, δυαδική αναζήτηση, το θεώρημα κυριαρχίας (master theorem). Άπληστοι (greedy) αλγόριθμοι: ανάθεση πόρων - μέγιστο ανεξάρτητο σύνολο σε γράφους διαστημάτων, δένδρο επικάλυψης ελάχιστου κόστους (minimum cost spanning tree), βέλτιστα μονοπάτια σε γράφους, το συνεχές πρόβλημα του σακιδίου (knapsack problem), ελάχιστη επικάλυψη συνόλου (minimum set cover). Δυναμικός προγραμματισμός: ελάχιστα μονοπάτια σε γράφους (αλγόριθμος Bellman), μέγιστη κοινή υπακολουθία, 0-1 σακίδιο. Δενδροειδείς αλγόριθμοι: το πρόβλημα των κ-βασιλισσών, το πρόβλημα του πλανόδιου πωλητή (TSP). Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα  NP-complete και NP-hard, αναγωγές.