Kategorie

Hlavní stránka > Knihy>Справочная литература>Естественные науки>Физико-математические науки>Математика>Общие вопросы математики>Теория алгоритмов и вычислений. Учебное пособие

Теория алгоритмов и вычислений. Учебное пособие

  • Автор: Гашков Сергей Борисович

  • Переплет: твердый
  • Страниц: 168
  • Формат: 24.3x17.5x1.4 см
  • Вес: 348 г
  • ISBN: 978-5-507-46897-3

  • Серия: Компьютеры и программное обеспечение

  • Год издания: 2023

44353960

Dostupnost: odeslání do 9-13 pracovních dnů

1 518 Kč

В первой части дается введение в теорию алгоритмов (часто называемую также теорией вычислимых функций или просто теорией вычислимости). Намечаются разные варианты её построения, основанные на использовании теории рекурсивных функций, машин Тьюринга, Поста и Минского, бесконечного абака, алгорифмов Маркова и экзотического языка Фрактран, предложенного Конвеем. Приводятся классические примеры алгоритмически неразрешимых проблем. Во второй части излагаются основы теории NP-полных задач. Доказывается NP-полнота ряда классических комбинаторных проблем переборного характера, таких как проблема выполнимости логических формул, проблемы коммивояжера, упаковки рюкзака, размена монет, поиска минимального покрытия и максимальной клики и др. Рассматриваются точные и приближенные алгоритмы для решения этих задач.
В конце каждой части приводится список задач, дополняющих ее содержание. К некоторым из них даны указания к решению.
В основу книги положен семестровый курс, читавшийся автором на факультете математики и компьютерных наук Бакинского филиала МГУ им. М. В. Ломоносова.