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

Κωδικός μαθήματος
αλγ-πολ
Μονάδες ECTS
6
Εξάμηνο
Εξάμηνο Δ
Κατηγορία μαθήματος
Κατεύθυνση
Κορμού
Περιγραφή μαθήματος
ΠΕΡΙΕΧΟΜΕΝΟ ΜΑΘΗΜΑΤΟΣ

Περιεχόμενα: Αλγόριθμοι και υπολογιστικά προβλήματα, Ανάλυση αλγορίθμων, Ασυμπτωτικοί συμβολισμοί, Αναδρομικές σχέσεις. Τεχνικές σχεδίασης: Διαίρει-και-Βασίλευε, Άπληστοι αλγόριθμοι, Δυναμικός προγραμματισμός. Αλγόριθμοι γραφημάτων: Αναζήτηση κατά πλάτος, Αναζήτηση σε βάθος, Τοπολογική ταξινόμηση, Ελάχιστα συνδετικά δέντρα, Συντομότερα μονοπάτια. Εισαγωγή στη θεωρία πολυπλοκότητας: Προβλήματα P, ΝP, και NP-πλήρη, Αναγωγές πολυωνυμικού χρόνου. Ειδικά θέματα: Προσεγγιστικοί αλγόριθμοι, Πιθανοτικοί αλγόριθμοι και Υπολογιστική γεωμετρία.

ΑΞΙΟΛΟΓΗΣΗ ΦΟΙΤΗΤΩΝ

Αξιολόγηση: Εργασίες με βάρος 30%-40% και γραπτή εξέταση.

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

URL ΜΑΘΗΜΑΤΟΣ ΣΤΟ ECLASS

https://eclass.uop.gr/courses/1768/

ΣΥΝΙΣΤΩΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ

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

  1. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Εισαγωγή στους αλγορίθμους, 1η έκδοση, ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, 2016. Κωδικός στον Εύδοξο: 59359780
  2. J. Kleinberg, E. Tardos, Σχεδιασμός αλγορίθμων, 1η έκδοση, Κλειδάριθμος, 2009. Κωδικός στον Εύδοξο: 13898
  3. S. Dasgupta, C. Papadimitriou, U. Vazirani, Αλγόριθμοι, 1η έκδοση, Κλειδάριθμος, 2009. Κωδικός στον Εύδοξο: 13583
  4. M. Goodrich, R. Tamassia, Αλγόριθμοι Σχεδίαση και Εφαρμογές, 1η έκδοση, Γκιούρδας, 2016. Κωδικός στον Εύδοξο: 59359833