Математические методы в разработке программного обеспечения
Длительность: 250 часов
Стоимость курса: 25 000 руб
Занятия проходят: в аудиториях и компьютерных классах мех-мата
Курс читают: преподаватели и научные сотрудники каф. ТИ
Выдается: Удостоверение о повышении квалификации установленного в МГУ образца.
Категория слушателей: сотрудники, студенты ВУЗов, программисты, преподаватели программирования и информатики
Форма обучения: без отрыва от работы
Программа рассчитана на 1 учебный год. Обучение будет проходить в вечерние часы и/или по субботам.
Для связи:
Тел. 939 17 86
Email: info.ti.msu@mail.ru
Учебный план программы:
| № п/п | Наименование разделов | Всего, час. | в том числе | |
|---|---|---|---|---|
| лекции | практические и лабораторные занятия | |||
| Математические методы в разработке программного обеспечения | 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 |
Итоговая аттестация состоит из защиты выпускной квалификационной работы, включающей написание алгоритма решения задачи, его реализацию и определение сложности этой реализации.
Учебно-методическое обеспечение программы:
- Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
- Борисенко В.В. Основы программирования. – М.: ИнтУИТ, 2005.
- Валединский В.Д., Пронкин Ю.Н., Вычислительные системы и программирование. I, II. – М.: Изд-во МГУ, 2000.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. – М.: Мир, 1987.
- Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – М.: МЦНМО, 2014
- Кнут Д. Искусство программирования для ЭВМ. Т.1-3. – М., СПб., Киев: Вильямс, 2000.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 200, 2001.
- Панкратьев Е.В. Элементы компьютерной алгебры. – М.: ИнтУИТ, 2007.
- Фергюсон Н., Шнейер Б. Практическая криптография. – М.: Вильямс, 2005.
- Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, 1995.
- Шнайер Б. Прикладная криптография. – М.: Триумф, 2002.
- Шнайер Б. Секреты и ложь. Безопасность данных в цифровом мире. – СПб: Питер, 2000.
Требования к результатам обучения:
В результате обучения слушатели должны: получить навыки программирования на современном объектно-ориентированном языке, знать классические алгоритмы сортировки, алгоритмы на графах и строках, знать и уметь применять ключевые структуры данных, уметь оценивать сложность и эффективность алгоритмов, знать основы вычислительных методов, методы линейного программирования, основы теории чисел, алгоритмы и инфраструктуру криптографии с открытым ключом, получить опыт разработки веб-приложений и баз данных.