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

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

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

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

Аннотация

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

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

  • − освоение технологии структурного программирования;
  • − изучение базовых элементов языков 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 модуль)
Список литературы

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

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

  • Алгоритмы: построение и анализ, Кормен, Т., 2011
  • Изучаем Python, Лутц, М., 2014
  • Солтис М. - Введение в анализ алгоритмов - Издательство "ДМК Пресс" - 2019 - 278с. - ISBN: 978-5-97060-696-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/123707
  • Трофимов В. В., Павловская Т. А. ; Под ред. Трофимова В.В. - АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ. Учебник для академического бакалавриата - М.:Издательство Юрайт - 2019 - 137с. - ISBN: 978-5-534-07834-3 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/algoritmizaciya-i-programmirovanie-423824

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

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