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

#	Тема	Дополнительно	Дедлайн
1	Создание простейших программ	checklab1-win, checklab1-mac	Ср 26 фев
2	Массивы и функции	-	Ср 12 мар
3	Интерактивный ввод, файлы и графика	Тестовые файлы	Пт 4 апр
4	Сложность алгоритмов, рекурсия, "разделяй и властвуй", методы сортировки	Тестовые файлы	Ср 16 апр
5	Стек, очередь, куча	Тестовые файлы	Сб 10 май
6	Словари, множества, графы	Тестовые файлы	Сб 10 май
7	Жадные алгоритмы, перебор с возвратом, динамическое программирование	Тестовые файлы	Пн 26 май
БОНУС	Числа Фибоначчи	-	-

Контрольные работы

Всего запланировано 2 очные контрольные работы.

#	Тема	Дополнительно	Задания
1	Темы 1-3	Тестовые файлы	Группа 4б Группа 4а Группа 5а Группа 11а Группа 5б Группа 11б
2	Темы 4-7	Занятие 17	-

Результаты

Смотреть таблицу

Контрольные вопросы

Структуры данных

На зачете нужно показать их реализацию в Python, знать основные методы и их производительность (асимптотику).

1. Список
2. Стек
3. Очередь
4. Бинарная куча
5. Словарь
6. Множество
7. Граф

Математические алгоритмы

На зачете нужно рассказать идею, а также быть готовым написать код на Python.

1. Алгоритм Евклида
2. Вычисление числа Пи (любой из методов)
3. Нахождение нулей функции методом Ньютона
4. Представление числа в заданной системе счисления
5. Разложение числа на множители
6. Генерация булеана (множества всех подмножеств списка)
7. Нахождение списка простых чисел используя решето Эратосфена
8. Приведение матрицы к ступенчатому виду
9. Вычисление интеграла функции (любой из методов)
10. Вычисление произведения матриц
11. Вычисление степени числа при помощи рекурсии
12. Генерация всех перестановок множества элементов

Другие алгоритмы

На зачете нужно рассказать идею, знать асимптотику, а также быть готовым написать код на Python.

1. Бинарный поиск
2. Медленные сортировки: пузырьком, вставками, выбором
3. Сортировка слияниям
4. Быстрая сортировка
5. Вычисление арифметического выражения (обратная польская запись)
6. Вычисление арифметического выражения (инфиксная запись)
7. Реализация очереди с приоритетом при помощи бинарной кучи
8. Сортировка кучей
9. Обход графа в ширину
10. Обход графа в глубину
11. Нахождение кратчайших расстояний в графе методом Дейкстры
12. Построение минимального остовного дерева алгоритмом Прима
13. Перебор с возвратом (бэктрекинг)
14. Размер монет (жадная стратегия и динамическое программирование
15. Решение задачи о рюкзаке 0-1

Литература

Введение в ИТ

• Джастис М. Как на самом деле работают компьютеры. Практическое руководство по внутреннему устройству машины / Пер. с англ. — ДМК Пресс, 2022.
• Петцольд Ч. Код. Тайный язык информатики / Пер. с англ. — МИФ, 2019.
• Спрингер В. Гид по Computer Science / Пер. с англ. — Питер, 2021.
• Феррейра Фило В. Теоретический минимум по Computer Science. Все, что нужно программисту и разработчику / Пер. с англ. — Питер, 2018.

Python

• Дауни А. Основы Python. Научитесь думать как программист / Пер. с англ. — МИФ, 2021.
• Любанович Б. Простой Python. Современный стиль программирования / Пер. с англ. — Питер, 2021.
• Рамальо Л. Python — к вершинам мастерства. Лаконичное и эффективное программирование / Пер. с англ. — МК Пресс, 2022.
• Седжвик Р., Уэйн К., Дондеро Р. Программирование на языке Python: учебный курс / Пер. с англ. — Альфа-книга, 2017.
• Хилл К. Научное программирование на Python / Пер. с англ. — ДМК Пресс, 2021.
• Харрисон М. Как устроен Python. Гид для разработчиков, программистов и интересующихся / Пер. с англ. — Питер, 2019.
• Шихи Д. Р. Структуры данных в Python: начальный курс / Пер. с англ. — ДМК Пресс, 2022.

Алгоритмы

• Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих / Пер. с англ. — Питер, 2022.
• Венгроу Дж. Прикладные структуры данных и алгоритмы. Прокачиваем навыки / Пер. с англ. — Питер, 2024.
• Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / Пер. с англ. — Издательство МЦНМО, 2014.
• Копец Д. Классические задачи Computer Science / Пер. с англ. — Питер, 2020.
• Курносов М. Г. Введение в методы машинной обработки данных — Автограф, 2020.
• Луридас П. Алгоритмы для начинающих: теория и практика для разработчика / Пер. с англ. — Эксмо, 2018.
• Солтис М. Введение в анализ алгоритмов / Пер. с англ. — ДМК Пресс, 2019.
• Стивенс Р. Алгоритмы. Теория и практическое применение / Пер. с англ. — Издательство Э, 2016.
• Хайнеман Дж. Алгоритмы. С примерами на Python / Пер. с англ. — Питер, 2023.