Роль алгоритмов в работе физика

Устройство Python было рассмотрено в предыдущем разделе, однако за ним стоит фундамент, переживающий и смену языка, и смену моды, — базовые знания computer science.

Алгоритмическая грамотность представляет собой умение заранее оценить, выполним ли расчёт за приемлемое время. Миллион событий детектора, обрабатываемый алгоритмом за \(O(n^2)\), приводит к триллиону операций, и NumPy, написанный на C, уменьшает лишь константу, но не порядок роста: расчёт сократится с часов до десятков минут, тогда как алгоритм \(O(n \log n)\) выполнит ту же работу меньше чем за секунду. Удачно выбранная структура данных сокращает время счёта на порядки, причём чаще, чем низкоуровневая оптимизация.

Слайды к главе. Материал первых трёх глав раздела изложен также в лекции «Алгоритмы и сложность» (алгоритм и O-нотация, время и память, память и массивы, списки и очереди, стек вызовов и рекурсия, сортировки) с демонстрациями в терминале; слайды лекции доступны на сайте книги и в PDF.

Слайды к главе. Материал глав о хеш-функциях, деревьях и графах изложен также в лекции «Хеши, деревья и графы» (хеш-таблицы и хеш-функции, деревья и деревья поиска, кучи, графы, кратчайшие пути и остов) с демонстрациями в терминале; слайды лекции доступны на сайте книги и в PDF.

В настоящем разделе рассматриваются:

  • Введение в алгоритмы, где вводится понятие алгоритма и разбирается оценка сложности, не привязанная к конкретной машине;
  • Основные структуры данных, где разобраны массивы, списки, стеки, очереди и деки и показано, как они представлены в Python;
  • Рекурсия и сортировки, где разобраны сортировка слиянием, быстрая сортировка и сортировка подсчётом;
  • Хеш-функции, объясняющие, почему словарь ищет в среднем за \(O(1)\) и как устроены хеш-таблицы;
  • Деревья, иерархические структуры, дополненные деревьями поиска и кучами;
  • Графы, их представления, обходы и классические задачи, решаемые обходом.

Материал построен на разборе задач: сначала излагается необходимая теория, затем приводятся задачи с решениями, расписанными на Python. Рекомендуется сперва попытаться решить задачу самостоятельно и только после этого обращаться к разбору.