| Κωδικός Μαθήματος | 321-4200 |
|---|---|
| Εξάμηνο | 4 |
| ECTS | 5.00 |
| Ώρες (Θεωρία) | 3 |
| Ώρες (Εργαστήριο) | 2 |
| Διδάσκοντας | Καπόρης Αλέξης |
Προβλήματα συνδυαστικής βελτιστοποίησης. Αλγόριθμοι αναδρομικοί και διαίρει-και-βασίλευε. Δυναμικός προγραμματισμός. Μέθοδος απληστίας. Αλγόριθμοι γραφημάτων: αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος, εφαρμογές. Ελάχιστα επικαλύπτοντα δέντρα, αλγόριθμοι Prim και Kruskal. Συντομότερα μονοπάτια, αλγόριθμοι Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Μέγιστη ροή, θεώρημα μέγιστης ροής - ελάχιστης τομής, αλγόριθμοι επαυξητικών μονοπατιών. Ροή ελάχιστου κόστους, αλγόριθμοι απάλειψης κύκλων αρνητικού μήκους. Υπολογιστική πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ-πληρότητα, αλγοριθμικές συνέπειες. Αλγόριθμοι προσέγγισης. Πιθανοτικοί αλγόριθμοι.
Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα:
- Έχει την γνώση να μελετάει και να αναλύει θεωρητικά και πειραματικά (γλώσσα C) σημαντικούς αλγόριθμους.
- Έχει την δεξιότητα να εφαρμόζει τεχνικές θεωρητικής και πειραματικής αναλύσεως σημαντικών αλγορίθμων.
- Έχει την ικανότητα να επιλύει προβλήματα χρονικής πολυπλοκότητας.
Δεν απαιτούνται.
Ατομικές και ομαδικές εργασίες, πρακτική εξάσκηση στο εργαστήριο, μικρά τεστ στη μορφή κουίζ, τελική γραπτή εξέταση.
| Δραστηριότητα | Φόρτος Εργασίας Εξαμήνου |
|---|---|
| Διαλέξεις | 52 ώρες |
| Εργαστηριακές Ασκήσεις | 26 ώρες |
| Προσωπική μελέτη | 43 ώρες |
| Πρόοδος | 1 ώρα |
| Τελική εξέταση | 3 ώρες |
| Σύνολο Μαθήματος | 125 ώρες (5 ECTS) |
Τελική εξέταση θεωρίας και εργαστηρίου (υλοποίηση αλγορίθμων σε γλώσσα C/C++)
Ελληνικά (Αγγλικά αν υπάρχουν φοιτητές/φοιτήτριες ERASMUS)