ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
МЕТОДЫ ПРОГРАММИРОВАНИЯ
УЧЕБНОЕ ПОСОБИЕ
для студентов, обучающихся по специальности 090102 – «Компьютерная безопасность»
Объем занятий: всего 200 часов Изучается в 7-8 семестре
г. Ставрополь, 2009 г.
Дисциплина "Методы программирования" имеет целью обучить студентов принципам построения и анализа алгоритмов, способствовать развитию логического мышления, формированию научного мировоззрения и прививать склонность к творчеству. При изучении курса используются знания, полученные слушателями в процессе изучения курсов "Математический анализ", " Дискретная математика", "Языки программирования". Знания и практические навыки, полученные из курса "Методы программирования", используются обучаемыми при изучении научных дисциплин, а также при разработке курсовых и дипломных работ.
Пособие составлено с учётом рекомендаций по изучению методов программирования студентами высшего профессионального образования по специальностям в области
информационных технологий.
Предназначено для студентов, обучающихся по специальности 090102 – «Компьютерная безопасность»
Авторы-составители:
Кандидат технических наук Д.Л. Осипов Кандидат технических наук, доцент О.М. Лепёшкин
Рецензент:
Доктор технических наук, доцент П.А. Будко
|
|
3 |
|
Содержание |
|
Содержание.................................................................................................................................... |
3 |
|
Рекомендации к проведению лабораторных работ.................................................................... |
6 |
|
Вводное занятие. Простейшая консольная программа на Delphi ............................................. |
7 |
|
|
Комментарии в тексте программы........................................................................................ |
7 |
|
Компиляция и запуск программы на выполнение............................................................... |
8 |
|
Переменные и константы....................................................................................................... |
8 |
|
Операторы и выражения........................................................................................................ |
9 |
|
Оператор присваивания........................................................................................................ |
9 |
|
Арифметические операции................................................................................................... |
9 |
|
Логические операции.......................................................................................................... |
10 |
|
Составной оператор begin..end........................................................................................... |
11 |
|
Условный оператор if..then................................................................................................. |
11 |
|
Оператор-селектор case..of ................................................................................................. |
11 |
|
Операторы обработки циклов.............................................................................................. |
11 |
|
Цикл с параметром for .. do ................................................................................................ |
12 |
|
Цикл с предусловием while..do .......................................................................................... |
12 |
|
Цикл с постусловием repeat..until....................................................................................... |
12 |
|
Вложенные циклы............................................................................................................... |
13 |
|
Процедуры break и continue................................................................................................ |
13 |
|
Оператор with..do................................................................................................................. |
14 |
|
Процедуры и функции.......................................................................................................... |
14 |
|
Процедуры............................................................................................................................ |
14 |
|
Функции ............................................................................................................................... |
15 |
1. |
Фундаментальные структуры данных................................................................................ |
16 |
|
Общее понятие типа данных................................................................................................ |
16 |
|
Простой тип........................................................................................................................... |
17 |
|
Перечислимые типы данных.............................................................................................. |
18 |
|
Поддиапазонны.................................................................................................................... |
18 |
|
Строковый тип ...................................................................................................................... |
19 |
|
Структурные типы................................................................................................................ |
19 |
|
Массивы................................................................................................................................ |
19 |
|
Записи................................................................................................................................... |
20 |
|
Множества............................................................................................................................ |
21 |
|
Представление структур в памяти....................................................................................... |
21 |
|
Задание................................................................................................................................... |
23 |
2. |
Работа с последовательностями, файлы............................................................................. |
24 |
|
Доступ к файлу...................................................................................................................... |
24 |
|
Операции над файлами......................................................................................................... |
25 |
|
Окончание файла .................................................................................................................. |
26 |
|
Пример работы с файлом..................................................................................................... |
27 |
|
Задание................................................................................................................................... |
27 |
3. |
Анализ алгоритмов............................................................................................................... |
28 |
|
Рост функций......................................................................................................................... |
28 |
|
Задание................................................................................................................................... |
30 |
4. Простейшие методы сортировки массивов........................................................................ |
32 |
|
|
Оценка алгоритмов сортировки .......................................................................................... |
32 |
|
Сортировка простым обменом (пузырьковый метод)....................................................... |
32 |
|
Шейкер-сортировка.............................................................................................................. |
33 |
|
Сортировка простым выбором............................................................................................ |
33 |
|
Сортировка простыми вставками........................................................................................ |
34 |
|
Сортировка бинарными вставками..................................................................................... |
34 |
|
|
4 |
|
Задание................................................................................................................................... |
35 |
5. |
Улучшенные методы сортировки массивов....................................................................... |
36 |
|
Сортировка с помощью включений с уменьшающимися расстояниями (сортировка |
|
|
Шелла).................................................................................................................................... |
36 |
|
Пирамидальная сортировка ................................................................................................. |
37 |
|
Сортировка с разделением (быстрая сортировка) ............................................................. |
38 |
|
Задание................................................................................................................................... |
39 |
6. |
Сортировка последовательных файлов .............................................................................. |
40 |
|
Сортировка простым слиянием........................................................................................... |
40 |
|
Естественное слияние........................................................................................................... |
41 |
|
Задание................................................................................................................................... |
42 |
7. |
Рекурсивные алгоритмы....................................................................................................... |
43 |
|
Сравнение рекурсии и итерации ......................................................................................... |
44 |
|
Задание................................................................................................................................... |
45 |
8. |
Динамические структуры данных, связные списки.......................................................... |
46 |
|
Списки.................................................................................................................................... |
47 |
|
Пример создания и заполнения списка............................................................................... |
48 |
|
Задание................................................................................................................................... |
48 |
9. |
Нелинейные структуры данных .......................................................................................... |
49 |
|
Граф........................................................................................................................................ |
49 |
|
Бинарное дерево.................................................................................................................... |
50 |
|
Задание................................................................................................................................... |
50 |
10. |
Алгоритмы на графах........................................................................................................... |
52 |
|
Алгоритмы обхода в глубину и по уровням ...................................................................... |
52 |
|
Построение минимального остовного дерева.................................................................... |
52 |
|
Поиск кратчайшего пути...................................................................................................... |
53 |
|
Задание................................................................................................................................... |
54 |
11. |
Поиск данных........................................................................................................................ |
55 |
|
Двоичный (бинарный) поиск элемента в массиве............................................................. |
55 |
|
Интерполяционный поиск элемента в массиве.................................................................. |
55 |
|
Алгоритм Бойера-Мура........................................................................................................ |
55 |
|
Задание................................................................................................................................... |
57 |
12. |
Хеширование......................................................................................................................... |
58 |
|
Отечественный стандарт хеширования.............................................................................. |
59 |
|
Создание хеш-функции........................................................................................................ |
59 |
|
Хеш-функции для строковых значений, алгоритм Гонера............................................... |
59 |
|
Задание................................................................................................................................... |
60 |
13. |
Методы сжатия текстовых данных..................................................................................... |
61 |
|
Метод “Running” ................................................................................................................... |
61 |
|
Словарные методы сжатия................................................................................................... |
61 |
|
Алгоритм Хаффмана............................................................................................................. |
63 |
|
Задание................................................................................................................................... |
64 |
14. |
Алгоритмы вывода графических примитивов................................................................... |
65 |
|
Рисование отрезка................................................................................................................. |
65 |
|
Прямое вычисление координат.......................................................................................... |
66 |
|
Инкрементный алгоритм Брезенхэма................................................................................ |
67 |
|
Простейший алгоритм закрашивания замкнутой области................................................ |
69 |
|
Задание................................................................................................................................... |
70 |
15. |
Псевдослучайные последовательности.............................................................................. |
71 |
|
Метод середин квадратов..................................................................................................... |
71 |
|
Линейный конгруэнтный метод.......................................................................................... |
71 |
|
Генератор псевдослучайных чисел, поставляемый с системой....................................... |
72 |
|
Оценка качества генератора ПСП....................................................................................... |
72 |
|
Задание................................................................................................................................... |
73 |
|
5 |
16. Параллельные алгоритмы.................................................................................................... |
74 |
Пример многопоточного приложения................................................................................ |
74 |
Задание................................................................................................................................... |
77 |
Задание на СКР............................................................................................................................ |
78 |
Вариант 1. Клеточные автоматы......................................................................................... |
78 |
Вариант 2. Раскрашивание карты........................................................................................ |
79 |
Вариант 3. Крисс-кросс........................................................................................................ |
80 |
Вариант 4. Лабиринт............................................................................................................. |
81 |
Список использованной литературы......................................................................................... |
82 |
Приложение A. Справочник по функциям Delphi.................................................................... |
83 |
Операции с порядковыми типами....................................................................................... |
83 |
Математические функции и процедуры............................................................................. |
83 |
Генерация псевдослучайного числа.................................................................................... |
83 |
Преобразование типов данных............................................................................................ |
84 |
Работа с памятью.................................................................................................................. |
84 |
Приложение Б. Компонент-сетка TStringGrid .......................................................................... |
85 |
Приложение В. Компонент-диаграмма TChart......................................................................... |
87 |
Приложение Г. Многострочный текстовый редактор – компонент TMemo ......................... |
89 |
Приложение Д. Элементарный поток – класс TThread............................................................ |
91 |
Приоритет потока ................................................................................................................. |
93 |
Время выполнения потока................................................................................................... |
94 |
Синхронизация потока с методами VCL............................................................................ |
94 |
6
Рекомендации к проведению лабораторных работ
Программа – это Идея, которую программист изложил на языке программиро-
вания. Такое определение во главу угла ставит не сотни строк безликого кода, а Её Величество Идею, то, без чего немыслимо существование творческой личности. Это определение – достойный ответ спорщикам на тему: “Что такое программирование – ремесло или Искусство?”.
Входе выполнения лабораторных работ студенты получат представление о:
-современных технологиях программирования;
-порядке оценки качества программного обеспечения;
-общих принципах проектирования архитектуры и структуры программ с учетом повышенных требований к надежности программ и их защищенности от несанкционированного доступа;
-технологии объектно-ориентированного программирования;
-применении математических методов в проектировании надежного и защищенного программного обеспечения;
-абстрактном представлении данных;
-элементарных, простых и сложных структурах данных;
-порядке оценки сложности алгоритмов;
-алгоритмах сортировки и поиска;
-итеративных и рекурсивных алгоритмах;
-алгоритмах на графах;
-построении хеш-функций;
-алгоритмах сжатия данных;
-алгоритмах вывода простейших графических примитивов;
-алгоритмах генерации псевдослучайных последовательностей;
-параллельных алгоритмах.
Вводное занятие предназначено для самостоятельной работы студентов. Занятие основано на материале, изученном студентами в предыдущий период обучения в ходе прохождения дисциплины “Языки программирования” и представляет собой краткий справочник по ключевым синтаксическим конструкциям языка программирования Delphi. Повторив материал вводного занятия, студент восстановит в памяти знания необходимые для выполнения цикла лабораторных работ по дисциплине “Методы программирования”.
Все лабораторные работы выполняются в среде Delphi. Работы 1..7 целесообразно разрабатывать в формате консольных приложений, оставшиеся работы в формате обычных приложений для Windows. С разрешения преподавателя допускается выполнение лабораторных работ на других языках программирования высокого уровня (C, C#, и т.д).
Отчёт о выполненной лабораторной работе должен содержать:
1.Листинг программ с подробными комментариями. Листинг может быть представлен в электронном формате (в виде исходных файлов).
2.Выводы о проделанной работе.
Отчёт защищается в устной форме с выставлением оценки.
Кроме лабораторных работ учебное пособие включает ряд приложений, которые могут использоваться студентами в качестве справочника по функциям и ряду компонентов Delphi и задание на самостоятельную работу