Основы теории дискретных логических и вычислительных устройств. Шоломов Л. А. — М.: Наука. Главная редакция физико-математической литературы, 1980. — 400 с.
Книга содержит систематическое и вместе с тем доступное изложение результатов по теории дискретных устройств.
Она состоит из трех частей, первая из которых посвящена устройствам с конечной памятью, вторая — алгоритмам и идеализированным моделям вычислительных машин, третья — надежным хранению, передаче и переработке дискретной информации. "Предпочтение отдается конструктивным методам, на основе которых можно производить анализ, синтез и оптимизацию устройства.
Книга является учебным пособием для студентов кибернетических специальностей втузов. Она будет полезной инженерам, имеющим дело с вычислительной техникой и устройствами управления, а также может служить аспирантам и научным работникам для первоначального ознакомления с предметом.
ОГЛАВЛЕНИЕ
Предисловие редактора ................ 5
Предисловие автора ................. 7
Введение ...................... 9
ЧАСТЬ ПЕРВАЯ
Глава I. Логические функции............. 25
§ 1.1. Задание логических функций......... 25
§ 1.2. Некоторые специальные представления логических
функций.................. 32
§ 1.3. Полнота систем логических функций....... 38
§ 1.4. Представление о функциях А-значной логики ... 46
Глава II. Дискретные устройства без памяти....... 48
4 § 2.1. Схемы из логических элементов......... 48
§ 2.2. Синтез схем на основе формул......... 56
§ 2.3. Минимизация логических функций....... 65
§ 2.4. Синтез схем методом декомпозиции....... 85
§ 2.5. Асимптотические методы синтеза схем...... 93
Глава III. Дискретные устройства с конечной памятью . . .110
§ 3.1. Конечные автоматы.............по
§ 3.2. Минимизация автоматов...........119
§ 3.3. Схемы из логических элементов и задержек ... .135 § 3.4. Схемы из автоматных элементов........150
ЧАСТЬ ВТОРАЯ
Глава IV. Модели алгоритмов .... 158
§ 4.1. Машины Тьюринга..............158
§ 4.2. Частично-рекурсивные функции . ....... 171
1 л'л' Эквивалентность моделей алгоритмов......182
I Л' *ниверсальные машины и универсальные функции 193 § 4.t>. Некоторые общие теоремы теории алгоритмов . . .203
Глава V. Вычислительные возможности машин......210
§ 5.1. Алгоритмически неразрешимые проблемы. Метод сводимости ........._ 210
1 ч'ч' *]екот°Рые алгоритмически неразрешимые проблемы 213 S o.j. Неразрешимость проблемы полноты конечной системы автоматов........ 222
§ 5.4. Сложно вычислимые функции •'..'.'.'.'. 229 S 0.5. Универсальные задачи перебора........245
1*
4 ОГЛАВЛЕНИЕ
ЧАСТЬ ТРЕТЬЯ
Глава VI. Помехоустойчивое кодирование........264
§ 6.1. Обшая схема передачи дискретной информации . . 264
§ 6.2. Равномерное кодирование...........268
§ 6.3. Кодовое расстояние и его связь с корректирующей
способностью................276
§ 6.4. Линейные коды...............284
§ 6.5. Циклические коды............. 295
§ 6.6. Эффективное построение кодов с заданной корректирующей способностью (БЧХ-коды) .......307
§ 6.7. Другие типы искажений...........323
§ 6.8. Самокорректирующиеся схемы.........328
Глава VII. Передача дискретной информации при наличии помех ...................333
§ 7.1. Неопределенность и информация........333
§ 7.2. Характеристики системы передачи информации . . .351 § 7.3. Теорема Шеннона о передаче при наличии помех . 356
§ 7.4. Сжатие информации.............369
Литература.................... 389
Указатель обозначений ............... 391
Предметный указатель................394
ПРЕДИСЛОВИЕ РЕДАКТОРА
В последнее время происходит интенсивное внедрение научных методов, средств вычислительной техники и автоматических систем специализированного назначения в сферу управления, организации и планирования. Чтобы удовлетворить все возрастающую в связи с этим потребность в специалистах, во многих вузах страны начата подготовка студентов кибернетического профиля. Для них и студентов других специальностей, соприкасающихся с вычислительной техникой, автоматикой, телемеханикой, связью, в разных объемах и под разными названиями читается курс (или совокупность курсов) по теории дискретных устройств. Туда обычно включаются вопросы из области математической логики, теории синтеза управляющих систем и теории автоматов, теории алгоритмов и теории сложности вычислений, теории информации и теории кодирования. Этот перечень указывает на большой объем и разнообразие относящегося сюда материала и на возникающие в связи с этим трудности в формировании курса.
Образованный специалист, использующий вычислительную технику в своей повседневной деятельности, должен иметь правильное представление о принципиальных возможностях вычислительных машин, о том, что представляет собой свойство универсальности и какие задачи могут решать универсальные машины, с помощью каких средств эти задачи могут быть описаны. Он должен понимать, как может быть формально уточнено интуитивное представление об алгоритме, и знать, что понятие алгоритма обладает большой степенью устойчивости (фактически не зависит от формализации). Специалист-кибернетик должен представлять, какие особенности вычислительных машин являются существенными с точки зрения принципиальных возможностей машин, а какие служат для удобства или убыстрения вычислений, сколь сложными могут быть сами вычисления и какие «сложностньге эффекты» могут при этом иметь место. Необходимо понимание того, что эти свойства являются общими, не зависят от конкретной концепции машины и справедливы как для простейших теоретических моделей, так и для современных ЦВМ и тех машин, которые появятся в будущем.
Цена: 150руб.
