Complexity Theory (ΠΛ1)
Από Wiki Τμήματος Μαθηματικών
- Ελληνική Έκδοση
- Graduate Courses Outlines
- Outline Modification (available only for faculty members)
- Department of Mathematics
- Save as PDF or Print (to save as PDF, pick the corresponding option from the list of printers, located in the window which will popup)
General
| School | School of Science |
|---|---|
| Academic Unit | Department of Mathematics |
| Level of Studies | Graduate |
| Course Code | ΠΛ1 |
| Semester | 1 |
| Course Title | Complexity Theory |
| Independent Teaching Activities | Lectures (Weekly Teaching Hours: 3, Credits: 7.5) |
| Course Type | Elective |
| Prerequisite Courses | - |
| Language of Instruction and Examinations |
Greek |
| Is the Course Offered to Erasmus Students | Yes (in English) |
| Course Website (URL) | See eCourse, the Learning Management System maintained by the University of Ioannina. |
Learning Outcomes
| Learning outcomes |
This course aims at introducing to students the concepts of time and space complexities for solving difficult problems. After successfully passing this course the students will be able to:
|
|---|---|
| General Competences |
|
Syllabus
- ΝΡ and Computational Intractibility
- The class of PSPACE
- Extending the limits of tractability
- Approximation Algorithms
- Local search.
- Randomized algorithms
Teaching and Learning Methods - Evaluation
| Delivery |
Lectures | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Use of Information and Communications Technology |
Use of projector and interactive board during lectures. | ||||||||||
| Teaching Methods |
| ||||||||||
| Student Performance Evaluation |
|
Attached Bibliography
- Computational Complexity, Christos Papadimitriou.
- Computers and Intractability, M. R. Garey and D. S. Johnson.
- J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.