АННОТАЦИОННАЯ ПРОГРАММА ДИСЦИПЛИНЫ
ОСНОВЫ ПРОГРАММИРОВАНИЯ
Направление подготовки 010400.62 прикладная математика и информатика (математическое и информационное обеспечение экономической деятельности)
Квалификация (степень) выпускника бакалавр
Общая трудоемкость дисциплины 144 ч.
1. Цели освоения дисциплины
Целью дисциплины является освоение базовых понятий и терминов программиро-вания как науки.
2. Место дисциплины в структуре ООП ВПО
Курс входит в цикл вспомогательных дисциплин. Для освоения курса необходимы знания и навыки, приобретенные в результате предварительного обучения по дисципли-нам: информатика, практикум на ЭВМ, алгоритмы и алгоритмические языки.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля): ОК-6, ОК-8, ОК-10, ОК-11, ПК-1, ПК-4, ПК-5, ПК-6, ПК-8, ПК-9, ПК-10, ПК-11, ПК-15, ПК-16, ПК-18, ПК-21, ПК-22, ПК-25, ПК-27, ПК-29.
В результате освоения дисциплины обучающийся должен:
1) Знать: основные понятия и конструкции языка программирования высокого уровня, основные структуры данных, алгоритмы сортировки и поиска данных, базовые концепции парадигм объектно-ориентированного и параллельного программирования.
2) Уметь: разрабатывать программы на языке высокого уровня, применяя изученные алгоритмы и структуры данных в соответствии с технологией разработки программ.
3) Владеть: способностью к самостоятельному освоению новых алгоритмов, структур данных и парадигм программирования.
4. Структура и содержание дисциплины.
1. Базовые понятия программирования
Информация. Определение, виды, свойства, меры информации. Информационные технологии. Аппаратное, программное и алгоритмическое обеспечение информационных технологий.
Компьютер. Структура компьютера. Принципы Фон-Неймана. Понятие архитектуры компьютера. Краткий обзор современных многоядерных и многопроцессорных вычислительных систем.
Программирование как научная дисциплина и профессиональная деятельность. Пользователи, программисты, системные администраторы. Прикладное, системное, научно-исследовательское программирование. Сложность ‑ основная проблема программирования.
Жизненный цикл программного обеспечения. Анализ и спецификация. Проектирование. Реализация. Тестирование. Сопровождение.
Среда программирования. Основные компоненты среды программирования: редактор, компилятор, отладчик. Классификация ошибок в программе: синтаксические, семантические ошибки, ошибки времени выполнения.
2. Основные конструкции программирования
Язык программирования. Алфавит, синтаксис и семантика языка программирования. Средства определения синтаксиса: расширенные формулы Бэкуса-Наура (РБНФ), синтаксические диаграммы. Классификация языков программирования по уровню абстракции. Обзор основных элементов языка программирования высокого уровня.
Константы. Объявление и использование констант. Типизированные константы.
Выражения. Классификация и приоритет операций. Построение и вычисление выражений.
Типы данных. Классификация типов данных, примеры. Эквивалентность типов. Совместимость типов, совместимость по присваиванию. Преобразование типов.
Операторы. Классификация операторов. Примеры операторов. Понятие структурного программирования. Теорема о структурном программировании.
Подпрограммы. Процедуры и функции. Спецификация подпрограммы. Формальные и фактические параметры подпрограммы. Способы передачи фактических параметров в подпрограмму. Понятие модульного программирования, модульная структура программы.
Структура программы. Определяющее и использующее вхождения идентификатора. Области действия и видимости декларации. Локальные и глобальные переменные, побочный эффект подпрограммы. Распределение памяти программы: сегмент данных, сегмент стека, куча.
Файловые типы данных. Классификация файловых типов. Стандартные подпрограммы работы с файлами.
Ссылочные типы данных и указатели. Статические и динамические переменные программы. Стандартные подпрограммы работы с указателями.
Библиотеки. Структура и назначение компонент библиотеки. Использование библиотек в разработке больших программных систем.
3. Теория алгоритмов
Интуитивное определение алгоритма. Основные свойства алгоритмов. Понятие исполнителя алгоритма. Основные методы разработки алгоритмов.
4. Рекурсия
Рекурсивные алгоритмы. Понятие рекурсивного алгоритма. Виды рекурсии. Структура рекурсивного алгоритма. Примеры рекурсивных алгоритмов. Реализация перебора с возвратом с помощью рекурсии. Реализация механизма рекурсии. Сравнение рекурсии и итерации.
5. Структуры данных
Понятие абстрактного типа данных. Классификация структур данных.
Последовательные списки: стек, очередь, дек.
Связные списки: однонаправленный список, двунаправленный список, циклический список.
Графы. Методы реализации графов: матрица смежности, матрица инцидентности, списки смежных вершин, список ребер.
6. Сортировка
Внутренняя сортировка (сортировка массивов). Понятие сложности алгоритма сортировки. Основные алгоритмы внутренней сортировки: пузырьковая сортировка, шейкерная сортировка, сортировка простым выбором, сортировка простыми вставками, сортировка Шелла, сортировка слиянием, быстрая сортировка.
Внешняя сортировка (сортировка файлов). Отрезки файла. Операции разделения файла и слияния файлов. Некоторые алгоритмы внешней сортировки: многофазная сортировка, сбалансированное слияние. Использование алгоритмов внутренней сортировки в сортировке последовательных файлов.
7. Поиск
Поиск в массиве. Линейный поиск. Бинарный поиск.
Поиск в таблице. Хеширование. Выбор хеш-функции. Разрешение коллизий: метод открытой адресации, метод цепочек.
8. Объектно-ориентированное программирование
Парадигма объектно-ориентированного программирования (ООП): концепции объекта и класса, инкапсуляции, наследования и полиморфизма. Спецификация видимости атрибутов и методов объекта. Механизмы раннего и позднего связывания. Статические и виртуальные методы. Иерархии классов. Шаблоны классов.
9. Событийное программирование и прикладные программные интерфейсы
Событийно-управляемое программирование. Пользовательские и системные события в программе. Методы обработки и распространение событий. Управление параллелизмом с помощью механизма обработки событий.
Прикладной программный интерфейс (Application Programming Interface), API-программирование. Методы обработки данных, основанные на компонентных технологиях. Промежуточное программное обеспечение (middleware).
10. Параллельные вычислительные технологии
Параллельная вычислительная система. Примеры больших задач. Режимы выполнения задач: последовательный, псевдопараллельный (разделение времени) и параллельный. Виды параллелизма: многопроцессорная, векторная и конвейерная обработка.
Методика разработки параллельных алгоритмов. Модель "процессы-каналы" параллельной программы. Разделение вычислений на независимые части: параллелизм по данным и функциональный параллелизм. Выделение информационных зависимостей: локальные и глобальные, статические и динамические схемы передачи данных, структурные и произвольные, синхронные и асинхронные способы взаимодействия. Масштабирование подзадач. Распределение подзадач по процессорам вычислительной системы.
Составил доцент кафедры МАиМ
