Теорія алгоритмів

Лекційних годин: 17 години

Практичних занять: ?? годин

Самостійна робота: ?? годин

3 course (6 term)
Course program: 
  1. Булівська алгебра.
  2. Елементи булівської алгебри. Операції та операнди. Елементарні дії з одним, двома та трьома операндами.
  3. Діаграми Венна, нормальні форми булівської функції. N-арні числа.
  4. Абстрактна абетка.
  5. Задачі алгебри над абстрактною абеткою. Потужність множини бінарних операцій над абстрактною абеткою.
  6. Зображення абстрактної абетки підабеткою N-арних чисел. Впорядкування, логічні операції. Стандартні абетки комп’ютерної алгебри.
  7. Абетка цілих чисел. Зображення від’ємних чисел, доповнення до двійки. Абетка символів, впорядкування, національні абетки. Абетка дійсних чисел, проблеми повноти та впорядкованості.
  8. Обчислювальна машина фон Неймана.
  9. Програма, крок програми, перехід, переходи вперед та назад, цикли. Проблема завершуваності програми.
  10. Розподіл слова на команди та параметри.
  11. Структури даних та задачі пошуку.
  12. Послідовні структури. Класифікація за методом доступу: стек, черга, магазин. Реалізації послідовних структур: послідовність, список. Пошук в послідовній структурі.
  13. Непослідовні структури. Класифікація за зв’язністю: граф, орієнтовний граф, дерево, бінарне дерево. Реалізація бінарного дерева. Пошук в бінарному дереві. Врівноважування бінарного дерева. Реалізація N-арного дерева та методів пошуку на ньому.
  14. Теорія кодування.
  15. Міра інформації, інформація та ентропія. Інформаційні характеристики дискретного джерела інформації, надлишкове кодування. Інформаційні характеристики каналу передачі, надійність каналу. Теореми Шенона.
  16. Оборотні та необоротні коди. Шифрування.

 

Knowledge tests: 

Залік

Literature: 

Основна

  1. Д. Кук, Г. Бейз, Компьютерная математика: пер. с англ., Наука, 1989, 384 с.

Додаткова

  1. Х. Хармут, Применение методов теории информации в физике: пер. с англ., Наука, 1989, 344 с.
  2. С.В. Яблонский, Введение в дискретную математику: Наука, 1979, 272 с.