Ανακεφαλαίωση

Αρχικά ορίστηκε και αναλύθηκε η έννοια της επίδοσης των αλγορίθμων, με ειδικότερη αναφορά στη χειρότερη περίπτωση κάθε αλγόριθμου. Έγινε καταγραφή των μεγεθών που επηρεάζουν την επίδοση ενός αλγορίθμου και των βασικών πράξεων για την ταξινόμηση, την αναζήτηση και τον πολλαπλασιασμό καθώς και για άλλα είδη προβλημάτων. Δόθηκε ορισμός για την αποδοτικότητα και για την ορθότητα των αλγορίθμων. Η πολυπλοκότητα αλγορίθμων περιγράφεται αναλυτικά και τυποποιούνται οι ορισμοί για τις κατηγορίες (τάξεις) πολυπλοκότητας των περισσότερων ειδών αλγορίθμων. Μερικοί από τους πλέον γνωστούς αλγορίθμους αναλύονται και εκφράζεται η πολυπλοκότητα τους με χρήση των αντίστοιχων συμβολισμών των κατηγοριών πολυπλοκότητας. Τέλος, παρουσιάζεται καταγραφή των ειδών των αλγορίθμων και τυποποιούνται με χρήση ορισμών οι πλέον γνωστοί τύποι αλγορίθμων (πολυωνυμικοί, μη πολυωνυμικοί, παράλληλοι αλγόριθμοι).

Λέξεις κλειδιά

Επίδοση/ αποδοτικότητα αλγορίθμου, Χειρότερη περίπτωση αλγορίθμου, Μέγεθος εισόδου, Ορθότητα αλγορίθμου, Πολυπλοκότητα αλγορίθμων, Συμβολισμός Ο, Ανάλυση αλγορίθμων, Είδη αλγορίθμων, Υπολογιστική Πολυπλοκότητα, Προσεγγιστικοί αλγόριθμοι, Ευριστικοί αλγόριθμοι

Ερωτήσεις - Θέματα για συζήτηση 1. Ποιά είναι τα πρωταρχικά ερωτήματα που τίθενται για την κατανόηση της επίδοσης ενός αλγορίθμου; 2. Τι είναι και πώς μπορεί να εκφρασθεί η χειρότερη περίπτωση ενός αλγορίθμου; 3. Να περιγραφεί το μέγεθος της εισόδου ενός αλγορίθμου και να δοθεί ένα παράδειγμα αναγνώρισης και καταγραφής αυτού του μεγέθους. 4. Από ποιους κύριους παράγοντες εξαρτάται ο χρόνος εκτέλεσης ενός αλγορίθμου; 5. Ποιες είναι οι απαραίτητες προϋποθέσεις για να είναι δυνατή η σύγκριση μεταξύ δύο προγραμμάτων αλγορίθμων; 6. Να ορισθεί η αποδοτικότητα αλγορίθμων. 7. Τι είναι ο έλεγχος ορθότητας ενός αλγορίθμου και ποιοι περιορισμοί υπάρχουν για αυτόν τον έλεγχο; 8. Να περιγραφεί ο τρόπος απόδειξης της ορθότητας ενός αλγορίθμου και να δοθεί ένα παράδειγμα απόδειξης ορθότητας αλγορίθμου. 9. Να δοθεί ο ορισμός της πολυπλοκότητας αλγορίθμου. 10. Με τη βοήθεια ενός διαγράμματος να γίνει σύγκριση μεταξύ της λογαριθμικής, της γραμμικής και της τετραγωνικής πολυπλοκότητας. 11. Ποια είναι η πολυπλοκότητα των λειτουργιών σε στοίβες και ουρές; 12. Ποια είναι η πολυπλοκότητα της σειριακής αναζήτησης; 13. Ποια είναι τα κυριότερα είδη αλγορίθμων;

Βιβλιογραφία 1. Φώτω Αφράτη και Γιώργος Παπαγεωργίου, Αλγόριθμοι ­ Μέθοδοι Σχεδίασης και Ανάλυση Πολυπλοκότητας, Εκδόσεις Συμμετρία, Αθήνα, 1993. 2. Χρήστος Κοίλιας, Δομές Δεδομένων και Οργάνωση Αρχείων. Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 1993. 3. Μανόλης Λουκάκης, Δομές Δεδομένων και Αλγόριθμοι, Εκδόσεις Θεραπευτικής Κοινότητας Ιθάκη, Θεσσαλονίκη, 1988. 4. Ιωάννης Μανωλόπουλος, Δομές Δεδομένων ­ μία Προσέγγιση με Pascal, Εκδόσεις Art of Text, Θεσσαλονίκη, 1998. 5. Ν. Μισυρλής, Δομές Δεδομένων, Συμμετρία, Αθήνα, 1993. 6. Niklaus Wirth, Αλγόριθμοι και Δομές Δεδομένων, Κλειδάριθμος, Αθήνα, 1990. 7. G. Brassard and P. Bratley, Fundamentals ofAlgorithms, Prentice Hall, 1996. 8. T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms MIT Press, 1990. 9.E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms, Computer Science Press, 1998. 10. I. Oliver, Programming Classics: Implementing the World's Best Algorithms, Prentice Hall, 1993. Διευθύνσεις Διαδικτύου - http://www.csd.auth.gr/~contest/ Κόμβος που ανήκει στο Τμήμα Πληροφορικής του Αριστοτέλειου Πανεπιστήμιου Θεσσαλονίκης. Παρέχει πληροφορίες για τις Βαλκανιάδες Πληροφορικής και συνδέει με άλλους παρεμφερείς κόμβους. - http://olympiads.win.tue.nl/ioi/ Κόμβος Ολυμπιάδων Πληροφορικής με σχετικά προβλήματα αλγορίθμων. - http://acm.baylor.edu/acmicpc/ Κόμβος με πληροφορίες και προβλήματα από μαθητικούς διαγωνισμούς Πληροφορικής που διοργανώνονται από τον οργανισμό Association for Computing Machinery (ACM).