Εισαγωγή στους Αλγόριθμους¶

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι¶

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

Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα έχουν αναπτύξει τις ακόλουθες δεξιότητες:

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

Περιεχόμενο (ύλη)¶

Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων Η έννοια του αλγορίθμου, εφαρμογές και σημασία αλγορίθμων. Η έννοια της αποδοτικότητας, μοντέλο μέτρησης αποδοτικότητας, μέθοδοι ανάλυσης αλγορίθμων, τεχνολογική σημασία αποδοτικών αλγορίθμων.
Βασικές έννοιες Ανάλυσης και Πολυπλοκότητας Αλγορίθμων Αποδοτικότητα και χρονική πολυπλοκότητα, βέλτιστο αλγορίθμων, ασυμπτωτική πολυπλοκότητα, ορθότητα αλγορίθμων.
Βασικοί Αλγόριθμοι και Στοιχειώδεις Δομές Δεδομένων Πίνακες, λίστες, στοίβες, ουρές, δένδρα. Αλγόριθμοι εύρεσης ελαχίστου ή μεγίστου στοιχείων, συγχώνευσης, ενθετικής ταξινόμησης, δυαδικής αναζήτησης, απαρίθμησης πλειάδων. Σωρός, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort).
Ευσταθές Ταίριασμα Διατύπωση προβλήματος και εφαρμογές του. Αλγόριθμος πρότασης/απόρριψης. Ανάλυση ορθότητας και πολυπλοκότητας αλγορίθμου. Αποδοτική υλοποίηση αλγορίθμου.
Τεχνική «Διαίρει και Βασίλευε» και Εφαρμογές της Γενική περιγραφή τεχνικής «Διαίρει & Βασίλευε». Αλγόριθμοι συγχωνευτικής ταξινόμησης (mergesort) και μέτρησης αντιστροφών. Αναδρομικές σχέσεις και μέθοδοι επίλυσής τους.
Γραφήματα και Αλγόριθμοι Γραφημάτων Γραφήματα ως βασικό εργαλείο μοντελοποίησης δικτύων και συστημάτων. Βασικές ιδιότητες και χαρακτηριστικά γραφημάτων. Συνεκτικότητα γραφημάτων. Αλγόριθμοι αναζήτησης πρώτα κατά βάθος (ΑΠΒ) και πρώτα κατά πλάτος (ΑΠΠ). Εφαρμογές/επεκτάσεις αλγορίθμων ΑΠΒ και ΑΠΠ στην εύρεση συνεκτικών συνιστωσών, τοπολογικής διάταξης, ισχυρά συνεκτικών συνιστωσών, και στον έλεγχο διμερότητας.
Τεχνική Απληστίας και Εφαρμογές της Γενική περιγραφή τεχνικής απληστίας. Αλγόριθμοι επίλυσης προβλημάτων χρονοπρογραμματισμού: χρονοπρογραμματισμός διαστημάτων, διαμέριση χρονικών διαστημάτων, χρονοπρογραμματισμός για ελαχιστοποίηση καθυστέρησης. Αλγόριθμοι επίλυσης προβλημάτων βελτιστοποίησης: ελάχιστα γεννητικά δένδρα (αλγόριθμοι Kruskal και Prim), συντομότερες διαδρομές (αλγόριθμος Dijkstra). Αποδοτική υλοποίηση αλγορίθμων βελτιστοποίησης.
Τεχνική Δυναμικού Προγραμματισμού και Εφαρμογές της Γενική περιγραφή τεχνικής δυναμικού προγραμματισμού. Αποδοτική εφαρμογή και υλοποίηση τεχνικής δυναμικού χρονοπρογραμματισμού. Αλγόριθμοι επίλυσης προβλημάτων σταθμισμένου χρονοπρογραμματισμός διαστημάτων. Αλγόριθμοι επίλυσης προβλημάτων σακιδίου.

Αξιολόγηση¶

Γλώσσα αξιολόγησης: Ελληνική (Αγγλικά αν χρειαστεί)

Αξιολόγηση (τα κριτήρια βρίσκονται στην ιστοσελίδα του μαθήματος): - Γραπτή εξέταση προόδου στο τέλος της 8ης διδακτικής εβδομάδας (40% του τελικού βαθμού). - Γραπτή τελική εξέταση (60% του τελικού βαθμού).

Γραπτή εξέταση (προόδου και τελική): διαβαθμισμένης δυσκολίας, η οποία περιλαμβάνει ερωτήσεις σύντομης απάντησης, επίλυση προβλημάτων με ανάπτυξη αλγορίθμων, αποδείξεις ορθότητας και πολυπλοκότητας αλγορίθμων, ασκήσεις.

Σειρά εργαστηριακών ασκήσεων με στόχο την εξοικείωση, εξάσκηση και απόκτηση εμπειρίας:

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

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

J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων. Ελληνική έκδοση. Εκδόσεις Κλειδάριθμος, 2008. Διαθέσιμο στον Εύδοξο.
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους. Ελληνική 2η έκδοση. Πανεπιστημιακές Εκδόσεις Κρήτης, 2016. Διαθέσιμο στον Εύδοξο.
K. Mehlhorn and P. Sanders, Αλγόριθμοι και Δομές Δεδομένων – Τα βασικά εργαλεία. Εκδόσεις Κλειδάριθμος, 2014. Διαθέσιμο στον Εύδοξο.
Διδακτικές σημειώσεις και διαφάνειες που αναρτώνται στην ιστοσελίδα του μαθήματος.

-Συναφή επιστημονικά περιοδικά:

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