- •Часть 2
- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа
- •Учреждение образования
- •«Белорусский государственный университет
- •Информатики и радиоэлектроники»
- •Протокол согласования учебной программы по изучаемой учебной дисциплине с другими дисциплинами специальности
- •Задачи изучения дисциплины. В результате изучения дисциплины «Основы информатики и программирования» студенты должны:
- •Содержание дисциплины
- •1. Название тем лекционных занятий, их содержание, объем в часах
- •2. Перечень тем лабораторных занятий,
- •Теоретический раздел Лекции
- •Int I; // I - счетчик членов ряда
- •X, // аргумент функции
- •Int newton(double (*f)(double), // Функция
- •1. Типы данных – простые и составные.
- •2. Агрегирование данных.
- •3. Генерация «псевдослучайных» данных.
- •4. Абстрактные типы данных.
- •5. Статические и динамические структуры данных.
- •6. Последовательности (динамические массивы).
- •7. Реализация операций над последовательностями.
- •Int nMaxSize; // Размер выделенной области памяти
- •Int nSize; // Количество элементов последовательности
- •1. Понятие стека. Операции над стеком.
- •2. Программная реализация стека на основе статического массива.
- •3. Использование стека при организации связи функций в языке Си и в операционной системе.
- •4. Понятие очереди. Операции над очередями. Кольцевая очередь. Деки.
- •5. Программная реализация очереди на основе статического массива.
- •1. Структура данных «список».
- •4. Реализация списков на основе динамических структур.
- •5. Двусвязный список и его программная реализация.
- •6. Кольцевые списки
- •7. Многосвязные (слоеные) списки
- •Фаза 1 сортировки: построение пирамиды
- •Фаза 2: собственно сортировка
- •Разделение массива
- •Общий алгоритм
- •Практический раздел
- •Контрольные работы
- •Контрольная работа №1
- •Указания по выбору варианта
- •Варианты контрольных заданий
- •Теоретическая часть (вопросы)
- •Практическая часть Контрольное задание №1. Организация распределения продукции в логистической системе
- •Исходные данные к контрольному заданию №1
Теоретическая часть (вопросы)
Понятие сложности алгоритма, оценки времени исполнения.
Общая классификация вычислительных алгоритмов.
Точность представления чисел.
Вычисление «машинного нуля».
Стеки, очереди, множества и их использование.
Понятие стека. Операции над стеком.
Программная реализация стека на основе статического массива.
Использование стека при организации связи функций в языке Си и в операционной системе.
Понятие очереди. Операции над очередями.
Кольцевая очередь. Деки.
Программная реализация очереди на основе статического массива.
Логическая шкала и описание множества элементов.
Операции над множествами. Использование структуры типа «множество» при программировании.
Списки и их организация.
Структура данных «список».
Ссылки.
Линейные списки – основные операции.
Реализация списков на основе динамических структур.
Двусвязный список и его программная реализация.
Кольцевые списки.
Многосвязные (слоеные) списки.
Алгоритмы поиска.
Поиск.
Бинарный поиск.
Алгоритм прямого поиска.
Алгоритм Кнута-Мориса-Пратта.
Алгоритм Боуера-Мура.
Алгоритмы сортировки.
Сортировки – общая классификация.
Сортировка с помощью включения
Сортировка с помощью выделения
Сортировка с помощью обменов
Шейкерная сортировка.
Сортировка Шелла
Сравнение рассмотренных сортировок
Пирамидальная сортировка
Быстрая сортировка
Сортировка слиянием
Графовые алгоритмы.
Графы – основные понятия.
Формы представления графов. Матрица смежности.
Формы представления графов. Матрица инцидентности.
Формы представления графов. Списки смежности.
Формы представления графов. Массив дуг.
Достижимость и обходы графа.
Алгоритм Дейкстры
Организация словарей и хеш-функции.
Словари – форма представления и основные понятия.
Схемы хеширования.
Хеш-функции: деление, мультипликативный метод, аддитивный метод, метод на основе операции «исключающее ИЛИ», метод середины квадрата.
Другие формы организации словарей.
Символьные вычисления
Вычисление выражений по их символьному представлению.
Построение обратной польской записи выражения.
Приоритеты операций.
Практическая часть Контрольное задание №1. Организация распределения продукции в логистической системе
Таблица 2
Исходные данные к контрольному заданию №1
|
Показатели |
Значение показателей по вариантам | ||||
|
1 |
2 |
3 |
4 |
5 | |
|
Мощность склада: V W |
20 20 |
25 22 |
15 40 |
30 10 |
20 20 |
|
Потребность в товаре: X Y Z |
20 10 10 |
20 10 10 |
20 10 5 |
15 15 10 |
18 10 12 |