Пособие является частью обязательного курса "Основы кибернетики" и посвящено некоторым вопросам сложности алгоритмов. Излагаются результаты по алгоритмическим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости и NP-полноты, устанавливается связь между временной сложностью вычислений на машинах Тьюринга и сложностью схем. Учебное пособие предназначено для студентов 3-4 курсов факультета
Алгоритмические трудности синтеза схем.
Этот параграф посвящен алгоритмическим трудностям синтеза минимальных схем. Излагается один из первых математических результатов по алгоритмической сложности дискретных задач, полученный С.В.Яблонским в 1959 г. [1]. Суть его состоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми “правильными” алгоритмами непременно связано с построением всех функции алгебры логики. Данное изложение является переработкой части статьи [2]. С целью упрощения доказательство ведется на примере схем из функциональных элементов (сокращенно СФЭ), а не контактных схем, как в оригинале.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Некоторые вопросы сложности алгоритмов, учебное пособие, Сапоженко А.А., 2001 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: Сапоженко :: книги по математике :: математика :: алгоритмы :: кибернетика
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Геометрия, 8 класс, поурочные планы по учебнику Погорелова А.В., Грицаева Н.В., 2006
- Алгебра, 9 класс, углублённый уровень, Мерзляк A.Г., Поляков B.М., 2019
- Математика, 6 класс, Козлов В.В., Никитин А.А., Белоносов B.C., Мальцев А.А., 2016
- Элементы выпуклого и сильно выпуклого анализа, Половинкин Е.С., Балашов М.В., 2007
Предыдущие статьи:
- Краткий курс теории аналитических функций, Маркушевич А.И.
- Математика, Её содержание, методы и значения, Том первый, Александров А.Д., Колмогоров А.Н., Лаврентьев М.А., 1956
- Курс высшей математики, том 4, часть 2, Смирнов В.И., 1981
- Курс высшей математики, том 3, часть 2, Смирнов В.И., 1974