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

Программирование и теория алгоритмов

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Направление: 45.03.03. Фундаментальная и прикладная лингвистика
Когда читается: 3-й курс, 2-4 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 5

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

Аннотация

Первая часть курса знакомит слушателей с основными принципами объектно-ориентированного программирования, в том числе применительно к языку программирования Python, а также с некоторыми возможностями и модулями стандартной библиотеки этого языка. Также рассматриваются темы, связанные с архитектурой ПО (например, основные шаблоны проектирования) и тестированием приложений. Вторая часть курса посвящена базовым алгоритмам и структурам данных. Третья часть курса знакомит слушателей с основами машинного обучения, детально рассматриваются линейная и логистическая регрессия, а также векторизация текстов.
Цель освоения дисциплины

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

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

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

  • Освоить принципы объектно-ориентированного программирования и научиться применять их при работе с языком Python
  • Уметь оценивать алгоритмы с точки зрения вычислительной сложности и потребляемой памяти и сравнивать алгоритмы
  • Уметь использовать функции из библиотек scikit-learn, реализующие линейную и логистическую регрессию
  • Знать английские эквиваленты всех используемых в курсе терминов и понятий, уметь пользоваться документацией на английском языке
  • Научиться реализовывать базовые структуры данных на языке Python
  • Освоить ряд стандартных алгоритмов и уметь реализовывать эти алгоритмы на языке Python
  • Уметь решать практические задачи, сводимые к ряду стандартных задач, для решения которых существуют реализованные алгоритмы
  • Владеть навыками первичной обработки данных и формализации задач обучения с учителем
  • Владеть основными функциями модулей numpy, pandas, scikit-learn в языке Python
  • Уметь реализовывать линейную и логистическую регрессию на языке программирования Python
  • Владеть навыками интерпретации результатов простейших моделей машинного обучения
  • Знать устройство базовых числовых и строковых типов данных, принципы исполнения программы
  • Знать основные техники оценки и сравнения времени работы алгоритмов
  • Знать основные алгоритмы сортировки и их сложность
  • Знать несколько реализаций словарей и множеств, их свойства и области применения
  • Понимать общую концепцию динамического программирования и умеет сводить к нему практические задачи
Содержание учебной дисциплины

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

  • Объектно-ориентированное программирование
    1. Функции и области видимости, встроенные типы данных, модули и пространство имен. Передача аргументов в функцию. 2. Тестирование ПО (модули doctest, unittest). Стандарт PEP8. Виртуальные окружения. 3. Итераторы и генераторы. 4. Класс, объект. Конструктор и деструктор. Композиция и агрегация. Абстракция данных, инкапсуляция, наследование, полиморфизм. 5. Перегрузка операторов. Исключения. 6. Декораторы. Метаклассы. Абстрактные классы. Статические методы и методы классов (модуль abc).
  • Введение в алгоритмы и структуры данных
    1. Модели данных и вычислений 2. Задача сортировки массива. Наивные и квадратичные алгоритмы сортировки. Сложность алгоритмов и нотация Big-O. Устойчивость сортировок и дополнительные затраты на память. 3. Принцип «разделяй и властвуй». Сортировка слиянием. Быстрая сортировка. Бинарный поиск. 4. Абстрактный тип данных. Очередь, стек, связный список, массив, очередь с приоритетом. 5. Ассоциативный массив. Хэш-таблицы, словари, множества 6. Графы. Базовые алгоритмы на графах: поиск в глубину, поиск в ширину; алгоритм Дейкстры; топологическая сортировка; алгоритм Прима (модуль networkx). 7. Жадные алгоритмы. 8. Модуль collections в Python.
  • Введение в машинное обучение. Введение в анализ текстов.
    1. Основы матричной алгебры. Матричные разложения. Методы оптимизации. 2. Обучение на размеченных данных. Признаки в машинном обучении. Первичная обработка данных. Отбор признаков. 3. Модули numpy, scikit-learn, scipy, pandas. Jupyter Notebook. 4. Линейные модели. Логистическая регрессия. Проблема переобучения. Регуляризация. 5. Метрики качества. Кросс-валидация. Несбалансированные данные. Многоклассовая классификация. 6. Векторизация текстов. TF-IDF. 7. Интерпретация моделей машинного обучения.
Элементы контроля

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

  • неблокирующий Домашнее задание 34
    Домашние работы в 3-4 модулях; в расчете оценки используется среднее арифметическое оценок за эти работы
  • неблокирующий Контрольная работа
    Контрольная работа по программированию
  • неблокирующий Экзамен
    Устный или письменный экзамен по усмотрению преподавателей
  • неблокирующий Проект
    Индивидуальный или групповой проект с последующей устной защитой по предложенным преподавателям темам (в том числе по смежным темам, не рассмотренных в основной части курса)
  • неблокирующий Домашнее задание 2
    домашние работы во 2 модуле; в расчете оценки используется среднее арифметическое оценок за эти работы
  • неблокирующий Коллоквиум
    Устный коллоквиум по машинному обучению
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.1 * Домашнее задание 2 + 0.2 * Домашнее задание 34 + 0.12 * Коллоквиум + 0.12 * Контрольная работа + 0.11 * Проект + 0.35 * Экзамен
Список литературы

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

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

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.

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

  • Гринченков Д.В., Потоцкий С.И. - Математическая логика и теория алгоритмов для программистов - КноРус - 2017 - 206с. - ISBN: 978-5-406-05421-5 - Текст электронный // ЭБС BOOKRU - URL: https://book.ru/book/919851