Как оптимизировать сложность алгоритмов

YOUTUBE · 30.11.2025 06:28

Ключевые темы и таймкоды

Введение

0:00

Ведущие подкаста "Подлодка" Егор Толстой, Катя Петрова и Женя Кателло приветствуют зрителей.
Напоминают о переходе на YouTube для лучшего восприятия контента.
Представляют гостя выпуска - Александра Куликова, доктора физико-математических наук и руководителя лаборатории алгоритмов и теории сложности в JetBrains Research.

Теория сложности

1:56

Александр Куликов рассказывает о своем интересе к теории сложности.
Теория сложности изучает, почему для некоторых задач до сих пор не придуманы быстрые алгоритмы.
Лаборатория, где работает Александр, занимается чисто исследовательской работой, не имеющей практических применений.

Алгоритмы и программисты

5:54

Обсуждается, нужны ли алгоритмы программистам.
Александр делится своим опытом создания образовательных материалов и объясняет, что алгоритмы важны для получения офферов в топовые компании.
Алгоритмическое мышление помогает программистам избегать написания неэффективного кода.

Красота алгоритмов

9:47

Александр объясняет, что красота алгоритмов субъективна и зависит от личного восприятия.
Приводит примеры красивых алгоритмов, таких как быстрое преобразование Фурье и алгоритм Дийеса.
Подчеркивает, что красота алгоритмов может быть как привлекательной, так и раздражающей для разных людей.

Теория сложности

13:43

Теория сложности изучает количество ресурсов, необходимых для решения задачи.
Основной ресурс - время, и интересует, как оно растет с ростом входа.
Цель теории сложности - понять, за какое самое быстрое время можно решить задачу.

Задачи логистики и теория сложности

14:42

Задача логистики требует сортировки объектов, что может быть сложно при большом количестве точек.
Вопрос о существовании более быстрого алгоритма остается открытым.
Теория сложности изучает различные ресурсы, такие как время, память и количество коммуникаций.

Ограниченность алгоритмов и семинар Колмогорова

15:42

Алгоритмов существует множество, и их сложно классифицировать.
Семинар Колмогорова пытался доказать, что перемножение чисел не может быть быстрее, чем n^2.
Алгоритм Карацубы предложил метод перемножения чисел за n^1.7, что стало началом улучшений.

Алгоритмы и их разнообразие

18:40

Алгоритмы могут использовать различные методы, такие как разделение и властвование или комплексные числа.
Сложно придумать математический метод, который бы охватывал все быстрые алгоритмы.
Вопрос о доказательстве отсутствия более оптимального решения остается открытым.

Доказательство существования алгоритмов

20:37

Доказательство существования алгоритмов часто требует конструктивных методов.
Пример с шахматной доской показывает, что дисбаланс клеток может препятствовать замостию.
В теории сложности часто пытаются найти более быстрые алгоритмы для нерешенных задач.

Современные исследования в теории сложности

26:29

Основная работа ученых заключается в поиске более быстрых алгоритмов для нерешенных задач.
Появляются результаты, связывающие задачи, которые на первый взгляд кажутся несвязанными.
Эти связи помогают понять, как алгоритмы могут применяться к другим задачам.

Задача редактирования и её применение

28:28

Задача редактирования определяет минимальное количество правок для преобразования одного слова в другое.
Применяется в биоинформатике для анализа геномных последовательностей.
Проблема в том, что современные компьютеры не могут решить задачу за приемлемое время.

Главный открытый вопрос теории сложности

31:24

Для большинства задач не известно, как выглядит оптимальный алгоритм.
Известные алгоритмы оптимальны только для задач, решаемых за линейное время.
Главный вопрос теории сложности: существуют ли задачи, решение которых можно быстро проверить, но не найти?

Пример задачи судоку

34:20

Судоку можно быстро проверить, но сложно найти решение.
Задачи, для которых решение можно быстро проверить, но не найти, представляют интерес.
Пример задачи логистики: найти маршрут с ограниченным бюджетом.

Полиномиальное и экспоненциальное время

37:18

Полиномиальное время работы считается хорошим, экспоненциальное - плохим.
На практике задачи, решаемые за полиномиальное время, часто решаются за N^2 или N^3.
Эвристические алгоритмы работают хорошо на практике, но не всегда доказывают свою эффективность.

Частные случаи задач

40:14

В теории сложности изучаются частные случаи задач.
Пример: расселение студентов в общежитии с учетом их предпочтений.
Важно найти алгоритмы, работающие в ограниченных условиях, что является частью теории сложности.

Задача независимого множества

42:12

Задача независимого множества NP-полная.
Перебор всех подмножеств размера 100 из 400 невозможен.
Если бы удалось решить эту задачу, это доказало бы, что P = NP.

Важность решения NP-полных задач

43:10

Решение NP-полных задач может привести к доказательству P = NP.
Институт Клэя предлагает миллион долларов за решение таких задач.
Если задача NP-полная, это не означает, что её нельзя решить в частном случае.

Почему именно эти задачи?

44:09

Институт Клэя выбрал эти задачи как маяки для исследований.
Решение этих задач может привести к мировой славе.
Некоторые математики считают, что эти задачи могут быть решены.

Триллер о решении NP-полной задачи

46:07

