Введение в теорию вычислительных процессов и структур, Кузьмин Е.В., 2006

Введение в теорию вычислительных процессов и структур, Кузьмин Е.В., 2006.

   В пособии в рамках теории вычислительных процессов и структур рассматриваются два направления теоретической информатики (теоретического программирования): теория схем программ и теория семантики и верификации программ. В первом разделе излагаются основы теории (стандартных) схем программ, математических моделей, отражающих взаимодействие информационных и логических структур программы Даются основные понятия теории, описываются её главные проблемы и результаты, ставшие классическими. Во введении в теорию семантики и верификации программ основное внимание уделяется формальному доказательству корректности программ, написанных на языках высокого уровня.
Пособие предназначено для студентов старших курсов, обучающихся по специальности 010503 Математическое обеспечение и администрирование информационных систем (дисциплина «Теория вычислительных процессов и структур», блок ДС), очной формы обучения. Может также быть использовано магистрантами и аспирантами, специализирующимися в области информатики и прикладной математики.




Схемы программ.
Программа выступает как промежуточное звено при общении человека с вычислительной машиной, связывая поставленную задачу с процессом поиска её решения на машине. Будучи посредником между задачей и машиной, программа задаёт некоторую механическую процедуру решения задачи, являясь одним из способов задания алгоритма. Поэтому программа обладает всеми общими свойствами алгоритмов: является конструктивным объектом; работает конечное время для тех наборов исходной информации, для которых вычисляемая функция определена; для программ характерны массовость (применимость ко множеству разных начальных данных) и однозначность.

Программа определяет алгоритм решения задачи (алгоритм нахождения значений функции), генерируя последовательность действий машины. Каждое из этих действий осуществляет некоторый шаг преобразования данных и вызывается соответствующими синтаксическими конструкциями языка. Каждая отдельная конструкция и их совокупность несут определённую смысловую нагрузку. Смысл языковых конструкций и всей программы в целом — семантическая программа. Основные проблемы как практического программирования, так и теории схем программ связаны с семантикой программ, с изучением и использованием тех свойств и преобразований, которые сохраняют семантику и инвариантны к синтаксису программы.

ОГЛАВЛЕНИЕ.
Глава 1. Введение в теорию схем программ.
1.1. Вычислимые функции и машины Тьюринга.
1.2. Пример машины Тьюринга.
1.3. Разрешимые и неразрешимые проблемы.
1.3.1. Массовые алгоритмические проблемы.
1.3.2. Проблема остановки.
1.3.3. Проблема пустой ленты и метод сведения.
1.3.4. Проблема зацикливания.
1.4. Стандартные схемы программ.
1.4.1. Схемы программ.
1.4.2. Класс стандартных схем.
1.4.3. Эквивалентность и главные свойства стандартных схем.
1.5. Неразрешимые свойства стандартных схем.
1.5.1. Двухголовочные автоматы.
1.5.2. Двоичный двух головочный автомат.
1.5.3. Моделирование двоичного автомата стандартной схемой.
1.5.4. Теоремы о неразрешимых свойствах стандартных схем.
1.6. Логико-термальная эквивалентность.
1.6.1. Определение.
1.6.2. Информационные маршруты, зацепленность и влияние.
1.6.3. Система эквивалентных преобразований ∑лт.
Глава 2. Введение в теорию семантики и верификации программ.
2.1. Использование утверждений для документирования программ.
2.1.1. Спецификации программ.
2.1.2. Представление начальных и конечных значений переменных.
2.1.3. Наброски доказательств.
2.2. Семантика простого языка программирования.
2.2.1. Преобразователь предикатов wp.
2.2.2. Команды skip, abort и композиция команд.
2 2.3. Команда присаивания.
2.2.4. Команда выбора.
2.2.5. Команда повторения.
2.3. Построение программ.
2.3.1. Стратегия построения команд выбора.
2.3.2. Построение циклов, исходя из инвариантов и ограничений.
2.3.3. Построение инвариантов.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в теорию вычислительных процессов и структур, Кузьмин Е.В., 2006 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по информатике :: информатика :: компьютеры :: Кузьмин