Notes from the NIE-KOP courses. It is still work in progress, but it could be relevant for students also studying for the midterm test or exam test.
Final notes for individual lectures:
- KOP 1. lecture ✅ Combinatorial problems and and algorithms, complexity
- KOP 2. lecture ✅ P and NP classes, polynomial hierarchy of problems
- KOP 3. lecture ✅ NPC and NPH problems, Karp reduction, Turing reduction
- KOP 4. lecture ✅ PO, NPO classes, approximation algorithms, classes APX, PTAS, FPTAS
- KOP 5. lecture ✅ Circuit and communication complexity
- KOP 6. lecture ✅ Randomized algorithms. Experimental evaluation
- KOP 7. lecture ✅ Local methods. State space. Simple local heuristics
- KOP 8. lecture ✅ Simulated annealing
- KOP 9. lecture ✅ Simulated evolution - genetic algorithms
- KOP 10. lecture✅ Simulated evolution - FMGA, genetic programming
- KOP 11. lecture ✅ Tabu Search
- KOP 12. lecture ✅ Global methods
To fully understand the notes and to have the full context, the official slides are needed. I did not capture everything from the slides, I focused on the things the lecturer said and that were not in the slides. I also added some “own” interpretations for better understanding.
If you find a bug or a mistake, let me know! See Disclaimer