В трейлере показали ученых, решающих NP-полную задачу.
Алгоритм, решающий NP-полную задачу, может быть использован для взлома шифров.
Фильм не был завершен, но вызвал интерес у коллег.

Популярность теории сложности вычислений

48:06

Теория сложности вычислений популярна среди ученых.
Конференции по теории сложности привлекают около 500 участников.
Машинное обучение и криптография также популярны, но имеют свои особенности.

Сравнение с другими областями

53:00

Теория сложности вычислений сравнима по популярности с криптографией.
Биоинформатика также имеет значительное сообщество.
Популярность измеряется количеством участников на конференциях и цитируемостью в научных журналах.

Влияние Twitter и цитируемость

56:53

В машинном обучении важно оставаться в курсе последних достижений через Twitter.
Индекс цитируемости H-index определяется количеством ссылок на работы.
Пример: статья с 20,000 ссылок в биоинформатике, что значительно больше, чем у других статей автора.

Влияние биоинформатики

57:52

Автор занимался биоинформатикой, но не добился значительных успехов.
Одна из его статей в биоинформатике получила 20,000 ссылок, что делает её топовой.
Программа, разработанная Павлом Перзнером, используется биологами для сборки геномов.

Влияние теории сложности на бизнес

59:50

Компании редко вкладываются в теорию сложности напрямую.
Теория сложности может быть полезна для разработки алгоритмов и эвристик.
Автор также занимается обучением студентов и настройкой образовательных программ.

Доказательство отсутствия быстрых алгоритмов

1:02:46

Доказать отсутствие быстрого алгоритма для задачи можно, если существует нижняя оценка.
Пример: задача поиска элементов в массиве не решается быстрее, чем за время, равное количеству элементов.
В теории сложности рассматриваются ограниченные модели вычислений, такие как сравнение попарных элементов.

Ограниченные модели вычислений

1:04:44

Пример с шарами показывает, что для сортировки требуется N log N сравнений.
Алгоритмы, основанные на сравнении попарных элементов, вынуждены делать N log N сравнений.
Для задач с известными объектами, такими как биты, можно использовать более эффективные методы сортировки.

Практические подходы к сложным задачам

1:09:38

Для интересных задач можно доказать отсутствие быстрых алгоритмов, если алгоритм сильно ограничен.
На практике важно рассматривать частные случаи и использовать эвристики для решения сложных задач.

NP-полные задачи и эвристики

1:10:35

NP-полные задачи не имеют оптимального алгоритма для всех входов.
Эвристики могут работать иногда, но не всегда оптимально.
Приближенные алгоритмы могут находить решения, которые не сильно хуже оптимальных.

Примеры использования эвристик

1:11:35

Эвристики полезны для частных случаев задач, таких как деревья.
Приближенные алгоритмы могут быть достаточно быстрыми и надежными.
В логистике и других задачах часто используются эвристики для быстрого нахождения приемлемых решений.

Задача выполнимости

1:14:31

Задача выполнимости популярна в теории и практике.
Она используется для доказательства полноты других задач.
Программы для решения задачи выполнимости, такие как SAT-решатели, становятся все быстрее и эффективнее.

Применение SAT-решателей

1:16:31

SAT-решатели используются в искусственном интеллекте и других областях.
Они позволяют быстро решать задачи, такие как судоку.
Эти программы развиваются и улучшаются, что делает их популярными и полезными.

Будущее алгоритмов

1:20:25

Если кто-то докажет, что P=NP, это не приведет к катастрофе.
Алгоритм может быть бесполезен на практике или работать очень медленно.
Возможные опасности включают взлом криптосистем, но это зависит от навыков хакеров.

Позитивные аспекты быстрых алгоритмов

1:23:22

Быстрый алгоритм может привести к улучшению в различных областях.
Это может улучшить поиск доказательств в математике и других областях.
Важно рассматривать как положительные, так и отрицательные аспекты новых алгоритмов.

Доказательство теорем и P=NP

1:24:21

Математики доказывают теоремы, чтобы другие могли проверить их правильность.
Если P равно NP, появится способ формулировать теоремы и заставлять их доказывать с помощью алгоритмов.
Это может сделать математиков бесполезными, так как алгоритмы могут сами находить доказательства.

Формализация теорем

1:25:19

Теоремы придется записывать в формальную систему для алгоритмов.
Пример теоремы Ферма: простое утверждение, доказательство которого заняло 300 лет.
Алгоритмы могут либо доказать теорему, либо признать её недоказуемой.

Ускорение алгоритмов

1:26:17

Вопрос о том, как ускорить алгоритмы, остается открытым.
Ведущие предлагают слушателям делиться идеями в комментариях.
Пример эвристического алгоритма для ускорения запросов.

Важность констант в алгоритмах

1:27:15

В оптимизации алгоритмов часто забывают о константах.
Константы могут быть важны, особенно в практических применениях.
Пример: алгоритм с константой 1000 может быть лучше, чем с константой 100000.

Практическое значение констант

1:29:14

На практике скрытые константы обычно небольшие.
Алгоритмы с большими константами интересны только в теории.
Улучшение констант может потребовать знаний за пределами курса алгоритмов.

Заключение и благодарности

1:31:09

Ведущие благодарят за интересный вопрос и делятся воспоминаниями.
Рекомендация двух выпусков подкаста для дальнейшего изучения.
Призыв к слушателям делиться выпуском и поддерживать подкаст.