• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

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

Статус: Курс обязательный (Информационная безопасность)
Направление: 10.03.01. Информационная безопасность
Когда читается: 1-й курс, 1-4 модуль
Формат изучения: без онлайн-курса
Преподаватели: Дерендяев Александр Борисович, Иванов Федор Ильич, Крещук Алексей Андреевич
Язык: русский
Кредиты: 12

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

Аннотация

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

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

  • Введение в теорию сложности алгоритмов
  • Изучение основных подходов к проектированию алгоритмов
  • Изучение основных структур данных
  • изучение базовых элементов языков 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 * Устный экзамен
Список литературы

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

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

  • Алгоритмы: построение и анализ, Кормен, Т., 2011
  • Изучаем Python, Лутц, М., 2014
  • Программирование : принципы и практика с использованием С++, Страуструп, Б., 2018

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

  • Python. Самое необходимое, Прохоренок, Н. А., 2015
  • Северенс Ч. - Введение в программирование на Python - Национальный Открытый Университет "ИНТУИТ" - 2016 - 231с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100703