Αλγόριθμοι

ΘΕΩΡΙΑ
Το µάθηµα καλύπτει τις παρακάτω θεµατικές ενότητες.

• Εισαγωγή: Γενικά περί αλγορίθµων. Μεθοδολογία ανάλυσης αλγορίθµων. Ασυµπτωτικός συµβολισµός. Ρυθµός αύξησης συναρτήσεων. Ανάλυση πολυπλοκότητας. Aνασκόπηση βασικών μαθηματιών ενοιών.
• Αναζήτηση: Σειριακή αναζήτηση. Δυαδική αναζήτηση. Αναζήτηση κατά ομάδες. Αναζήτηση παρεμβολής. Αναζήτηση Fibonacci.
• Ταξινόµηση: Ταξινόµηση με επιλογή (selection sort). Ταξινόµηση µε εισαγωγή (insertion sort). Ταξινόμηση με αντιµετάθεση ή φυσαλίδας (bubble sort). Ταξινόµηση παρεµβολής µε φθίνοντα διαστήµατα.  Αναδρομικοί αλγόριθμοι ταξινόμησης. Ταξινόµηση µε διαµερισµό (merge sort). Συγχώνευση (merge). Ταχυταξινόµηση (quicksort, in place quicksort).  Tαξινόµηση σε γραµµικό χρόνο (radix sort, bucket sort, κ.α.). Ταξινόμηση σωρού (heap sort). Εύρεση ελαχίστου, μεγίστου, και διαμέσου.
• Γράφοι: Γενικά, ορισµοί. Δομές δεδομένων για γράφους. ∆ιάσχιση, αναζήτηση (Breadth First Search, Depth First Search). Τοπολογική ταξινόµηση. Ισχυρά συνδεδεµένες συνιστώσες. Ελαφρύτατα συνδετικά δέντρα (Minimum Spanning Trees, Prim, Kruskal). Γράφοι με βάρη. Oµοαφετηριακές διαδροµές (shortest paths, Bellman-Ford, Dijkstra). All-pairs shortest paths. Περιοδεύων πωλητής.
• Αλγοριθμικές τεχνικές: Διαίρει και βασίλευε. Άπληστοι αλγόριθμοι (fractional knapsack). ∆υναµικός προγραµµατισµός (0-1 knapsack, πολλαπλασιασμός πολλών πινάκων). Πιθανοκρατικοί αλγόριθµοι (επιλογή θεµάτων).

 
ΕΡΓΑΣΤΗΡΙΟ
Στο εργαστήριο του µαθήµατος εκπονούνται ασκήσεις που αποτελούν εφαρµογή της διδασκόμενης ύλης της θεωρίας. Ο διδάσκων αξιολογεί τον τρόπο ανάπτυξης και τα αποτελέσµατα των ασκήσεων, ελέγχει την απόδοση µε τέστ που θα διεξάγονται κατά την διάρκεια του εξαμήνου για το σύνολο των φοιτητών. Τέλος, δίνονται εργασίες για κατ' οίκον προετοιµασία, στην ανάπτυξη και στα αποτελέσµατα των οποίων εξετάζεται ο φοιτητής.
 
ΣΥΝΙΣΤΩΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ

• «Αλγόριθμοι Σχεδίαση και Εφαρμογές», Michael T. Goodrich, Roberto Tamassia, Εκδόσεις Μ. Γκιούρδας, 2016, ISBN  978-960-512-697-1.
• «Εισαγωγή στους Αλγόριθμους», Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2006, ISBN 960-524-225-7, ISBN-13 978-960-524-225-1.
• “Algorithms in C”, R. Sedgewick, Addison-Wesley, ISBN 0-201-31452-5.