Борисенко В.В. Основы программирования

Учебное пособие. — М.: Интернет-университет Информационных Технологий (Интуит), 2005. — 328 с. — (Основы информатики и математики). — ISBN 5-9556-0039-6.Основой книги является курс программирования, который на протя­жении многих лет читается на механико-математическом факультете МГУ. Главные идеи курса принадлежат А.Г. Кушниренко и Г.В. Лебедеву, они содержатся в книге Кушниренко А.Г., Лебедев Г.В. Программирование для математиков . Особенность курса заключается в том, что не придается большого значения изучению конкретных языков программирования — скорее, он посвящен общим принципам программирования, следовать которым можно, работая в любой языковой среде.
Курс предназначен для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т.п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т.п. Приводятся примеры записи программ как на виртуальном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рассмотрены аппаратные средства поддержки многозадачности.
Значительная часть курса посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисление корня функции, приведение матрицы к ступенчатому виду методом Гаусса, работа с файлами и текстами и т.п.
Последние лекции посвящены структурам данных и их реализациям. Рассматриваются структуры последовательного и прямого доступа, такие как стек, очередь, список, дерево, множество и нагруженное множество, а также их непрерывные и ссылочные реализации. Значительное место уделено реализациям множества с помощью бинарного поиска, на базе сбалансированных деревьев и с помощью хеш-функции.
Курс полезен студентам и преподавателям ВУЗов.Общее понятие алгоритма.
Алгоритмические языки.
Управляющие конструкции алгоритмического языка.
Понятие переменной.
Типы переменных.
Примеры алгоритмов.
Устройство компьютера.
Оперативная память.
Процессор.
Аппаратный стек.
RTL: машинно-независимый Ассемблер.
Внешние устройства и аппаратные прерывания.
Виртуальная память и поддержка параллельных задач.
Основы языка СИ.
Структура Си-программы.
Функции.
Типы переменных.
Выражения.
Управляющие конструкции.
Пример: вычисление квадратного корня методом деления отрезка пополам.
Представление программы в виде функций.
Работа с памятью.
Структуры.
Технология программирования на СИ.
Структуры данных.
Общее понятие структуры данных.
Массив как базовая структура.
Реализация одних структур на базе других.
Простейшие структуры данных. Стек. Очередь.
Ссылочные реализации структур данных.
Множество.
Задачи по теме «Структуры данных».
Литература.
Предметный указатель.