 ПОЗНАВАТЕЛЬНОЕ
| ПО САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ ТЕМ
Тема 1. Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. Понятие переменной Общее понятие алгоритма и краткий обзор существующих алгоритмических языков. Неформальный алгоритмический язык - псевдокод, максимально приближенный к естественному языку. Основные конструкции алгоритмического языка - алгоритм, ветвление, цикл; приводятся простейшие примеры программ на псевдокоде. Понятие переменной. При изучении данной темы следует обратить внимание на источники: [1], [2]. Контрольные вопросы для самопроверки 1.Понятие алгоритма. Свойства. 2.Формы записей алгоритмов. 3.Основные алгоритмические конструкции. 4.Основы алгебры логики. 5.Законы логических операций. Таблицы истинности.
Тема 2. Основные конструкции программирования Алфавит, синтаксис и семантика языка программирования. Средства определения синтаксиса: расширенные формулы Бэкуса-Наура (РБНФ), синтаксические диаграммы. Классификация языков программирования по уровню абстракции. Обзор основных элементов языка программирования высокого уровня. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. В чем состоит расширенный формализм Бэкуса-Наура (РБНФ)? 2. Синтаксис и семантика языка программирования Компонетный Паскаль. 3. Приведите классификацию языков программирования по уровню абстракции. 4. Перечислите основные элементы языка программирования высокого уровня.
Тема 3. Теория алгоритмов Интуитивное определение алгоритма. Основные свойства алгоритмов. Понятие исполнителя алгоритма. Основные методы разработки алгоритмов. Формальное определение алгоритма. Машина Тьюринга. Операции над машинами Тьюринга. Тезис Тьюринга. Нормальные алгорифмы Маркова. Принцип нормализации Маркова. Понятия самоприменимости алгоритма и алгоритмической неразрешимости. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Дайте формальное определение понятию алгоритма. Как работает машина Тьюринга? 2. Какие операции допустимы над машиной Тьюринга? 3. Определите нормальный алгоритм Маркова. 4. В чем состоит принцип нормализации Маркова? 5. Поясните понятие самоприменимости и алгоритмической неразрешимости.
Тема 4. Рекурсия Рекурсивные алгоритмы. Понятие рекурсивного алгоритма. Виды рекурсии. Структура рекурсивного алгоритма. Примеры рекурсивных алгоритмов. Реализация перебора с возвратом с помощью рекурсии. Реализация механизма рекурсии. Сравнение рекурсии и итерации. Рекурсивные данные. Бинарные деревья. Обходы бинарного дерева. Основные алгоритмы обработки бинарных деревьев (уничтожение дерева, вставки информации в дерево, удаление вершины из дерева, сравнения двух деревьев и др.). При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Дайте определение понятию рекурсии. 2. Приведите примеры рекурсивного определения. 3. Поясните реализацию перебора с возвратом с помощью рекурсии. 4. Сравните рекурсию с итерацией. 5. Поясните алгоритм обхода бинарного дерева. 6. Как реализуются операции по обработке бинарных деревьев?
Тема 5. Структуры данных Понятие абстрактного типа данных. Классификация структур данных. Последовательные списки: стек, очередь, дек. Связные списки: однонаправленный список, двунаправленный список, циклический список. Графы. Методы реализации графов: матрица смежности, матрица инцидентности, списки смежных вершин, список ребер. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Определите абстрактный тип данных. 2. Приведите классификацию фундаментальных структур данных. 3. Дайте определение типу записи. 4. Как определяется тип список? 5. Поясните редактирование списка. 6. Как задать циклический список? 7. Приведите пример задания двунаправленного списка. 8. Приведите примеры стека, очереди, дека. 9. Что такое матрица смежности? 10. Что такое матрица инцидентности? 11. Приведите примеры списков смежных вершин, список ребер графа. 12. Какие знаете методы реализации графов?
Тема 6. Сортировка Внутренняя сортировка (сортировка массивов). Понятие сложности алгоритма сортировки. Основные алгоритмы внутренней сортировки: пузырьковая сортировка, шейкерная сортировка, сортировка простым выбором, сортировка простыми вставками, сортировка Шелла, сортировка слиянием, быстрая сортировка. Внешняя сортировка (сортировка файлов). Отрезки файла. Операции разделения файла и слияния файлов. Некоторые алгоритмы внешней сортировки: многофазная сортировка, сбалансированное слияние. Использование алгоритмов внутренней сортировки в сортировке последовательных файлов. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Поясните операцию сортировки элементов массива. 2. Какие показатели эффективности алгоритма сортировки можете перечислить? 3. Приведите примеры квадратичных и субквадратичных алгоритмов сортировки элементов массива. 4. Дайте определение логарифмическому алгоритму сортировки. 5. Дайте определение линейному алгоритму сортировки. 6. Поясните сортировку пузырьком и оцените показатели эффективности. 7. Поясните сортировку вставками. 8. Дайте определение сортировки выбором. 9. Приведите примеры сортировки выбором.
Тема 7. Поиск Поиск в массиве. Линейный поиск. Бинарный поиск. Поиск в таблице. Хеширование. Выбор хеш-функции. Разрешение коллизий: метод открытой адресации, метод цепочек. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Дайте определение задачи поиска в массиве. 2. Поясните алгоритм линейного поиска в массиве. 3. Оцените количество элементарных операций в линейном поиске. 4. Выполните сравнительный анализ эффективности линейного и бинарного алгоритмов поиска. 5. Как реализуется поиск в таблице? 6. В чем состоит хеширование? 7. Как выполняется выбор хеш-функции? 8. Раскройте понятие коллизии. 9. В чем состоит метод открытой адресации? 10. Опишите метод цепочек.
Тема 8. Объектно-ориентированное программирование Парадигма объектно-ориентированного программирования (ООП): концепции объекта и класса, инкапсуляции, наследования и полиморфизма. Спецификация видимости атрибутов и методов объекта. Механизмы раннего и позднего связывания. Статические и виртуальные методы. Иерархии классов. Шаблоны классов. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. Раскройте понятия объекта и класса. 2. Что понимают под инкапсуляцией? 3. Что такое наследование? 4. В чем состоит полиморфизм поведения класса? 5. Приведите спецификацию видимости атрибутов и методов класса. 6. В чем состоит механизм раннего (позднего) связывания? 7. Приведите примеры статистического и виртуального методов.
Тема 9. Событийное программирование и прикладные программные интерфейсы Событийно-управляемое программирование. Пользовательские и системные события в программе. Методы обработки и распространение событий. Управление параллелизмом с помощью механизма обработки событий. Прикладной программный интерфейс (Application Programming Interface), API-программирование. Методы обработки данных, основанные на компонентных технологиях. Промежуточное программное обеспечение (middleware). При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки 1. В чем заключается событийно-управляемое программирование? 2. Определите пользовательские и системные события в программе. 3. Какие методы обработки и распространения событий можете назвать? 4. В чем состоит параллелизм обработки событий? 5. Что называют прикладным программным интерфейсом? 6. Что такое промежуточное программное обеспечение?
Тема 10. Параллельные вычислительные технологии Параллельная вычислительная система. Примеры больших задач. Режимы выполнения задач: последовательный, псевдопараллельный (разделение времени) и параллельный. Виды параллелизма: многопроцессорная, векторная и конвейерная обработка. Методика разработки параллельных алгоритмов. Модель "процессы-каналы" параллельной программы. Разделение вычислений на независимые части: параллелизм по данным и функциональный параллелизм. Выделение информационных зависимостей: локальные и глобальные, статические и динамические схемы передачи данных, структурные и произвольные, синхронные и асинхронные способы взаимодействия. Масштабирование подзадач. Распределение подзадач по процессорам вычислительной системы. При изучении данной темы следует обратить внимание на источники: [1], [2], [3]. Контрольные вопросы для самопроверки |
