Algorithms and Models of Computing

Major: Computer Engineering
Code of subject: 6.123.00.O.128
Credits: 6.00
Department: Specialized Computer Systems
Semester: 4 семестр
Mode of study: денна

Algorithms and Models of Computing

Major: Computer Engineering
Code of subject: 6.123.00.O.127
Credits: 6.00
Department: Electronic Computing Machines
Lecturer: senior lecturer Nazar Kozak
Semester: 4 семестр
Mode of study: денна
Learning outcomes: Theoretical knowledge: 1) knowledge of the basic concepts of the theory of algorithms; 2) knowledge of the principles of Posta machine operation; 3) knowledge of the principles of the Turing machine; 4) knowledge of the theory of computational complexity. Practical skills: 1) be able to develop algorithms; 2) be able to develop recursive algorithms; 3) be able to program algorithms; 4) analyze algorithms; 5) perform modeling of Turing machines.
Required prior and related subjects: Discrete mathematics Programming part 1 (Fundamentals of algorithmization and programming) Programming Part 2 (Object Oriented Programming)
Summary of the subject: Introduction to the theory of algorithms. Post machine. Turing machine. Introduction to the analysis of algorithms. Labor intensity of algorithms and their time estimates. Theory of computational complexity and classes of problem complexity. An example of a complete analysis of the algorithm for solving the sum problem. Recursive functions and algorithms. Recursive algorithms and methods of their analysis. Direct analysis of the recursive call tree.
Assessment methods and criteria: Execution and defense of laboratory and practical works: 30. Examination control: 70 (written component: 60, oral component: 10).
Recommended books: 1. Ахо, А. Структуры данных и алгоритмы / Ахо А., Хопкрофт Дж., Ульман Дж. – М.: Издательский дом «Вильямс», 2001. –384 с. 2. Вирт Н. Алгоритмы и структуры данных / Н. Вирт – 2-ое изд., испр. – СПб.: Невский диалект, 2001. – 352 с. 3. Карпов, Ю.Г. Теория автоматов / Ю.Г. Карпов – СПб.: Питер, 2002. – 224 с. 4. Кнут, Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. / Д. Кнут. Уч. пос. – М.: Изд. дом "Вильямс", 2001. – 385 с. 5. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест – М.: МЦНМО, 2001. – 960 с. 6. Макконнел Дж. Анализ алгоритмов. Вводный курс / Макконнел Дж. – М.: Техносфера, 2002. –304 с. 7. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков – СПб.: Питер, 2001. – 304 с. 8. Романовский, И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике / И.В. Романовский – Издание 2-ое, исправленное. – СПб.; Невский диалект, 2000. – 240 с. 9. Чмора, А.Л. Современная прикладная криптография / А.Л. Чмора – М.: Гелиос АРВ, 2001.