|
|
|
|
αρχική · σπουδές
| Αλγόριθμοι & Πολυπλοκότητα |
| Χαρακτηρισμός |
Ειδικής Υποδομής |
| Κωδικός Μαθήματος |
421 |
| Περιγραφή |
Ασυμπτωτικός συμβολισμός και ανάλυση αλγορίθμων
(sequencing, for/while/repeat loops, recursive calls). Ανάλυση αλγορίθμων
αναζήτησης και ταξινόμησης. Άπληστοι αλγόριθμοι (π.χ. αλγόριθμοι Kruskal,
Prim). Τεχνικές σχεδίασης αλγορίθμων: Διαίρει και βασίλευε (top-down τεχνική), Δυναμικός προγραμματισμός (bottom-up τεχνική). Πιθανοκρατικοί
αλγόριθμοι (π.χ. αλγόριθμοι Monte Carlo, Las Vegas). Στοιχεία παράλληλων
αλγορίθμων. Στοιχεία Πολυπλοκότητας: Οι κλάσεις P και NP, πληρότητα NP. |
| Στόχος - Σκοπός |
Ο σκοπός αυτού του μαθήματος σαν συνέχεια των «Δομές Δεδομένων και Αλγόριθμοι» είναι αφενός η παρουσίαση πιο περίπλοκων
αλγορίθμων καθώς και κάποιων ιδιαίτερων περιπτώσεων όπως οι παράλληλοι, πιθανοκρατικοί και άλλοι αλλά και αφετέρου η εισαγωγή εννοιών όπως
ανάλυση πολυπλοκότητας αλγορίθμων και η σημασία του τεκμηριωμένου υπολογισμού του χρόνου υλοποίησής των. Τέλος, η εκμάθηση τεχνικών
σχεδίασης αλγορίθμων είναι ένας από τους πιο βασικούς σκοπούς του μαθήματος.
Με την ολοκλήρωση του μαθήματος, ο σπουδαστής θα είναι σε θέση να
εκτιμήσει την πολυπλοκότητα ενός αλγορίθμου αλλά θα ξέρει και σημαντικές
τεχνικές σχεδίασης. Επίσης, θα είναι σε θέση να αναπτύξει περίπλοκους αλ-
γόριθμους και να υπολογίζει τα χρονικά όρια μέσα στα οποία θα κυμανθεί η
υλοποίησή του. |
| Βιβλιογραφία |
• Ιωάννης Χατζηλυγερούδης, «Δομές Δεδομένων, Εισαγωγή Στην Πληροφορική, Τόμος Γ», Ελληνικό Ανοικτό Πανεπιστήμιο, Πάτρα, 2000
• Colin Reeves (Edited), “Modern Heuristic Techniques for Combinatorial
Problems”, McGraw Hill Book Company, UK, 1995
• Herbert S. Wilf, “Algorithms And Complexity”, Prentice Hall Inc., USA,
1986
• Robert Sedgewick, “Algorithms In C”, Addison – Wesley Publishing
Company, USA, 1998
• Michael R. Garey, David S. Johnson,“Computers And Intractability, A
Guide To The Theory Of NP-Completeness”, W.H. Freeman And Company,
New York, USA, 1979
|
|
|
|
|
|
|
