Категория
Информатика
Тип
методичка
Страницы
1 стр.
Дата
09.05.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
149440.zip — 56.94 kb
  • teorija-algoritmov_149440_1.rtf — 523.56 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Оценка алгоритмов Mariy
Кафедра : Автоматика и информационные технологии
ТЕОРИЯ АЛГОРИТМОВ
Екатеринбург
2006
Привод и тся
формализация понятия «алгоритм» . Обсуждаются два способа формального описания алгоритма – с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся
меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и
N P ,
алгоритмически неразрешимые проблемы.
Содержание
ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА
Определение
Нормальный алгоритм Маркова
Тезис Маркова
Машина Тьюринга
Основная гипотеза теории алгоритмов (тезис Чёрча)
Универсальная машина Тьюринга
МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ
Оценка алгоритма
Практические и NP-полные алгоритмы
Алгоритмически неразрешимые проблемы
« Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и
N P .
N P – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.
» ( из стандарта специальности ВМКСС, дисциплина «Математическая логика и теория алгоритмов)
ФОPМАЛИЗАЦИЯ



Ваше мнение



CAPTCHA


Отзывы


  • вася

    материал достаточно полный хотелось бы больше практических заданий

    Рейтинг: 0
    Отзыв полезен?   Да  /  Нет