CS341 - Θεωρία πολυπλοκότητας
Bachelor of Science στην Πληροφορική και τις Τεχνολογίες Επιχειρήσεων
Κύριο μάθημα
CS341 - Θεωρία πολυπλοκότητας
Κωδικός Μονάδας Μαθήματος: CS341
Τύπος μονάδας: Πυρήνας
Επίπεδο Μονάδας Μαθήματος: Πρώτος κύκλος
Έτος σπουδών: Τρίτο έτος
Εξάμηνο: Πυρήνας
Αριθμός μονάδων ECTS: 7.5
Ώρες επαφής με το μάθημα: 36
Τρόπος παράδοσης:
Πρόσωπο με πρόσωπο
Προαπαιτούμενα
Στόχοι του μαθήματος
Στόχος αυτού του μαθήματος είναι να εισαγάγει τους φοιτητές στη θεωρία της υπολογιστικής πολυπλοκότητας. Οι φοιτητές θα μάθουν πώς να αναλύουν την πολυπλοκότητα αλγορίθμων και σημαντικές έννοιες σε αυτόν τον τομέα, όπως το πρόβλημα P=NP και το κύριο θεώρημα.
Μαθησιακά αποτελέσματα
- Κατανόηση των βασικών εννοιών της θεωρίας υπολογιστικής πολυπλοκότητας: μηχανές turing και το πρόβλημα του σταματήματος.
- Κατανοήστε τις διάφορες κατηγορίες πολυπλοκότητας, όπως NP και P.
- Κατανοήστε πώς να αναλύετε την πολυπλοκότητα των αλγορίθμων.
- Κατανοήστε πώς να αναλύετε αλγορίθμους διαίρει και βασίλευε και μάθετε πώς να χρησιμοποιείτε το κύριο θεώρημα.
- Εισαγωγή στη θεωρία γραφημάτων και στους αλγορίθμους.
Περιεχόμενο μαθήματος
Χαρακτηριστικά μαθήματος
Προγραμματισμένες μαθησιακές δραστηριότητες και μέθοδοι διδασκαλίας
Διαλέξεις, συζητήσεις και αντιπαραθέσεις εντός της τάξης, ασκήσεις εντός της τάξης, σύνολα προβλημάτων, ομαδική εργασία, μελέτες περιπτώσεων σε βίντεο, ομαδικές παρουσιάσεις, διαδραστική ηλεκτρονική μάθηση μέσω του Moodle (κουίζ, εργασίες, φόρουμ).
Μέθοδοι και κριτήρια αξιολόγησης
10% Συμμετοχή στην τάξη
90% Τελική εξέταση
Γλώσσα διδασκαλίας
Αγγλικά
Αναγνώσεις
Συγγράμματα:
1. Sanjeev Arora και Boaz Barak, Computational Complexity: Cambridge University Press, 2009.
Προαιρετικό βιβλίο:
2. Richard Wilson (2010). Εισαγωγή στη θεωρία γραφημάτων
3. Miklos Bona (2011) A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory: An Introduction to Enumeration and Graph Theory (Third Edition)
English (UK) 
Ελληνικά