Содержание

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

Длительность: 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

Итоговая аттестация состоит из защиты выпускной квалификационной работы, включающей написание алгоритма решения задачи, его реализацию и определение сложности этой реализации.

Учебно-методическое обеспечение программы:

  1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
  2. Борисенко В.В. Основы программирования. – М.: ИнтУИТ, 2005.
  3. Валединский В.Д., Пронкин Ю.Н., Вычислительные системы и программирование. I, II. – М.: Изд-во МГУ, 2000.
  4. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. – М.: Мир, 1987.
  5. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – М.: МЦНМО, 2014
  6. Кнут Д. Искусство программирования для ЭВМ. Т.1-3. – М., СПб., Киев: Вильямс, 2000.
  7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 200, 2001.
  8. Панкратьев Е.В. Элементы компьютерной алгебры. – М.: ИнтУИТ, 2007.
  9. Фергюсон Н., Шнейер Б. Практическая криптография. – М.: Вильямс, 2005.
  10. Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, 1995.
  11. Шнайер Б. Прикладная криптография. – М.: Триумф, 2002.
  12. Шнайер Б. Секреты и ложь. Безопасность данных в цифровом мире. – СПб: Питер, 2000.

Требования к результатам обучения:

В результате обучения слушатели должны: получить навыки программирования на современном объектно-ориентированном языке, знать классические алгоритмы сортировки, алгоритмы на графах и строках, знать и уметь применять ключевые структуры данных, уметь оценивать сложность и эффективность алгоритмов, знать основы вычислительных методов, методы линейного программирования, основы теории чисел, алгоритмы и инфраструктуру криптографии с открытым ключом, получить опыт разработки веб-приложений и баз данных.