- •Тема 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.3.Алгоритм расчета резервов времени
После того, как рассчитаны наиболее ранние и наиболее поздние сроки наступления событий сетевого графика, рассчитывают так называемые резервы времени операций. Различают три вида резервов времени.
Максимальное время задержки выполнения операции (x,y) не оказывающее влияние на время выполнения всего проекта называется полным резервом времени операции (x,y). Полный резерв времени операции (x,y) рассчитывается по формуле:
ПРВ(x,y)=L(y)-E(x)-t(x,y).
Если время выполнение операции (x,y) будет задержано на величину ПРВ(x,y), то это наложит временные ограничения на все предшествующие и последующие операции. Действительно, все операции, предшествующие операции (x,y) должны завершиться в наиболее ранний срок наступления события x, а последующие операции начнутся в наиболее поздний срок наступления события y.
Резерв времени операции (x,y), не накладывающий временных ограничений на последующие операции, называется свободным резервом времени и рассчитывается по формуле:
СРВ(x,y)=E(y)-E(x)-t(x,y).
Если время выполнение операции операция (x,y) будет задержано на величину CРВ(x,y), то это наложит временные ограничения на все предшествующие операции.
Резерв времени операции (x,y), не накладывающий никаких временных ограничений ни на одну другую операцию проекта называется независимым резервом времени и рассчитывается по формуле:
НРВ(x,y)=E(y)-L(x)-t(x,y).
Очевидно, что для резервов времени каждой операции (x,y) выполняется отношение:
ПРВ(x,y)СРВ(x,y)НРВ(x,y).
Для критических операций (x,y) выполняется:
ПРВ(x,y)=СРВ(x,y)=НРВ(x,y)=0.
Расчет всех резервов времени сетевого графика рассмотренного в разделе 7.5.2 (см. рис.7.24) сведен в табл.7.3. Строки таблицы, соответствующие критическим операциям выделены серым цветом.
Таблица 7.3
Расчет резервов времени
Операция |
Резервы времени выполнения операции |
||
полный |
свободный |
независимый |
|
(1,2) |
4-0-4=0 |
4-0-4=0 |
4-0-4=0 |
(1,3) |
7-0-3=4 |
5-0-3=2 |
5-0-3=2 |
(1,4) |
10-0-4=6 |
4-0-4=0 |
4-0-4=0 |
(2,3) |
7-4-1=2 |
5-4-1=0 |
5-4-1=0 |
(2,5) |
11-4-7=0 |
11-4-7=0 |
11-4-7=0 |
(2,7) |
16-4-8=4 |
16-4-8=4 |
16-4-8=4 |
(3,5) |
11-5-4=2 |
11-5-4=2 |
11-7-4=0 |
(4,6) |
12-4-2=6 |
12-4-2=6 |
12-10-2=0 |
(5,6) |
12-11-1=0 |
12-11-1=0 |
12-11-1=0 |
(5,7) |
16-11-3=2 |
16-11-3=2 |
16-11-3=2 |
(6,7) |
16-12-4=0 |
16-12-4=0 |
16-12-4=0 |
Вопросы для повторения
Алгоритмы поиска элемента в неупорядоченном массиве.
Алгоритм поиска элемента в упорядоченном массиве.
Назначение и идея фонетического поиска.
Задача сортировки. Алгоритмы сортировки массива.
Сортировка массива методом пузырька.
Сортировка массива вставками.
Сортировка массива выбором.
Пирамидальная сортировка массива.
Быстрая сортировка массива.
Сортировка слиянием.
Поиск на графах. Поиск в глубину.
Поиск на графах. Поиск в ширину.
Топологическая сортировка графа.
Постановка задачи сетевого планирования.
Алгоритм расчета наиболее ранних сроков наступления событий.
Алгоритм расчета наиболее поздних сроков наступления событий.
Алгоритм расчета резервов времени.
Резюме по теме
В данной теме рассмотрены некоторые из алгоритмов, которые наиболее часто используются в экономических информационных системах.
Литература
Рекомендуемая основная литература
Шмидский Я.К. Программирование на языке C/C++: Самоучитель [Текст]. - Диалектика, 2004.
Подбельский В.В. Программирование на языке Си [Текст]. - Финансы и статистика, 2001
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы [Текст]. - Издательский дом «Вильямс», 2001.
Рекомендуемая дополнительная литература
Дейл Н. Программирование на С++ [Текст]. - ДМК, 2000.
Савич У. Программирование на C++ [Текст].- Питер : BHV, 2004.
Кнут Д.Э. Искусство программирования = The Art of Computer Programming [Текст].- Вильямс, 2000.
Арсак Ж. Программирование игр и головоломок [Текст].- Наука, 1990.
Муромцев В.В. Теория экономических информационных систем [Электронный ресурс]. - Белгород, БелГУ,2007.
Муромцев В.В.Теория экономических информационных систем [Текст].- Белгород, БелГУ, 2007.
Муромцев В.В.Алгоритмы на графах. [Электронный ресурс]. - Белгород, БИИММАП, 2000.
Муромцев В.В.Методические указания к лабораторным работам по курсу "Дискретная математика" [Электронный ресурс].- Белгород, БТИСМ, 1993.
1 Если из контекста ясно, что рассматривается орграф, то ради сокращения речи термин "граф" употребляется вместо термина "орграф".
2 При реализации на ЭВМ вместо бесконечности используют максимально возможное значение типа используемого для элементов матрицы.
3 Вместо нуля можно использовать любое число, не использующееся для нумерации вершин дерева.