Αλγόριθμοι

Στη συγκεκριμένη ενότητα πραγματοποιείται μια πρώτη γνωριμία με το μάθημα. Δίνεται το κίνητρο της ενασχόλησης με τα περιεχόμενα του μαθήματος και παρέχονται βασικές έννοιες και ορισμοί.

Λέξεις Κλειδιά: Αλγόριθμος, ταξινόμηση, ταξινόμηση με επιλογή, μέγιστος κοινός διαιρέτης

Στη συγκεκριμένη ενότητα παρουσιάζονται έννοιες σχετικά με την ανάλυση των αλγορίθμων όπως η χρονική αποδοτικότητα, οι τάξεις μεγέθους και οι ασυμπτωτικοί συμβολισμοί Ο, Ω, Θ.

Λέξεις Κλειδιά: Ανάλυση αλγορίθμων, αποδοτικότητα, καλύτερη περίπτωση, μέση περίπτωση, χειρότερη περίπτωση, τάξη μεγέθους, ασυμπτωτική κλάση, πύργοι του Ανόι, Fibonacci

Η συγκεκριμένη ενότητα παρέχει βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Ωμή Βία». Επίσης, παρουσιάζονται αλγόριθμοι «Ωμής Βίας» για ορισμένα κλασικά προβλήματα (π.χ. ταύτιση προτύπου, κυρτού περιβλήματος κ.α.)

Λέξεις Κλειδιά: Ωμή βία, bubble sort, εξαντλητική αναζήτηση

Σε αυτήν την ενότητα παρουσιάζονται βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Διαίρει και Βασίλευε». Συγκεκριμένα, αναλύονται δύο σημαντικοί αλγόριθμοι ταξινόμησης, ο αλγόριθμος της ταξινόμησης με συγχώνευση και ο αλγόριθμος της γρήγορης ταξινόμησης. Επίσης παρουσιάζεται ο πολλαπλασιασμός πινάκων αλά Strassen και ο αλγόριθμος Quickhull για το πρόβλημα του κυρτού περιβλήματος.

Λέξεις Κλειδιά: Διαίρει και Βασίλευε, αναδρομή, ταξινόμηση με συγχώνευση, γρήγορη ταξινόμηση, Strassen, Quickhull

Στην ενότητα αυτή αναπτύσσονται βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Μείωσε και Βασίλευε». Συγκεκριμένα, περιγράφονται ο αλγόριθμος της ταξινόμησης με εισαγωγή και οι μέθοδοι διάσχισης γράφων DFS και BFS. Επίσης, αναφέρονται ζητήματα σχετικά με τη δημιουργία μεταθέσεων, το πρόβλημα εύρεσης μέσου και την αναζήτηση παρεμβολής.

Λέξεις Κλειδιά: Μείωσε και Βασίλευε, ταξινόμηση με εισαγωγή, αναζήτηση κατά βάθος, DFS, αναζήτηση κατά πλάτος, BFS, τοπολογική ταξινόμηση, δημιουργία μεταθέσεων, αναζήτηση παρεμβολής

Η συγκεκριμένη ενότητα περιγράφει βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Μετασχημάτισε και Κυριάρχησε». Συγκεκριμένα, γίνεται αναφορά στο πρόβλημα της επιλογής και στη Gaussian απαλοιφή, αναλύονται τα ισοζυγισμένα δένδρα AVL ενώ τέλος περιγράφεται η ταξινόμηση με τη χρήση σωρού.

Λέξεις Κλειδιά: Μετασχημάτισε και Κυριάρχησε, προταξινόμηση, Gaussian απαλοιφή, Δένδρα AVL, σωρός, ταξινόμηση με σωρό

Η ενότητα αυτή αναλύει μεθόδους οι οποίες βασίζονται στη χρήση επιπλέον χώρου με σκοπό τη μείωση του συνολικού χρόνου εκτέλεσής τους. Οι τρεις κύριες έννοιες που παρουσιάζονται στην ενότητα είναι η ταξινόμηση με απαρίθμηση, η ταύτιση προτύπου με τους αλγορίθμους Horspool και Boyer-Moore και ο κατακερματισμός.

Λέξεις Κλειδιά: Συμβιβασμοί, ταξινόμηση με απαρίθμηση, ταύτιση προτύπου, ολίσθηση, Horspool, Boyer-Moore, ανοικτός κατακερματισμός, κλειστός κατακερματισμός

Σε αυτή την ενότητα παρουσιάζονται έννοιες σχετικά με τον Δυναμικό Προγραμματισμό καθώς και οι αλγόριθμοι Warshall, Floyd που βασίζονται στη λογική του Δυναμικού Προγραμματισμού. Επίσης, παρουσιάζονται έννοιες σχετικά με βέλτιστα δυαδικά δέντρα αναζήτησης καθώς και με το πρόβλημα του σάκου (knapsack).

Λέξεις Κλειδιά: Δυναμικός προγραμματισμός, διωνυμικοί συντελεστές, Warshall, Floyd, βέλτιστα δυαδικά δέντρα αναζήτησης, πρόβλημα του σάκου

Στην παρούσα ενότητα αναλύονται οι άπληστοι αλγόριθμοι και δίνονται συγκεκριμένα παραδείγματά τους, όπως οι αλγόριθμοι Prim, Kruskal και Dijkstra που αφορούν γραφήματα.

Λέξεις Κλειδιά: Άπληστος αλγόριθμος, απληστία, ζευγνύον δένδρο, Prim, Kruskal, Dijkstra, Huffman

Το περιεχόμενο της συγκεκριμένης ενότητας αφορά την επαναληπτική βελτίωση η οποία είναι μια τεχνική σχεδίασης αλγορίθμων για προβλήματα βελτιστοποίησης. Συγκεκριμένα, παρουσιάζεται η μέθοδος Simplex καθώς και το πρόβλημα του ευσταθούς γάμου.

Λέξεις Κλειδιά: Επαναληπτική βελτίωση, simplex, ευσταθής γάμος

Σε αυτή την ενότητα γίνεται μια παρουσίαση εννοιών σχετικά με τους περιορισμούς της αλγοριθμικής ισχύος. Συγκεκριμένα, αναπτύσσονται τα κατώτερα φράγματα και οι κλάσεις P και NP

Λέξεις Κλειδιά: Περιορισμοί αλγοριθμικής ισχύος, κατώτερο φράγμα, δένδρα απόφασης, κλάση P, κλάση NP, CNF, NP-complete

Στη συγκεκριμένη ενότητα παρουσιάζονται η τεχνική της ανάτρεξης και η τεχνική της φραγής-και-διακλάδωσης οι οποίες αποτελούν δύο στρατηγικές αντιμετώπισης περιορισμών αλγοριθμικής ισχύος. Επίσης, περιγράφεται το πρόβλημα των n βασιλισσών, το πρόβλημα του Χαμιλτονιανού κυκλώματος καθώς και το πρόβλημα της ανάθεσης.

Λέξεις Κλειδιά: Αντιμετώπιση περιορισμών αλγοριθμικής ισχύος, ανάτρεξη, διακλάδωση και φραγή