Информатика (программирование)
Информатика и вычислительная техника
  • формат pdf
  • размер 4,78 МБ
  • добавлен 1 апреля 2015 г.
Орлов С.А. Теория и практика языков программирования
Учебник для вузов. Стандарт 3-го поколения. — СПб. : Питер, 2013. — 688 с. : ил. — ISBN 978-5-496-00032-1.
Учебник посвящен систематическому изложению теории и практики языков программирования. Он отражает классическое содержание учебной дисциплины по языкам программирования. Все сложные вопросы поясняются законченными примерами. Кроме того, здесь предлагается полный комплекс задач и упражнений по узловым вопросам. В российских стандартах третьего поколения (компьютерного направления) учебник охватывает базисные разделы следующих дисциплин: теория формальных языков, теория автоматов и формальных языков, языки программирования, программирование, объектно-ориентированное программирование, логическое и функциональное программирование, теория вычислительных процессов.
Учебник предназначен для студентов инженерного, бакалаврского и магистерского уровней компьютерных специальностей, может быть полезен преподавателям и исследователям/разработчикам трансляторов и другого программного обеспечения.
Рекомендовано Санкт-Петербургским институтом информатики и автоматизации Российской академии наук (СПИИРАН) в качестве учебника по направлению «Информатика и вычислительная техника».
Введение.
Благодарности.
Определение и проблемы языков программирования.
Для чего нужно изучать принципы построения языков программирования.
Аппарат абстракции-конкретизации.
Исходное определение языка программирования.
Практическое определение языка программирования.
Технологическое определение языка программирования.
Области применения языков программирования.
Научные вычисления.
Обработка деловой информации.
Искусственный интеллект.
Системная область.
Веб-обработка.
Критерии эффективности языков программирования.
Читабельность.
Легкость создания программ.
Надежность.
Стоимость.
Способы построения критериев эффективности.
Нормализация частных показателей.
Учет приоритета частных показателей.
Заключительные замечания.
Контрольные вопросы и упражнения.
Виртуальные машины и трансляция языков.
Аппаратная организация компьютеров.
Принцип программного управления.
Структура виртуальной машины.
Порядок функционирования виртуальной машины.
Понятие виртуальной машины.
Трансляторы и интерпретация.
Иерархия виртуальных машин.
Этапы трансляции.
Анализ исходной программы.
Синтез объектной программы.
Контрольные вопросы.
Виды языков программирования.
Парадигмы программирования.
Императивные языки программирования.
Язык Fortran.
Язык C.
Функциональные языки программирования.
Язык LISP.
Логические языки программирования.
Язык Prolog.
Объектно-ориентированные языки программирования.
Язык Smalltalk.
Язык разметки HTML.
Скриптовые языки.
Общие характеристики скриптовых языков.
Язык Perl.
Язык JavaScript.
Язык PHP.
Язык Python.
Язык Ruby.
Язык Lua.
Гибридные языки разметки/программирования.
Язык XSLT.
Язык JSP.
Контрольные вопросы и упражнения.
Выражения и присваивания в языках программирования.
Нотации выражений.
Префиксная нотация выражения.
Постфиксная нотация выражения.
Инфиксная нотация выражения.
Смешанная нотация.
Сравнение нотаций для записи выражений.
Присваивание.
Порядок вычисления операндов в выражении.
Контрольные вопросы и упражнения.
Действия и операторы в программах.
Базовые операторы.
Операторы перехода.
Поток управления.
Составные операторы.
Условные операторы.
Вложенность условных операторов.
Операторы выбора.
Организация повторения операторов.
Операторы цикла с заданным числом повторений.
Оператор for языка Python.
Циклы с заданным числом повторений в функциональных языках.
Операторы цикла без заданного числа повторений.
Бесконечные циклы и механизмы управления ими.
Циклы с предусловием.
Циклы с постусловием.
Универсальность оператора for в языках С, С++, C# и Java.
Охраняемые структуры управления Дейкстры.
Инварианты.
Программирование с инвариантами.
Контрольные вопросы и упражнения.
Средства представления синтаксиса языков программирования.
Особенности определения языка программирования.
Качество синтаксиса языка.
Легкость чтения.
Легкость написания.
Легкость трансляции.
Отсутствие неоднозначности.
Синтаксические элементы языка.
Набор символов.
Идентификаторы.
Константы и литералы.
Символы операций.
Ключевые и зарезервированные слова.
Необязательные слова.
Комментарии.
Пробелы.
Разделители и скобки.
Выражения.
Операторы.
Лексемы и лексический синтаксис.
Абстрактный синтаксис и абстрактные синтаксические деревья.
Грамматики в языках программирования.
Контекстно-свободная грамматика.
Форма Бэкуса—Наура (BNF).
Деревья разбора.
Синтаксическая неоднозначность.
Неоднозначность повисшего Else.
Выводы — линейная форма грамматического разбора.
Списки в инфиксных выражениях.
Переход к конкретному синтаксису.
Обработка ассоциативности и приоритетности.
Расширенная BNF.
Синтаксические схемы.
Точки с запятой и пустые операторы.
Контрольные вопросы и упражнения.
Формальная семантика языков программирования.
Семантика языка программирования.
Синтезируемые атрибуты.
Порядок вычислений.
Выводы.
Атрибутные грамматики.
Операционная семантика.
Аксиоматическая семантика.
Аксиома присваивания.
Применение аксиомы присваивания.
Правило консеквенции (упрощения).
Правило вывода для последовательности.
Применение правила вывода для последовательности.
Правило вывода для условного оператора.
Применение правила вывода для условного оператора.
Вычисление предусловия для цикла FOR.
Правило вывода для оператора цикла WHILE.
Требования к инварианту цикла.
Определение инварианта цикла по индукции.
Пример доказательства цикла.
Общий случай определения инварианта цикла.
Денотационная семантика.
Семантическая функция отображения двоичных чисел.
Семантическая функция отображения десятичных чисел.
Состояние программы.
Выражения.
Операторы присваивания.
Логические циклы с предусловием.
Контрольные вопросы и упражнения.
Типизация данных.
Объекты данных.
Переменные и константы.
Типы данных.
Элементарные типы данных.
Объявления.
Статический контроль типов.
Динамический контроль типов.
Обзор составных типов данных.
Системы типизации данных.
Атрибуты переменной.
Связывание.
Динамическое связывание типов.
Время жизни.
Тип выражения.
Контрольные вопросы и упражнения.
Скалярные типы данных.
Перечисления.
Целые и вещественные типы.
Десятичные числа.
Поддиапазоны.
Логический тип.
Символьные типы.
Стиль программирования в языке С. Преобразование типов.
Контрольные вопросы и упражнения.
Составные типы данных.
Массивы.
Разновидности массивов.
Инициализация массива.
Атрибуты и операции простого массива.
Операции над массивами в скриптовых языках.
Прямоугольные массивы и массивы массивов.
Сечения массивов.
Статические массивы языка С.
Ассоциативные массивы.
Строки символов.
Записи.
Записи и массивы со вложенными структурами.
Сравнение массивов и записей.
Объединения и вариантные записи.
Вариантные записи ослабляют надежность типов?
Множества.
Кортежи.
Списки.
Контрольные вопросы и упражнения.
Указатели.
Основные понятия.
Операции над указателями в языке Pascal.
Динамические связные структуры данных.
Повисшие указатели и утечки памяти.
Безопасность указателей в Паскале.
Указатели как посредники.
Перестановка указателей и перемещение данных.
Указатели в языке Ada.
Массивы и указатели в языках С и С++.
Динамическое распределение памяти.
Гибкость указателей в языке С.
Ссылочный тип.
Реализация указателей.
Контрольные вопросы и упражнения.
Преобразования типов данных.
Эквивалентность типов данных.
Преобразование типа и явное приведение.
Явные приведения типа в языке С++.
Оператор static_cast.
Оператор const_cast.
Оператор reinterpret_cast.
Оператор dynamic_cast.
Совместимость типов и неявное приведение.
Уровень типизации языка.
Контрольные вопросы и упражнения.
Подпрограммы.
Разновидности подпрограмм.
Объявление подпрограммы.
Вызов подпрограммы.
Рекурсия — множественные выполнения подпрограммы.
Преимущества подпрограмм.
Методы передачи параметров.
Передача параметров по значению.
Передача параметров по ссылке.
Эффект передачи параметров по ссылке с помощью указателей языка С.
Передача по значению-результату.
Передача по результату.
Правила области видимости для имен.
Статическая область видимости и переименование локальных переменных.
Макрорасширение и динамическая область видимости.
Конфликты именования.
Передача параметров — текстуальная подстановка.
Передача параметров по имени и статическая область видимости.
Реализация методов передачи параметров.
Методы передачи параметров в популярных языках программирования.
Проверка типов параметров.
Массивы в качестве параметров.
Подпрограммы в качестве параметров.
Проверка типов параметров при вызовах подпрограммы.
Организация области видимости для выполнения переданной подпрограммы.
Типы возвращаемых значений.
Количество возвращаемых значений.
Побочные эффекты функций.
Полиморфизм в языках программирования.
Параметрический полиморфизм.
Полиморфизм включения или полиморфизм подтипов.
Перегрузка и неявное приведение.
Реализация полиморфизма.
Перегруженные подпрограммы.
Родовые подпрограммы.
Родовые подпрограммы в языке Ada.
Родовые подпрограммы в языке С++.
Родовые методы в языке Java.
Родовые методы в языке C#.
Родовые функции в языке F#.
Замыкания.
Контрольные вопросы и упражнения.
Управление подпрограммами.
Вложенные области видимости объявлений.
Связывания при выполнении подпрограмм.
Поток управления между активациями подпрограмм.
Деревья активации.
Формат записи активации.
Размещение и освобождение в куче.
Повторное использование свободного пространства.
Уплотнение свободного пространства.
Фрагментация памяти в куче.
Размещение и освобождение в стеке.
Размещение статических переменных в период компиляции.
Управление подпрограммами в языке С.
Управление подпрограммами в языке Pascal.
Дисплеи для быстрого доступа к информации.
Контрольные вопросы и упражнения.
Абстрактные типы данных.
Абстракция процесса.
Инкапсуляция и абстракция данных.
Абстрактные типы данных.
АТД в языке Ada.
АТД в языке С++.
АТД в языке Java.
АТД в языке C#.
АТД в языке Ruby.
Параметрический полиморфизм в АТД.
Родовые АТД в языке Ada.
Классы-шаблоны в языке С++.
Родовые классы в языке Java.
Родовые классы в языке C#.
Синтаксические контейнеры для множества типов.
Контейнеры в языке C.
Контейнеры в языке C++.
Пакеты языка Ada.
Сборки языка C#.
Пространства имен.
Пространства имен в языке C++.
Пакеты в языке Java.
Пространства имен в языке Ada.
Модули в языке Ruby.
Контрольные вопросы и упражнения.
Объектно-ориентированное и аспектно-ориентированное программирование.
Основные понятия объектно-ориентированного подхода к программированию.
Классы.
Отношения между классами.
Деревья наследования классов.
Объекты.
Отношения между объектами.
Возможности наследования и полиморфизм.
Природа наследования.
Иерархия наследования в различных языках.
Принцип подстановки Барбары Лисков.
Корректность наследования.
Переопределение и виртуальные методы.
Интерфейсы и абстрактные классы.
Формы наследования.
Вариации на тему наследования.
Сообщения и объекты.
Синтаксис пересылки сообщений.
Сообщения в языках со статической и динамической типизацией.
Доступ к получателю внутри метода.
Создание объектов и конструкторы.
Связывание сообщения и метода.
Переопределение методов.
Замещение методов.
Уточнение методов.
ООП на языке С++.
Единичное наследование.
Множественное наследование.
Динамическое связывание.
ООП на языке Ада.
Расширяемые типы.
Классы.
Абстрактные классы и интерфейсы.
Надклассовые типы.
Наследование от родового класса.
ООП на языке Java.
Единичное наследование.
Смешанное наследование.
Вложенные классы.
ООП на языке C#.
Наследование.
Динамическое связывание.
Вложенные классы.
ООП на языке Ruby.
Наследование.
Динамическое связывание.
Реализация объектно-ориентированных классов и объектов.
Организация памяти для сохранения объекта.
Динамическое связывание сообщений с методами.
Особенности аспектно-ориентированного подхода.
Базовые понятия АОП.
Аспекты.
Жизнь без аспектов.
Жизнь с аспектами.
Программирование на аспектно-ориентированном языке AspectJ.
Конструкции пересечения языка AspectJ.
Альтернативный синтаксис @AspectJ.
Контрольные вопросы и упражнения.
Аппарат исключений.
Характеристика исключений.
Этапы работы с определяемыми исключениями.
Потоки управления при обработке исключений.
Многоуровневая система исключений.
Обработка исключений в языке С++.
Связывание исключений с обработчиками.
Оформление функций в С++.
Обработка исключений в языке Java.
Классы исключений.
Обработчики исключений.
Связывание исключений с обработчиками.
Секция finally.
Обработка исключений в языке C#.
Контрольные вопросы и упражнения.
Ввод-вывод и файлы.
Характеристика аппарата ввода-вывода.
Пакеты ввода-вывода языка Ада.
Процедуры ввода языка Ада.
Процедуры вывода языка Ада.
Организация файлов и средства управления ими.
Текстовые файлы.
Двоичные файлы последовательного доступа.
Двоичные файлы прямого доступа.
Потоки ввода-вывода.
Объектно-ориентированный ввод-вывод в языке C++.
Потоковая библиотека ввода-вывода.
Стандартные потоки.
Форматирование потоков.
Ошибки потоков.
Файловые потоки.
Строковые потоки.
Контрольные вопросы и упражнения.
Основные понятия параллельного программирования.
Процессы и потоки.
Задачи языка Ада.
Синхронизация процессов на основе разделяемых переменных.
Семафоры.
Мониторы.
Защищенные объекты.
Синхронизация процессов на основе сообщений.
«Развязка» взаимодействия задач при рандеву.
Селективный прием selective accept.
Временной вызов входа.
Условный вызов входа.
Асинхронный отбор.
Потоки языка Java.
Класс Thread.
Приоритеты.
Семафоры.
Синхронизация конкуренции.
Синхронизация взаимодействия.
Неблокирующая синхронизация.
Явная блокировка.
Потоки в C#.
Основные операции над потоками.
Синхронизация потоков.
Контрольные вопросы и упражнения.
Функциональное программирование.
Особенности функциональных языков программирования.
Выводы.
Язык Scheme — классический функциональный подход.
Выражения языка Scheme.
Специальные формы.
Создание функций.
Динамическая проверка типа.
Хвостовая и не хвостовая рекурсия.
Структуры данных в языке Scheme.
Программирование в языке Scheme.
Функции высшего порядка.
Статическая область видимости.
Настройка — специализация языка Scheme.
Язык ML — функциональный подход со статической типизацией.
Функции и величины языка ML.
Списки в языке ML.
Проверка типов в языке ML.
Ввод и вывод в языке ML.
Типы данных.
Функции высшего порядка и карризация.
Отложенные вычисления.
Нестрогие функции.
Специальные формы для отложенных вычислений.
Ленивые вычисления.
Контрольные вопросы и упражнения.
Логическое программирование.
Исчисление предикатов.
Компоненты исчисления предикатов первого порядка.
Запись утверждений в исчислении предикатов.
Правила вывода исчисления предикатов первого порядка.
Специфика логического программирования.
Формулы Хорна.
Резолюция и унификация.
Язык Prolog.
Нотация и структуры данных.
Выполнение в среде языка Prolog.
Арифметика.
Унификация.
Стратегия поиска в языке Prolog.
Циклы и структуры управления.
Проблемы языка Prolog.
Проблема проверки вхождения при унификации.
Проблема замкнутого мира.
Проблема логического отрицания.
Формулы Хорна не выражают всю логику утверждений.
Информация управления в логическом программировании.
Контрольные вопросы и упражнения.
Заключение.
Список литературы.
Алфавитный указатель.