«Математические методы в разработке программного обеспечения»

Математические методы в разработке программного обеспечения

250

134

116

Итоговая аттестация

Экзамен,

зачет

1.

Объектно-ориентированное программирование

50

16

16

18

2.

Алгоритмы и структуры данных

90

40

24

26

3.

Вычислительные методы и линейное программирование

60

18

20

22

4.

Теоретико-числовые алгоритмы и приложения к криптографии

50

24

12

14

5.

Интернет-технологии и веб-разработка

78

20

28

30

6.

Базы данных

50

16

16

18

1. Объектно-ориентированное программирование

16

16

18

1.1. Базовые типы и управляющие конструкции. Массивы, итераторы, работа с консолью и файлами. Исключения и их обработка.

4

4

4

1.2. Классы: наследование, полиморфизм, инкапсуляция. Модификаторы доступа, статические методы. Абстрактные классы и интерфейсы. Стандартные контейнеры.

6

4

4

1.3. Современные управляемые языки: Java и C#. Виртуальные машины, JIT-компиляция, автоматическая сборка мусора. Информация о типах данных времени исполнения, сериализация.

2

2

4

1.4. Программирование оконных приложений. Событийное программирование. Основы работы с графикой.

4

6

6

2. Алгоритмы и структуры данных

40

24

26

2.1. Сложность алгоритмов. Метод "разделяй и властвуй". Бинарный поиск, алгоритмы сортировки: выбором, вставками, слиянием, быстрая сортировка. Элементы компьютерной алгебры: умножение многочленов, матриц, быстрое преобразование Фурье.

4

2

2

2.2. Базовые структуры данных: стек, очередь, вектор. Очередь с приоритетами, реализация с помощью бинарной кучи. Пирамидальная сортировка. Система непересекающихся множеств.

4

2

2

2.3. Алгоритмы в графах. Поиск в ширину и глубину, топологическая сортировка, определение сильных компонент связности ориентированных графов. Поиск кратчайшего пути, алгоритм Дейкстры.

4

2

2

2.4. Жадные алгоритмы. Задача кэширования и задача о составлении расписания. Минимальные остовные деревья, алгоритмы Прима и Крускала.

4

4

4

2.5. Динамическое программирование. Алгоритмы Беллмана-Форда и Флойда-Уоршелла.

4

2

4

2.6. Хеш-таблицы. Бинарные деревья поиска. Сбалансированные деревья. AVL и красно-черные деревья.

6

4

4

2.7. Алгоритмы работы со строками. Поразрядная сортировка, деревья поиска, поиск подстроки. Оптимальный префиксный код Хаффмана. Расстояние Левенштейна.

8

4

4

2.8. NP-полные задачи. Задача о рюкзаке и задача коммивояжера. Методы решения NP-задач.

6

4

4

3. Вычислительные методы и линейное программирование

18

20

22

3.1. Основы вычислительных методов. Понятие машинного нуля, численное дифференцирование и интегрирование. Поиск корней методом деления пополам, алгоритм Ньютона.

2

2

2

3.2. Метод наименьших квадратов. Системы линейных уравнений. Метод Гаусса.

2

4

4

3.3. Задача линейного программирования. Геометрическая интерпретация, структура множества допустимых значений. Базисы и вырожденность. Двойственная задача линейного программирования. Симплекс-метод.

6

6

8

3.4. Задача целочисленного линейного программирования. NP-полнота. Метод отсечения, метод ветвей и границ.

4

4

4

3.5. Решение комбинаторных задач методами линейного программирования.

4

4

4

4. Теоретико-числовые алгоритмы и приложения к криптографии

24

12

14

4.1. НОД и алгоритм Евклида. Кольцо вычетов, китайская теорема об остатках. Основы теории групп, малая теорема Ферма, теорема Эйлера.

4

2

2

4.2. Символ Лежандра, квадратичный закон взаимности Гаусса. Задача дискретного логарифмирования.

4

2

2

4.3. Вероятностные тесты на простоту. Числа Кармайкла. Тест Рабина-Миллера.

6

2

4

4.4. Криптография с открытым ключом.Алгоритмы Диффи-Хеллмана и RSA. Хеширование, цифровая подпись.

6

4

4

4.5. Инфраструктура PKI: сертификационные центры, управление сертификатами.

4

2

2

5. Интернет-технологии и веб-разработка

20

28

30

5.1. Введение в многопоточное программирование и примитивы синхронизации.

2

2

2

5.2. IP протокол, сетевая адресация. Создание классического многопоточного сервера и клиентского приложения.

2

2

2

5.3. HTTP и другие текстовые сетевые протоколы (FTP, SMTP, POP3). Криптография в сети и безопасные протоколы.

2

2

2

5.4. Язык разметки гипертекстовых страниц HTML. Каскадные таблицы стилей CSS.

4

6

6

5.5. Способы кодирования текста. Форматы хранения и передачи данных XML, JSON, BSON.

2

2

2

5.6. Создание веб-приложения с использованием паттерна MVC.

4

8

10

5.7. Язык Javascript. Интерактивные веб-приложения с использованием технологии AJAX.

4

6

6

6. Базы данных

16

16

18

6.1. Обзор моделей баз данных. Реляционные базы данных. Таблицы, индексы, внешние ключи.

4

2

2

6.2. Реляционная алгебра. Язык запросов SQL.

4

4

4

6.3. Создание базы данных. Доступ к базам данных из приложений. Веб-приложение, работающее с базой данных.

4

6

6

6.4. NoSQL-хранилища, их типы и использование.

4

4

6