Αλγόριθμοι και Πολυπλοκότητα

Εξάμηνο	8ο
Κωδικός	Λ11Ε
ECTS	3
Διδακτικές Μονάδες	4
Ώρες Θεωρίας	2
Ώρες Ασκήσεων	1
Ώρες Εργαστηρίου	2
Τομέας	Λογισμικού και Ανάπτυξης Εφαρμογών
Διδάσκοντες	Παύλος Εφραιμίδης

Περίληψη

Βασικές έννοιες αλγορίθμων. Ταξινόμηση και Αναζήτηση. Υπολογιστικά Μοντέλα. Η μηχανή Turing και η Random Access Machine. Πολυπλοκότητα Αλγορίθμων. Τεχνικές Σχεδιασμού Αλγορίθμων. Διαίρει και Βασίλευε. Αναδρομή και Απαλοιφή Αναδρομής. Δυναμικός Προγραμματισμός. Απληστία. Αλγόριθμοι Γραφημάτων και Δέντρων. Αλγόριθμοι με χρήση Τυχαιότητας. Κλάσεις Πολυπλοκότητας. Οι κλάσεις P και NP. Προβλήματα πλήρη για την κλάση NP. Αναγωγές. Αναφορά σε Ευρετικές Τεχνικές και Αλγόριθμους Προσέγγισης. Σχεδιασμός και υλοποίηση βασικών Αλγορίθμων σε σύγχρονα περιβάλλοντα Προγραμματισμού.

Θεωρία

Θα ασχοληθούμε με επιλεγμένα θέματα Αλγορίθμων και Πολυπλότητας. Θα χρησιμοποιήσουμε ως εφαρμογή παραδείγματα και έννοιες από την Αλγοριθμική Θεωρία Παινγίων.

Εργαστήριο

Θα υλοποιήσουμε πολιτικές παικτών-agents που θα συναγωνιστούν σε απλά (δικτυακά) παίγνια.

Διδάσκων

Παύλος Εφραιμίδης, Αναπλ. Καθηγητής.

Ώρες γραφείου

Παύλος (για οποιοδήποτε θέμα): Τετάρτη 09:00 – 12:00.

Ημερομηνία	Τύπος	Σχόλια	Αρχεία
14-02-2020	Εισαγωγή στο μάθημα

Βιβλιογραφικές εργασίες.

1. eClass του μαθήματος
2. Χώρος συζητήσεων στο DUTh EECE forum

Διακρίσεις στην Εργασία 2: Επίλυση του k-center

Καλύτερες λύσεις για το Γ146

1. Κόστος 677, Ομάδες 17, 19 και 20

Καλύτερες λύσεις για το Γ500

1. Κόστος 1757, Ομάδα 17
2. Κόστος 1779, Ομάδα 19
3. Κόστος 1785, Ομάδες 3 και 20

Πρωτότυπος αλγόριθμος

1. • Ομάδα 29, CDS heuristic
   • Ομάδα 15, Αλγόριθμος βασισμένος σε paper
2. • Ομάδες 0 και 8: Αλγόριθμος k-medoids ή partitioning around medoids (PAM)
   • Ομάδες 19 και 24: Γενετικός Αλγόριθμος