Некоторые вопросы сложности алгоритмов, учебное пособие, Сапоженко А.А., 2001

Некоторые вопросы сложности алгоритмов, Учебное пособие, Сапоженко А.А., 2001.

Пособие является частью обязательного курса "Основы кибернетики" и посвящено некоторым вопросам сложности алгоритмов. Излагаются результаты по алгоритмическим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости и NP-полноты, устанавливается связь между временной сложностью вычислений на машинах Тьюринга и сложностью схем. Учебное пособие предназначено для студентов 3-4 курсов факультета

Некоторые вопросы сложности алгоритмов, Учебное пособие, Сапоженко А.А., 2001


Алгоритмические трудности синтеза схем.
Этот параграф посвящен алгоритмическим трудностям синтеза минимальных схем. Излагается один из первых математических результатов по алгоритмической сложности дискретных задач, полученный С.В.Яблонским в 1959 г. [1]. Суть его состоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми “правильными” алгоритмами непременно связано с построением всех функции алгебры логики. Данное изложение является переработкой части статьи [2]. С целью упрощения доказательство ведется на примере схем из функциональных элементов (сокращенно СФЭ), а не контактных схем, как в оригинале.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Некоторые вопросы сложности алгоритмов, учебное пособие, Сапоженко А.А., 2001 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу



Скачать - pdf - Яндекс.Диск.

Дата публикации:





Теги: :: :: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 

Книги, учебники, обучение по разделам




Не нашёл? Найди:





2024-11-21 15:51:56