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

#ТемаДополнительноДедлайн
1Создание простейших программ-Вт 20 фев
2Массивы и функции-Вт 5 мар
3Интерактивный ввод, файлы и графикаАрхив с файламиСб 23 мар
4Сложность алгоритмов, рекурсия, "разделяй и властвуй", методы сортировки-Вт 9 апр
5Стек, очередь, кучаСб 4 май
6Словари, множества, графыАрхив с файламиВт 21 май
7Жадные алгоритмы, перебор с возвратом, динамическое программированиеАрхив с файламиВт 21 май
БОНУСЧисла Фибоначчи--

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

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

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

Список алгоритмов

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

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

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

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

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

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

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

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

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