Перейти к содержимому 
База данных: ЭБС Лань
Страница 1, Результатов: 1
Отмеченные записи: 0
1.
Подробнее
Гашков, С. Б.
Теория алгоритмов и вычислений : учебное пособие для вузов / С. Б. Гашков. - Санкт-Петербург : Лань, 2023. - 168 с. . - ISBN 978-5-507-46897-3
Книга из коллекции Лань - Информатика
ББК 22.12я73
Рубрики: Информатика--Алгоритмизация--Лань
Кл.слова (ненормированные):
машины тьюринга -- машины поста -- алгоритмы минского -- фрактран -- np-полные задачи -- вычисления на абаке
Аннотация: В первой части дается введение в теорию алгоритмов (часто называемую также теорией вычислимых функций или просто теорией вычислимости). Намечаются разные варианты её построения, основанные на использовании теории рекурсивных функций, машин Тьюринга, Поста и Минского, бесконечного абака, алгорифмов Маркова и экзотического языка Фрактран, предложенного Конвеем. Приводятся классические примеры алгоритмически неразрешимых проблем. Во второй части излагаются основы теории NP-полных задач. Доказывается NP-полнота ряда классических комбинаторных проблем переборного характера, таких как проблема выполнимости логических формул, проблемы коммивояжера, упаковки рюкзака, размена монет, поиска минимального покрытия и максимальной клики и др. Рассматриваются точные и приближенные алгоритмы для решения этих задач. В конце каждой части приводится список задач, дополняющих ее содержание. К некоторым из них даны указания к решению. В основу книги положен семестровый курс, читавшийся автором на факультете математики и компьютерных наук Бакинского филиала МГУ им. М. В. Ломоносова.
Гашков, С. Б.
Теория алгоритмов и вычислений : учебное пособие для вузов / С. Б. Гашков. - Санкт-Петербург : Лань, 2023. - 168 с. . - ISBN 978-5-507-46897-3
Книга из коллекции Лань - Информатика
| УДК |
Рубрики: Информатика--Алгоритмизация--Лань
Кл.слова (ненормированные):
машины тьюринга -- машины поста -- алгоритмы минского -- фрактран -- np-полные задачи -- вычисления на абаке
Аннотация: В первой части дается введение в теорию алгоритмов (часто называемую также теорией вычислимых функций или просто теорией вычислимости). Намечаются разные варианты её построения, основанные на использовании теории рекурсивных функций, машин Тьюринга, Поста и Минского, бесконечного абака, алгорифмов Маркова и экзотического языка Фрактран, предложенного Конвеем. Приводятся классические примеры алгоритмически неразрешимых проблем. Во второй части излагаются основы теории NP-полных задач. Доказывается NP-полнота ряда классических комбинаторных проблем переборного характера, таких как проблема выполнимости логических формул, проблемы коммивояжера, упаковки рюкзака, размена монет, поиска минимального покрытия и максимальной клики и др. Рассматриваются точные и приближенные алгоритмы для решения этих задач. В конце каждой части приводится список задач, дополняющих ее содержание. К некоторым из них даны указания к решению. В основу книги положен семестровый курс, читавшийся автором на факультете математики и компьютерных наук Бакинского филиала МГУ им. М. В. Ломоносова.
Страница 1, Результатов: 1