Программа осеннего семестра по задавальнику - mipt-cs/course-site-python3 GitHub Wiki

П Р О Г Р А М М А

по дисциплине: Информатика
по направлению: 03.03.01 «Прикладные математика и физика»
факультет: ФМХФ, 1 курс, 1 семестр
Дифф. зачет – 1 семестр

Программу и задание составил ст. преп. Т.Ф. Хирьянов

Лекции

На лекциях разбираются алгоритмы, излагается теория информатики, объясняются концепции, которые сложно понять самостоятельно. Лекции являются основой данного курса, их пропуск существенно усложняет выполнение лабораторных работ.

Синтаксис языка Python 3. Концепция присваивания. Арифметические операции в Python. Цикл while. Инструкции управления циклом. Вложенный цикл while. Цикл for и его особенности в Python. Функция range(). Условный оператор if.
Основы алгебры логики. Таблицы истинности и логические законы. Дизъюнктивная и конъюнктивная нормальные формы. Тип bool и логические операции в Python. Вложенные и каскадные условные конструкции.
Позиционные системы счисления. Разложение числа на цифры. Однопроходные алгоритмы: подсчёт, сумма, произведение, поиск числа в потоке, максимум. Алгоритм Евклида.
Функции в Python. Декомпозиция задач. Структурное программирование. Проектирование «сверху-вниз». Метод грубой силы. Тест простоты числа. Разложение числа на множители. Бисекция: поиск корня функции.
Массивы. Линейный поиск в массиве. Алгоритм обращения массива. Алгоритм циклического сдвига в массиве. Добавление и удаление элемента в конец и в начало массива. Ссылочная модель данных в Python. Операторы == и is. Решето Эратосфена.
Сортировки. Квадратичные сортировки: вставками, выбором и методом пузырька. Сортировка подсчётом. Поразрядная сортировка.
Рекурсия. Прямой и обратный ход рекурсии. Факториал числа. Рекурсивный алгоритм Евклида. Быстрое возведение в степень. Ханойские башни.
Быстрая сортировка Хоара. Устойчивость сортировок. Генерация всех перестановок (рекурсивная).
Сортировка слиянием. Слияние двух упорядоченных массивов. Проверка упорядоченности массива за O(N). Проблема алгоритмической сложности задачи. Бинарный поиск в массиве за O(logN).
Динамическое программирование. Вычисление чисел Фибоначчи и проблема перевычислений. Рекурсия с кешированием. Алгоритм укладки рюкзака.
Примеры динамического программирования. Наибольшая общая подпоследовательность. Наибольшая возрастающая подпоследовательность. Вычисление расстояния Левенштейна. Поиск последовательности редакционных изменений.
Строки. Проверка равенства строк. Простой и вероятностный алгоритмы. Поиск подстроки в строке. Префикс-функция и z-функция. Z-алгоритм. Алгоритм Кнута-Морриса-Пратта.
Стек. Проверка корректности скобочной последовательности. Обратная Польская нотация.
Пирамида (куча). Пирамидальная сортировка.
Списки и строки в Python. Методы строк find, count, replace. Методы списков append, extend, pop. Срезы списков и строк. Присваивание в срез списка. Стандартные функции len, max, min, sum. Методы split и join.

Лабораторные работы

Список и содержание лабораторных работ публикуется на сайте http://judge.mipt.ru/mipt_cs_on_python3/, при этом доступ к ним открывается по ходу семестра.

Система контроля и оценки

В семестре предусмотрены две контрольные работы в форме контеста. Дифференцированный зачёт принимается в устной форме, при этом оценки по контрольным и лабораторным работам являются базой для оценки на зачёте.

Литература

Макконнелл Дж. Анализ алгоритмов. Активный обучающий подход. — Техносфера, 2009.
Кормен Томас Х. Алгоритмы. Вводный курс. — М.: И.Д. Вильямс, 2016.
Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. — Питер, 2017.

Дополнительная литература

Саммерфилд М. Программирование на Python 3. Подробное руководство. — М.: Символ-Плюс, 2009.
Лутц М. Python. Карманный справочник. — М.: И.Д.Вильямс, 2014.
Лутц М. Изучаем Python. — М.: Символ-Плюс, 2011.
Лутц М. Программирование на Python. Т.1, 2. — М.: Символ-Плюс, 2011.
Саммерфилд М. Python на практике. — М.: ДМК Пресс, 2014.