Головна

Основи аналізу алгоритмів.

  1.  I. Якісні методи системного аналізу.
  2.  I. Методологічні основи менеджменту.
  3.  II. Дидактичні основи курсу
  4. " Основи екології та економіка природокористування "як міжгалузева навчальна дисципліна. Предмет і методологія курсу
  5.  А) Критерії аналізу продажів товару
  6.  Алгоритм аналізу родоводу
  7.  Алгоритм кореляційно-регресійного аналізу парної зв'язку

Алгоритми і аналіз складності

Зміст курсу (з1)

Введення в теорію алгоритмів. Основи теорії обчислюваності.

Історія виникнення теорії алгоритмів. Визначення поняття "Алгоритм", основні вимоги, що пред'являються до алгоритму. Класифікації алгоритмічних моделей. Машина Поста. Машина Тьюринга. Опис, способи завдання, особливості програмування машин Тьюринга (МТ). Основні операції над МТ, доказ теореми про існування універсальної МТ.

Введення в теорію рекурсивних функцій. Визначення, приклади і способи завдання рекурсивних функцій, формулювання і доказ відповідних теорем.

Нормальні алгоритми Маркова.

Визначення обчислюваності. Розв'язні і нерозв'язні проблеми. Невичіслімие функції, проблема зупинки. Застосування невичіслімості.

Введення в теорію кінцевих автоматів (КА). Формальне визначення КА, способи завдання, приклади. Властивості і варіанти кінцевих автоматів (КА). Контекстно-вільні граматики. Визначення поняття формального мови, граматика мови, мову граматики. Класифікація формальних граматик по Хомського.

Основи аналізу алгоритмів.

Асимптотический аналіз верхньої і середньої оцінок складності алгоритмів; порівняння найкращих, середніх і найгірших оцінок; O-, o-, ?- і ?-нотації; стандартні класи складності; емпіричні вимірювання ефективності алгоритмів; накладні витрати алгоритмів по часу і пам'яті; рекурентні співвідношення та аналіз рекурсивних алгоритмів.



 Аналіз конструкції деталі |  Стратегії алгоритмів.

 Введення в теорію алгоритмів. |  Основні типи алгоритмічних моделей. (С8) |  Машина Поста. |  Машина Поста складається з (с11) |  Практичні завдання. |  Машина Тьюринга. |  Граф переходів |  Визначення обчислюваності по Тьюрингу. (С25) |  Приклади (С27-С29) |  Послідовна композиція МТ. (С30-С31) |

© um.co.ua - учбові матеріали та реферати