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