Методы оптимизации, обозначения

Материал из eSyr's wiki.

Перейти к: навигация, поиск

К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается

Сокращения

  • КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
  • ПЧ -- задача распознавания простоты числа (стр. 8)
  • ДМТ -- детерминированная машина Тьюринга (стр. 9)
  • НДМТ -- недетерминированная машина Тьюринга (стр. 9)
  • ЛП -- линейное программирование (стр. 25)
  • озЛП -- основная задача линейного программирования (стр. 25)
  • ЗМП -- задача математического программирования (стр. 39)
  • ЦЛП -- целочисленное линейное программирование (стр. 55)
  • БЛП -- булево линейное программирование (стр. ??)

Математические обозначения

  • Π -- массовая задача (стр. 4)
  • I \in \Pi -- индивидуальная задача (стр. 4)
  • Σ -- алфавит кодирования (стр. 7)
  • e -- кодировка задачи Π (стр. 7)
  • L(Π,e) -- язык задачи (стр. 7)
  • TA(n) -- временная сложность алгоритма A (стр. 8)
  • \overline{\Pi} -- дополнительная задача к массовой задача Π (стр. 12)

Классы сложности задач

  • P -- класс полиномиальных разрешимых задач (стр. 8)
  • NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
  • co-P -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
  • co-NP -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
Получено с http://esyr.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%BE%D0%B1%D0%BE%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F
Личные инструменты
Разделы