- •Тема 1. Алгоритмы и программы 4
- •Тема 2. Характеристика языка Си 6
- •Тема 3. Основы языка Си 11
- •Тема 4.Работа с файлами 33
- •Тема 5.Распределение памяти 40
- •Тема 6. Методы организации данных в памяти эвм 43
- •Тема 7. Некоторые алгоритмы обработки данных 58
- •Тема 1. Алгоритмы и программы Цели и задачи изучения темы
- •1.1.Понятие алгоритма. Понятие программы. Способы записи алгоритмов.
- •1.2.Критерии качества программ
- •1.3.Низкоуровневые и высокоуровневые языки программирования
- •1.4.Принципы структурного программирования
- •Принципы структурного программирования.
- •2.2.Основные характеристики языка Си.
- •2.2.1.Достоинства языка Си
- •2.2.2.Компиляторы и интерпретаторы
- •2.2.3.Сильная типизация
- •2.3.Структура простой программы
- •Вопросы для повторения
- •3.1.2.Основные типы данных
- •3.1.3.Структуры данных
- •3.1.4.Оператор определения имени типа typedef
- •3.1.5.Массивы
- •3.1.6.Указатели
- •3.1.7.Указатели и массивы
- •3.1.8.Внешние и внутренние переменные
- •3.2.Стандартные функции ввода-вывода
- •3.3. Операции, операторы и выражения
- •3.3.1.Оператор присваивания
- •3.3.2.Арифметические операции
- •3.3.3.Операции увеличения и уменьшения
- •3.3.4.Операции сравнения
- •3.3.5.Логические операции
- •3.3.6.Побитовые логические операции
- •3.3.7.Операции сдвига
- •3.3.8.Операции "увеличить на", "домножить на" и т.П.
- •3.3.9.Операции с указателями. Указатели и массивы
- •3.3.10.Операция приведения типа
- •3.4.Управляющие конструкции
- •3.4.1.Фигурные скобки
- •3.4.2.Оператор выбора if и операция условия
- •3.4.3.Оператор множественного выбора switch
- •3.4.4.Оператор цикла while
- •3.4.5.Оператор цикла for
- •3.4.6.Оператор цикла do...While
- •3.5.Данные (более детальные сведения)
- •3.5.1.Структуры
- •3.5.2.Указатели и структуры
- •3.5.3.Структуры и оператор определения имени типа typedef
- •3.5.4.Строки
- •3.5.5.Матрицы и многомерные массивы
- •3.6.Пользовательские функции
- •3.6.1.Определение функций
- •3.6.2.Прототипы функций
- •3.6.3.Аргументы командной строки
- •Вопросы для повторения
- •4.2.Функция открытия файла fopen
- •4.3.Функции бинарного чтения и записи fread и fwrite
- •4.4.Функция закрытия файла fclose
- •4.5.Функции форматного чтения и записи fscanf и fprintf
- •4.6.Другие функции ввода-вывода
- •4.6.1.Функции посимвольного ввода-вывода
- •Int fgetc(file *f); - ввести один символ из файла f.
- •Int fputc(int c, file *f); - записать один символ в файл f.
- •4.6.2.Функции построкового ввода-вывода
- •Char *fgets(char *line,int size, file *f); - ввести строку из файла f.
- •Char *fputs(char *line, file *f); - записать строку в файл f.
- •4.6.3.Функции позиционирования в файле
- •Int fseek(file *f, long offset, int whence); - установить текущую позицию в файле f
- •Long ftell(file *f); - получить текущую позицию в файле f
- •Int feof(file *f); - проверить,достигнут ли конец файла f
- •Функция открытия файла fopen
- •Функции бинарного чтения и записи fread и fwrite
- •Функция закрытия файла fclose
- •5.2.Функции malloc и free
- •5.3.Выделение памяти под матрицы на этапе выполнения программы
- •Функции malloc и free.
- •6.2.Время выполнения программ
- •6.3.Списки
- •6.4.Реализация списков
- •6.5.Стеки
- •6.6.Реализация стеков
- •6.7.Очереди
- •6.8.Реализация очередей
- •6.9.Графы и деревья
- •6.10.Некоторые сд для хранения графов и деревьев
- •Матрица смежности графа, изображенного на рис.6.10
- •Матрица инцидентности графа, изображенного на рис.6.10
- •Матрица весов графа, изображенного на рис.6.11
- •Матрица смежности дерева, изображенного на рис.6.16
- •Вопросы для повторения
- •Реализация стеков.
- •Реализация очередей.
- •7.1.1.Поиск элемента в неупорядоченном массиве
- •7.1.2.Поиск элемента в упорядоченном массиве.
- •7.1.3.Фонетический поиск
- •7.2.Алгоритмы сортировки
- •7.2.1.Сортировка методом пузырька.
- •7.2.2.Сортировка вставками
- •7.2.3.Сортировка выбором
- •7.2.4.Пирамидальная сортировка
- •7.2.5.Быстрая сортировка
- •7.2.6.Сортировка слиянием
- •Этапы слияния файлов f1 и f2
- •7.3.Поиск на графах
- •7.3.1.Поиск в глубину
- •7.3.2.Поиск в ширину
- •7.4.Топологическая сортировка графа
- •7.5.Сетевое планирование
- •Информация о проекте
- •7.5.1.Алгоритм расчета наиболее ранних сроков наступления событий
- •7.5.2.Алгоритм расчета наиболее поздних сроков наступления событий
- •7.5.3.Алгоритм расчета резервов времени
- •Расчет резервов времени
- •Вопросы для повторения
7.5.Сетевое планирование
Многие крупные работы (проекты) как правило, состоят из более мелких работ (операций). Некоторые из операций могут выполняться одновременно, другие - только последовательно. Например, при строительстве дома можно совместить во времени внутренние отделочные работы и работы по благоустройству территории, однако возводить стены можно только после закладки фундамента.
Задача управления проектом состоит в том, чтобы обеспечить его своевременное завершение. При этом необходимо учитывать время, необходимое для выполнения каждой операции и взаимосвязи между операциями характеризующие последовательность их выполнения. Например, если подрядчик задержит закладку фундамента, то дом не будет построен к намеченному сроку. При управлении проектом необходимо выявить так называемые критические операции, т.е. операции, задержка выполнения которых приведет к задержке выполнения всего проекта. На сроки завершения критических операций руководитель проекта должен обращать особое внимание. В данном разделе рассматривается алгоритм определения критических операций.
Для задания проекта необходима следующая информация:
Перечень всех операций проекта.
Время необходимое для выполнения каждой операции.
Перечни операций, непосредственно предшествующих каждой операции.
Каждый проект можно представить в виде ориентированного графа, в котором каждая операция соответствует некоторой дуге, при этом выполняется следующее правило: если некоторая операция представлена дугой (x,y), то в вершину x входят только дуги, представляющие операции, непосредственно предшествующие данной операции. Каждой дуге приписывается число равное времени выполнения соответствующей операции. При необходимости в граф вводятся фиктивные операции, т.е. дуги, не представляющие никакой операции (фиктивные дуги). Время выполнения фиктивной операции равно нулю. Граф, представляющий проект, называется сетевым графиком.
Вершины сетевого графика называют событиями. Говорят, что событие x произошло, если все операции непосредственно предшествующие операции соответствующей некоторой дуге (x,y) завершились.
В сетевом графике есть начальное событие, т.е. событие, соответствующее началу работы над проектом и конечное событие, т.е. событие, соответствующее окончанию работ над проектом.
Пример. Рассмотрим абстрактный проект, представленный в табл.7.2. Время операций в проекте не важно. Данному проекту соответствует сетевой график на рис.7.21.
Таблица 7.2
Информация о проекте
Операция |
Непосредственно предшествующие операции |
A |
нет |
B |
A |
C |
A |
D |
A |
E |
B,C |
F |
B,C,D |
G |
E,F |
Отметим, что сетевой график не может содержать контуров. Действительно, пусть в сетевом графике имеется контур (a,b),(b,c),...,(r,s),(s,a). Тогда событие a не может произойти, пока не произошло событие s, событие s не может произойти, пока не произошло событие r, и т.д. Очевидно, что в этом случае проект никогда не может быть завершен.
Поскольку сетевой график не содержит контуров, он может быть топологически отсортирован. Это упрощает алгоритмы расчета наиболее ранних и наиболее поздних сроков наступления событий, которые будут рассмотрены в разделах 7.5.1 и 7.5.2 соответственно.