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

Статус:: Курс обязательный

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

Преподаватели

Дерендяев Александр Борисович

Крещук Алексей Андреевич

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

Аннотация

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

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

Введение в теорию сложности алгоритмов
Изучение основных подходов к проектированию алгоритмов
Изучение основных структур данных
изучение базовых элементов языков Python и C++

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

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

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

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

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

Домашние задания
Дистанционный устный экзамен
Преподаватель вправе освободить от прохождения экзамена студентов, с выставлением им во время сессии оценки по промежуточной аттестации, соответствующей накопленной оценке без учёта веса экзамена (то есть сумма весов всех элементов контроля, за исключением экзамена, приравнивается к единице). Преподаватель объявляет свое решение не позднее, чем на последнем занятии до экзамена. Для объявления оценок могут быть использованы официальные каналы передачи информации, используемые в процессе обучения. По желанию студентов, они могут отказаться от выставления оценки без проведения экзамена и сдать его, о чем сообщают преподавателю не позднее последнего занятия. Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Jitsi https://meet.miem.hse.ru К экзамену необходимо подключиться согласно расписанию ответов. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Jitsi. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение более одной минуты. При долговременном нарушении связи студент не может продолжить участие в экзамене.
Групповой проект
Дистанционный формат со 2-го модуля.
Домашние задания
3 и 4 модули
Групповой проект
3 и 4 модули
Устный экзамен
3 и 4 модули. Преподаватель вправе освободить от прохождения экзамена студентов, с выставлением им во время сессии оценки по промежуточной аттестации, соответствующей накопленной оценке без учёта веса экзамена (то есть сумма весов всех элементов контроля, за исключением экзамена, приравнивается к единице). Преподаватель объявляет свое решение не позднее, чем на последнем занятии до экзамена. Для объявления оценок могут быть использованы официальные каналы передачи информации, используемые в процессе обучения. По желанию студентов, они могут отказаться от выставления оценки без проведения экзамена и сдать его, о чем сообщают преподавателю не позднее последнего занятия. Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Jitsi https://meet.miem.hse.ru К экзамену необходимо подключиться согласно расписанию ответов. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Jitsi. Для участия в экзамене студент обязан: явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение более одной минуты. При долговременном нарушении связи студент не может продолжить участие в экзамене.

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

Промежуточная аттестация (2 модуль)
0.4 * Групповой проект + 0.2 * Дистанционный устный экзамен + 0.4 * Домашние задания
Промежуточная аттестация (4 модуль)
0.2 * Групповой проект + 0.2 * Домашние задания + 0.5 * Промежуточная аттестация (2 модуль) + 0.1 * Устный экзамен

Бакалаврская программа «Информационная безопасность»

Контакты

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

Преподаватели

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

Аннотация

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

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

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

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

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

Список литературы

Рекомендуемая основная литература

Рекомендуемая дополнительная литература