Μάθετε περισσότερα για τις προϋποθέσεις συμμετοχής
Σχεδίαση και Ανάλυση Αλγορίθμων
Επιλογές
Τελευταίες Ανακοινώσεις


Σχεδίαση και Ανάλυση Αλγορίθμων

Σκοπός του μαθήματος

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

Περιεχόμενα του μαθήματος

Πολυπλοκότητα αλγορίθμων και προβλημάτων, πολυπλοκότητα καλύτερης, χειρότερης και μέσης περίπτωσης, αποσβεστική πολυπλοκότητα.
Διαχείριση συνόλων: ευρετήρια, ουρές προτεραιότητας,
union-find.
Σχεδιασμός αποτελεσματικών αλγορίθμων: άπληστοι αλγόριθμοι, διαίρει και βασίλευε, δυναμικός προγραμματισμός.
Αλγόριθμοι γραφημάτων: διάσχιση, συνεκτικότητα, μονοπάτια, μεταβατική κλειστότητα, τοπολογική ταξινόμηση, επικαλυπτικά δένδρα, ροές, ταιριάσματα.
Aλγεβρικοί αλγόριθμοι: πίνακες, πολυώνυμα και ταχύς μετασχηματισμός Fοurier.
Αλγόριθμοι θεωρίας αριθμών.
Αλγόριθμοι ταιριάσματος προτύπων.
Κλάσεις πολυπλοκότητας και ΝΡ-πλήρη προβλήματα.
Αλγόριθμοι για Ν
P-πλήρη προβλήματα: προσεγγιστικοί αλγόριθμοι, οπισθοδρόμηση, διακλάδωση-και-φράγμα, τοπική αναζήτηση. Εισαγωγή στους άμεσους (on-line) αλγόριθμους.

Βιβλιογραφία

Γ. Φ. Γεωργακόπουλος, "Δομές Δεδομένων: Έννοιες Τεχνικές και Αλγόριθμοι", Πανεπιστημιακές Εκδόσεις Κρήτης, 2002.
Τ. Η. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Introduction to Algorithms" (Second Edition), MIT Press and McGraw-Hill, 2001.
A. V. Aho, J. E. Hopcroft and J. D. Ullman, "Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
C. H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization", Dover, 1998.
C. H. Papadimitriou, "Computational Complexity", Addison-Wesley, 1994.

Απαιτούμενο Υπόβαθρο

Σύνολα, σχέσεις και συναρτήσεις. Γραφήματα και δένδρα. Συνδυαστική: μεταθέσεις, διατάξεις και συνδυασμοί. Βασικές έννοιες και εργαλεία θεωρίας πιθανοτήτων. Επαγωγή, αναδρομή και αναδρομικές σχέσεις. Πολυπλοκότητα αλγορίθμων και ασυμπτωτικοί συμβολισμοί (Ο, Ω, Θ, ο, ω, ?). Πίνακες και γραμμικές δομές δεδομένων (λίστες, στοίβες, ουρές). Δυαδικά δένδρα αναζήτησης, ισοζυγισμένα δένδρα, κατακερματισμός, σωροί. Αναζήτηση, ταξινόμηση και στατιστικές τάξεως. Βασικοί αλγόριθμοι γραφημάτων. Τεχνικές σχεδίασης αλγορίθμων και βασικά παραδείγματα (άπληστοι αλγόριθμοι, διαίρει και βασίλευε, δυναμικός προγραμματισμός). NP-πλήρη προβλήματα.

Ιστοσελίδα του μαθήματος

 



Οδηγός Σπουδών του Προγράμματος
Βρείτε εδώ ολες τις απαραίτητες πληροφορίες

Οδηγός Σπουδών του Προγράμματος
ΟΠΑ - Πρόγραμμα Μεταπτυχιακών Σπουδών στην Επιστήμη των Υπολογιστών
Copyright 2024 - All Rights Reserved