Алгоритмизация и программирование

Бакалавриат 2019/2020

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Информационная безопасность)

Направление: 10.03.01. Информационная безопасность

Кто читает: Департамент компьютерной инженерии

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 1-й курс, 1-4 модуль

Формат изучения: с онлайн-курсом

Преподаватели: Крещук Алексей Андреевич

Язык: русский

Кредиты: 12

Контактные часы: 140

Полная версия программы учебной дисциплины

Аннотация

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

Цель освоения дисциплины

− освоение технологии структурного программирования;
− изучение базовых элементов языков Python и C/C++;
− изучение стандартных алгоритмов обработки различных структур данных;
− изучение приёмов разработки алгоритмов для обработки различных структур данных.

Планируемые результаты обучения

Умеет оценивать сложность алгоритмов.
Знает алгоритмы поиска и сортировки с наименьшей асимптотической сложностью.
Умеет использовать динамическое программирование и метод «разделяй и властвуй» для проектирования алгоритмов.
Знает основные структуры данных, такие как очередь, список, хеш-таблица, красно-чёрное дерево.
Умеет выбрать подходящую структуру данных для решения конкретной задачи.
Знает определения Тьюринг-полноты и NP-полноты.
Знает основы языка программирования Python.
Умеет использовать основные конструкции языка, такие как ветвления циклы, generator expressions.
Умеет реализовывать свои функции и классы.
Знает основы языка программирования C++.
Знает основные коллекции и алгоритмы стандартной библиотеки.
Понимает внутреннее устройство большей части алгоритмов из стандартной библиотеки.

Содержание учебной дисциплины

Тема 1. Алгоритмы и их сложность. Алгоритмы поиска и сортировки.
Введение в алгоритмы. Сложность алгоритма поиска элемента в массиве. Вычисление сложности по дереву решений. Границы на минимальную сложность. Алгоритмы сортировки. Дерево решений для сортировки. Алгоритм сортировки слиянием, имеющий минимальную асимптотическую сложность.
Тема 2. Основные методы проектирования алгоритмов.
Методы построения алгоритмов. Динамическое программирование. Метод "разделяй и властвуй". Жадные алгоритмы. Алгоритмы поиска заданной подстроки в длинной строке.
Тема 3. Структуры данных.
Понятие структур данных и операций над ними. Пространственная сложность. Базовые структуры: массив, списки, стек, очередь. Двоичные деревья. Красно-чёрные деревья. Сортирующие деревья (очередь с приоритетом). Пирамидальная сортировка. Хеш таблицы. Алгоритмы хеширования.
Тема 4. Общая теория сложности задач
Общая теория сложности задач. Машины Тьюринга. Классы P и NP.
Тема 5. Python.
Синтаксис Python. Управляющие структуры. Осваиваем Jupyter Notebook. Массивы, графики. Функции. Рекурсия. Области видимости. Типы данных. Работа с файлами. Управление ресурсами. Словари. Операции со строками. Классы и объекты. Наследование. Обработка ошибок. Тесты.
Тема 6. C++
Синтаксис C++, базовая программа. Среда разработки. Ввод и вывод. Управляющие структуры. Функции. Типы данных. Указатели и ссылки. Основные коллекции. Интеграция с Python (pybind11 и cppimport). Итераторы. Диапазоны (ranges) и современная работа с последовательностями. Основные алгоритмы. Структуры. Переопределение операторов. Модель компиляции. Модель памяти. Модель исполнения. Обработка ошибок в С++. Классы и наследование.

Элементы контроля

домашнее задание №1
групповой проект на ЯП Python
экзамен (2 модуль)
домашнее задание №2
групповой проект на ЯП С++
экзамен (4 модуль)
Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Jitsi (http://meet.miem.hse.ru/). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Jitsi. Для участия в экзамене студент обязан: явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи подразумевает использование усложненных заданий.

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.4 * групповой проект на ЯП Python + 0.3 * домашнее задание №1 + 0.3 * экзамен (2 модуль)
Промежуточная аттестация (4 модуль)
0.2 * групповой проект на ЯП С++ + 0.2 * домашнее задание №2 + 0.5 * Промежуточная аттестация (2 модуль) + 0.1 * экзамен (4 модуль)

Программа дисциплины