Προηγμένα Θέματα Αλγορίθμων

Εξάμηνο:
7ο
Τύπος Μαθήματος:
Προαιρετικό (ΠΜ)
Κατεύθυνση:
-
Κωδικός:
ΘΠ12
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
B Βασικό
Διαχείριση Δεδομένων και Γνώσης (S2):
-
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
-
Σχετικά Μαθήματα
Σύντομη περιγραφή Μαθήματος

Το μάθημα αποσκοπεί στην εμβάθυνση σε θέματα σχεδίασης και ανάλυσης αλγορίθμων. 

Μέγιστες ροές και ελάχιστες αποκοπές σε ένα δίκτυο. Αλγόριθμοι μέγιστης ροής. Μέγιστα ταιρίασματα. Ασύνδετες διαδρομές σε κατευθυνόμενα και μη κατευθυνόμενα γραφήματα.  Χρονοπρογραμματισμός εργασιών, σχεδιασμός διεξαγωγής έρευνας, τμηματοποιήση εικόνας, επιλογή έργων. Εύκολα και δύσκολα προβλήματα, προβλήματα απόφασης. Oι κλάσεις P και NP. Προβλήματα NP-complete και NP-hard, αναγωγές. Το πρόβλημα του πλανόδιου πωλητή (TSP), κύκλος Hamilton, προβλήματα διαμέρισης, χρωματισμός γραφήματος. Τυχαιοποιημένοι αλγόριθμοι: Αλγόριθμοι Monte Carlo, Αλγόριθμοι Las Vegas, Τυχαιοποιημένο διαίρει και βασίλευε. Προσεγγιστικοί αλγόριθμοι: Άπληστοι αλγόριθμοι, Η μέθοδος της τιμολόγησης.

Βιβλιογραφία
  • Σχεδιασμός Αλγορίθμων, Jon Kleinberg , Eva Tardos, Εκδόσεις Κλειδάριθμος
  • Aλγόριθμοι, S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Εκδόσεις Κλειδάριθμος
  • Εισαγωγή στους αλγορίθμους, Cormen, Leiserson, Rivest, Stein, Τόμος Ι. Πανεπ. Εκδόσεις Κρήτης