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

(DIND136) -  Χρήστος Τσίνος (ctsinos@uoa.gr)

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

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

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

Δευτέρα 4 Οκτωβρίου 2021