====== Математические методы в разработке программного обеспечения ====== **Длительность**: 250 часов **Стоимость курса**: 25 000 руб **Занятия проходят**: в аудиториях и компьютерных классах мех-мата **Курс читают**: преподаватели и научные сотрудники каф. ТИ **Выдается**: Удостоверение о повышении квалификации установленного в МГУ образца. **Категория слушателей**: сотрудники, студенты ВУЗов, программисты, преподаватели программирования и информатики **Форма обучения**: без отрыва от работы Программа рассчитана на 1 учебный год. Обучение будет проходить в вечерние часы и/или по субботам. **Для связи**: **Тел**. 939 17 86 **Email**: [[mailto:info.ti.msu@mail.ru|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. ==== Требования к результатам обучения: ==== В результате обучения слушатели должны: получить навыки программирования на современном объектно-ориентированном языке, знать классические алгоритмы сортировки, алгоритмы на графах и строках, знать и уметь применять ключевые структуры данных, уметь оценивать сложность и эффективность алгоритмов, знать основы вычислительных методов, методы линейного программирования, основы теории чисел, алгоритмы и инфраструктуру криптографии с открытым ключом, получить опыт разработки веб-приложений и баз данных.