Delivered at:: School of Linguistics

Course type:: Elective course

When:: 3 year, 2-4 module

Instructors

Zakharova, Elena

Kuznetcov, Maksim

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

Аннотация

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

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

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

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

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

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

Объектно-ориентированное программирование
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. Интерпретация моделей машинного обучения.
Модели данных и вычислений. Язык программирования Go.
Анализ алгоритмов
Базовые структуры данных
Сортировка
Деревья
Деревья (продолжение)
Словари и множества
Динамическое программирование
Алгоритмы на графах
Алгоритмы на строках

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

Самостоятельная работа (П)
самостоятельные работы на 10-20 мин на семинарах несколько раз в модуль; в расчете оценки используется среднее арифметическое оценок за эти работы
Домашнее задание (П)
домашние работы несколько раз в модуль; в расчете оценки используется среднее арифметическое оценок за эти работы во втором модуле
Контрольная работа (П)
Экзамен (П)
Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Zoom (https://zoom.us/). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom. Для участия в экзамене студент обязан: явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи подразумевает использование усложненных заданий.
Индивидуальный проект (П)
индивидуальный проект с последующей устной защитой по предложенным преподавателям темам (в том числе по смежным темам, не рассмотренных в основной части курса) для получения дополнительных баллов
Домашнее задание 2 (П)
домашние работы несколько раз в модуль; в расчете накопленной оценки используется среднее арифметическое оценок за эти работы во втором и третьем модулях
Контрольная работа 2 (П)
домашнее задание (ТА)
Домашняя работа подлежит пересдаче в виде очного решения задач аналогичных домашним по нескольким произвольным темам. Пересдача длится до 2-х часов на одного студента. Во время решения не разрешается пользоваться электронными устройствами и учебными материалами.

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

Промежуточная аттестация (2 модуль)
Оценка за второй модуль равна оценке за домашние задания.
Промежуточная аттестация (4 модуль)
Курс состоит из двух частей: "программирование" (П) и "теория алгоритмов" (ТА), итоговая оценка - 0,6П+0,4ТА. Оценка за часть"программирование": 0.12*СР + 0.12*КР1 + 0.12*КР2 + 0.1*ДЗ1 + 0.12* ДЗ2 + 0.12*Проект+0.4*Экз1. Если округленная по стандартным правилам оценка > 10, она считается равной 10. Оценка за часть "теория алгоритмов" равна среднему арифметическому оценок за домашние задания.

Bachelor’s Programme 'Fundamental and Computational Linguistics'

Programming and Theory of Algorithms

Instructors

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

Аннотация

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

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

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

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

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

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

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

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