Основы программирования. Борисенко
.pdfУДК 004.4(075.8)
ББК 32.973.26-018я73
Б-82
МБорисенко В.В.
Основы программирования : [учеб. пособие] / В. В. Борисенко; Интернет ун - т информ. технологий. - М. : Интернет - ун-т информ. технологий, 2005. - 328 с. - (Основы информатики и математики). - ISBN 5-9556-0039-6.
Книга предназначена для обучения основам программирования. Рассматривают ся основные понятия программирования - алгоритма, исполнителя, алгоритмиче ского языка, переменной, основные типы данных, управляющие конструкции ал горитмического языка и т.п. Излагаются общие приемы программирования, осно¬ ванные на применении математики, такие, как вычисление функций на последо¬ вательностях с помощью применения теории индуктивных функций и схема по строения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т.п. Приводятся примеры записи программ как на вирту альном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рас смотрены аппаратные средства поддержки многозадачности.
Значительная часть книги посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисле ние корня функции, приведение матрицы к ступенчатому виду методом Гаусса, ра¬ бота с файлами и текстами и т.п.
Заключительная глава посвящена структурам данных и их реализациям. Рассмат риваются структуры последовательного и прямого доступа, такие как стек, оче редь, список, дерево, множество и нагруженное множество, а также их непрерыв ные и ссылочные реализации. Значительное место уделено реализациям множеста с помощью бинарного поиска, на базе сбалансированнных деревьев и с помо щью хеш-функции.
Книга полезна студентам и преподавателям ВУЗов.
ISBN 5-9556-0039-6
©Текст В.В. Борисенко, 2005
©Оформление Интернет-университет информационных технологий, 2005
ОСНОВЫ ИНФОРМАТИКИ И МАТЕМАТИКИ
Серия издается совместно
МОСКОВСКИМ ГОСУДАРСТВЕННЫМ УНИВЕРСИТЕТОМ имени М.В.Ломоносова
и
И н т е р н е т - У н и в е р с и т е т о м И н ф о р м а ц и о н н ы х Т е х н о л о г и й
при поддержке корпорации Microsoft
Главный редактор серии: A. В. Михалев
Редакционная коллегия: В.В. Борисенко
B.С. Л ю ц а р е в
И.В. Машечкин A. А . Михалев Е.В. Панкратьев
А. М . Ч е п о в с к и й B. Г. Ч и р с к и й А . В . Ш к р е д
Информация о серии
Серия учебных пособий по информатике и ее математическим осно вам открыта в 2005 г. с целью современного изложения широкого спектра направлений информатики на базе соответствующих разделов математи ческих курсов, а также примыкающих вопросов, связанных с информаци онными технологиями.
Особое внимание предполагается уделять возможности использовать материалы публикуемых пособий в преподавании информатики и ее мате¬ матических основ для непрофильных специальностей. Редакционная кол легия также надеется представить вниманию читателей широкую гамму практикумов по информатике и ее математическим основам, реализую¬ щих основные алгоритмы и идеи теоретической информатики.
Выпуск серии начат при поддержке корпорации Microsoft в рамках междисциплинарного научного проекта МГУ имени М.В. Ломоносова.
ПРЕДИСЛОВИЕ
Основой книги является курс программирования, который на протя жении многих лет читается на механико-математическом факультете МГУ. Главные идеи курса принадлежат А. Г. Кушниренко и Г. В. Лебедеву, они со держатся в книге [3]. Особенность курса заключается в том, что не прида ется большого значения изучению конкретных языков программирования
— скорее, он посвящен общим принципам программирования, следовать которым можно, работая в любой языковой среде. Основным понятием курса является понятие исполнителя, которое соответствует понятию клас са в объектно-ориентированных языках. Большое внимание уделяется ме тодам разработки объемных проектов, в частности, реализации исполните ля на основе нижестоящих «базовых» исполнителей и технологии «сверху вниз». Поскольку курс предназначен студентам-математикам, в нем после довательно применяется математический подход к программированию. Например, рассматривается схема вычисления функций на последователь ностях (таких как вычисление суммы или максимума последовательности, вычисление значения многочлена в заданной точке по последовательности его коэффициентов и т.п.), основанная на применении теории индуктив ных функций и индуктивных расширений. Излагаются простейшие спосо¬ бы доказательства правильности программ по их тексту. Наиболее важны¬ ми из них является явная формулировка утверждений в различных точках программы и схема построения цикла «пока» с помощью инварианта. Зна чительная часть курса посвящена структурам данных и их реализациям. Те оретический материал курса иллюстрируется практическими проектами небольшого объема (не более тысячи строк), такими как стековый кальку лятор, текстовый редактор, простейший компилятор и др.
Вместе с тем данная книга не предназначена исключительно студен¬ там-математикам, поэтому ее материал несколько упрощен по сравнению с курсом программирования мехмата и более направлен в сторону практи ческого программирования. Больше внимания уделено понятию алгорит ма и алгоритмического языка, представлению копьютерных целых чисел как элементов кольца вычетов, логическим выражениям, что частично дуб¬ лирует начальные математические курсы.
Значительная часть книги посвящена изложению основ языка Си. Традиционно на механико-мататематическом факультете изучению кон¬ кретных языков уделяется мало внимания, считается, что большинство студентов способно самостоятельно прочитать учебник по языку Си и
C++. Тем не менее практика показывает, что даже у сильных студентов ос¬ таются пробелы в знании языка и умении применять его в конкретных за дачах. Проблемой является и содержание многих учебников по Си: зачас тую они предлагают не самые правильные решения (такие как реализация матрицы с помощью массива указателей), и даже содержат примеры, напи¬ санные, с точки зрения автора этой книги, в дурном стиле (например, за головок функции main не содержит типа возвращаемого значения, что на самом деле неявно подразумевает тип i n t , а тело функции main не возвра щает никакого значения). Для изучения Си и C++ можно порекомендо вать лишь книги [6] и [8]. Но даже великолепная книга [6] написана уже очень давно, и многолетняя практика использования Си требует некото рых «стилевых» коррекций. Все это явилось причиной включения в дан ную книгу главы, посвященной основам Си, в которой автор попытался передать свой опыт программирования на языках Си и C++.
Заключительная глава книги посвящена структурам данных - тради ционной для учебников по программированию теме. Рассматриваются структуры данных последовательного и прямого доступа — стек, очередь, список, дерево, множество и нагруженное множество. Подчеркивается разница между абстрактным описанием структуры данных и ее реализаци¬ ями. (Так, для очереди возможны как непрерывная реализация на базе «ци клического» массива, так и ссылочная реализация.) Приводятся основные способы непрерывных и ссылочных реализаций структур данных. Значи¬ тельное внимание уделяется различным реализациям множества: с помо¬ щью бинарного поиска, на базе сбалансированных деревьев (рассматрива¬ ются A V L и красно-черные деревья) и с помощью хеш-функции.
Автор надеется, что книга принесет пользу как студентам-математи¬ кам, так и студентам непрофильных специальностей.
ОБ АВТОРЕ
Владимир Витальевич Борисенко,
кандидат физико-математических наук, старший научный сотрудник ла¬ боратории вычислительных методов при кафедре вычислительной мате¬ матики механико-математического факультета МГУ, автор и соавтор бо¬ лее 20 работ по алгебре, компьютерной алгебре и информатике, включая одну монографию по алгебре и школьные учебники информатики. На протяжении многих лет читал лекции по программированию на механи¬ ко-математическом факультете МГУ. Имеет большой опыт системного и прикладного программирования, включая иммитационное моделирова ние, разработку сетевых драйверов, разработку компиляторов, компью¬ терную графику и компьютерную томографию.
Оглавление
Глава |
1. Общее понятие алгоритма |
1 |
|||
1.1. |
Алгоритмические языки |
2 |
|||
1.2. |
Управляющие конструкции алгоритмического языка . |
5 |
|||
1.3. |
Понятие переменной |
|
10 |
||
1.4. |
Типы |
переменных |
|
|
14 |
|
1.4.1. |
Целочисленные |
переменные |
14 |
|
|
1.4.2. |
Вещественные |
переменные |
20 |
|
|
1.4.3. |
Символьные |
переменные |
27 |
|
|
1.4.4. |
Логические |
переменные и выражения |
29 |
|
|
1.4.5. |
Массивы |
|
|
32 |
|
1.4.6. |
Текстовые строки |
33 |
||
1.5. |
Примеры алгоритмов |
|
34 |
1.5.1.Вычисление функций на последовательностях . 34
|
1.5.2. |
Построение цикла |
с помощью инварианта . . . |
51 |
Глава 2. |
Устройство компьютера |
67 |
||
2.1. |
Оперативная память |
|
68 |
|
2.2. |
Процессор |
|
70 |
|
|
2.2.1. |
CISC и RISC-процессоры |
73 |
|
|
2.2.2. |
Алгоритм работы |
компьютера |
74 |
2.3. |
Аппаратный стек |
|
75 |
2.3.1.Команды вызова подпрограммы call и возврата
return |
77 |
2.3.2.Аппаратный стек и локальные переменные
подпрограммы |
78 |
2.4. R T L : машинно-независимый Ассемблер |
81 |
viii |
ОГЛАВЛЕНИЕ |
2.4.1.Примеры программ на R T L и Ассемблере Intel
80x86 |
84 |
2.4.2.Задачи по теме «Программирование на
|
|
Ассемблере» |
|
|
90 |
2.5. |
Внешние устройства |
и аппаратные |
прерывания . . . . |
91 |
|
2.6. |
Виртуальная память |
и поддержка |
параллельных задач |
93 |
|
|
2.6.1. |
Страничная организация памяти |
93 |
||
|
2.6.2. |
Переключение |
между процессами и нитями . . |
94 |
Глава 3. |
Основы языка Си |
|
97 |
|
3.1. |
Структура Си-программы |
98 |
||
3.2. Ф у н к ц и и |
|
101 |
||
|
3.2.1. |
Программа "Hello, World!" |
102 |
|
3.3. |
Типы |
переменных |
|
104 |
|
3.3.1. |
Базовые типы |
|
104 |
|
3.3.2. |
Конструирование |
новых типов |
109 |
3.4. |
Выражения |
|
119 |
|
|
3.4.1. |
Оператор присваивания |
119 |
|
|
3.4.2. |
Арифметические |
операции |
120 |
|
3.4.3. |
Операции увеличения и уменьшения |
121 |
3.4.4.Операции «увеличить на», «домножить на» и
|
т.п. |
|
|
123 |
3.4.5. |
Логические операции |
|
125 |
|
3.4.6. |
Операции |
сравнения |
|
126 |
3.4.7. |
Побитовые |
логические |
операции |
127 |
3.4.8. |
Операции |
сдвига |
|
131 |
3.4.9. |
Арифметика указателей |
132 |
||
3.4.10. Связь между указателями и массивами |
134 |
|||
3.4.11. Операция |
приведения |
типа |
135 |
|
3.5. Управляющие конструкции |
|
137 |
||
3.5.1. |
Фигурные |
скобки |
|
138 |
3.5.2. |
Оператор if |
|
138 |
|
3.5.3. |
Выбор из нескольких |
возможностей: |
|
|
|
i f . . . else if |
|
|
140 |
3.5.4.Пример: решение квадратного уравнения . . . . 141
3.5.5. Ц и к л while |
145 |
3.5.6.Пример: вычисление квадратного корня
методом деления отрезка пополам |
147 |
ОГЛАВЛЕНИЕ |
ix |
3.5.7.Выход из цикла break, переход на конец цикла
|
continue |
149 |
3.5.8. |
Оператор перехода на метку goto |
151 |
3.5.9. |
Ц и к л for |
152 |
3.5.10. Операция «запятая» и цикл for |
154 |
|
3.5.11. Конструкции, которые лучше не использовать . |
156 |
|
3.6. Представление программы в виде функций |
160 |
|
3.6.1. |
Прототипы функций |
160 |
3.6.2.Пример: вычисление наибольшего общего
делителя |
161 |
3.6.3. Передача параметров функциям |
162 |
3.6.4.Пример: расширенный алгоритм Евклида . . . . 163
3.7. Работа |
с памятью |
166 |
3.7.1. |
Статическая память |
166 |
3.7.2. |
Стековая, или локальная, память |
169 |
3.7.3. |
Динамическая память, или куча |
170 |
3.7.4.Пример: печать n первых простых чисел . . . . 172
3.7.5. |
Операторы |
new и delete языка C + + |
174 |
3.8. Структуры |
|
177 |
|
3.8.1. |
Структуры |
и указатели |
179 |
3.8.2. |
Пример: рекурсивный обход дерева |
181 |
3.8.3.Структуры и оператор определения типа typedef 183
3.9. Технология программирования на Си |
185 |
3.9.1.Представление матриц и многомерных массивов 185
3.9.2.Пример: приведение матрицы к ступенчатому
|
виду методом Гаусса |
188 |
|
3.9.3. |
Работа |
с файлами |
196 |
3.9.4. |
Работа |
с текстами |
219 |
3.9.5. |
Разработка больших проектов |
240 |
3.9.6.Задачи по теме «Технология программирования
|
|
на Си» |
242 |
Глава 4. |
Структуры данных |
246 |
|
4.1. |
Общее |
понятие структуры данных |
246 |
4.2. |
Массив |
как базовая структура |
248 |
4.3. |
Реализация одних структур на базе других |
249 |
|
4.4. |
Простейшие структуры данных. Стек. Очередь |
. . . . 250 |
|
|
4.4.1. |
Очередь |
250 |
x
|
4.4.2. |
Стек |
|
253 |
4.5. |
Ссылочные реализации структур данных |
283 |
||
|
4.5.1. |
Массовые |
операции |
284 |
|
4.5.2. |
Список |
|
285 |
|
4.5.3. |
Ссылочная |
реализация списка |
286 |
|
4.5.4. |
Деревья и графы |
287 |
|
4.6. |
Множество |
|
291 |
4.6.1.Реализации множества: последовательный и
бинарный |
поиск, хеширование |
293 |
4.6.2. Бинарный |
поиск |
294 |
4.6.3.Реализации множества на базе деревьев . . . . 297
4.6.4. |
Хеширование |
304 |
4.6.5. |
Ц и к л ы «для каждого» и итераторы |
306 |
4.7. Задачи по теме «Структуры данных» |
307 |
|
Л и т е р а т у ра |
|
309 |
Предметный |
указатель |
311 |