Αλγόριθμοι

Academic Semester:
Course TypeReference NumberSubprogram
Υποχρεωτικό (Υ)Theory: ΤΠ30Κ4
Lab: ΤΠ31Κ4
SemesterAcademic YearHours per week
Χειμερινό2oTheory: 3 Lab: 2
ExamsECTSWorkload
611
PrerequisitesTeaching methodTeaching Language
Ελληνικά

Ακαδημαϊκό Προσωπικό

Ακαδημαϊκός Υπεύθυνος: 
fragopou's picture
φραγκοπούλου παρασκευή
Fragopoulou Paraskevi
Professor
Καθηγήτρια
+30 2810 379180

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

  • Εισαγωγή: Γενικά περί αλγορίθµων. Μεθοδολογία ανάλυσης αλγορίθµων. Ασυµπτωτικός συµβολισµός. Ρυθµός αύξησης συναρτήσεων. Ανάλυση πολυπλοκότητας. 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, πολλαπλασιασμός πολλών πινάκων). Πιθανοκρατικοί αλγόριθµοι (επιλογή θεµάτων).

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

Πρόεδρος Τμήματος Μηχανικών Πληροφορικής 
Μαλάμος Αθανάσιος, Αναπληρωτής Καθηγητής, amalamos@hmu.gr

Αναπληρωτής Πρόεδρος Τμήματος Μηχανικών Πληροφορικής
Μαριάς Κώστας, Αναπληρωτής Καθηγητής, kmarias@hmu.gr

Γραμματεία
Τμήμα Μηχανικών Πληροφορικής, ΣΤΕΦ, Ελληνικό Μεσογειακό Πανεπιστήμίο, Ηράκλειο, Κρήτη 71500
Τηλ: 2810-379853, 2810-379716, 2810-379795, Fax: 2810-379717
E-mail: secretariat@ie.teicrete.gr
Website: http://www.ie.teicrete.gr