![Pavel Mavrin](/img/default-banner.jpg)
- Видео 278
- Просмотров 1 084 251
Pavel Mavrin
Россия
Добавлен 1 дек 2007
This channel mainly contains my lectures about algorithms and data structures.
Fun Stories and Practical Tips. Talk from EUC 2024
Fun Stories and Practical Tips.
Talk from 2024 ICPC European Championship.
In this talk, I recall some stories from my experiences in competitions and share tips that can help you perform better.
Talk from 2024 ICPC European Championship.
In this talk, I recall some stories from my experiences in competitions and share tips that can help you perform better.
Просмотров: 2 220
Видео
A&DS S04E14. Parallel Algorithms
Просмотров 9 тыс.2 года назад
Algorithms and data structures. Semester 4. Lecture 14 In the final lecture, we discussed parallel algorithms. ITMO University, 2022
АиСД S04E14. Параллельные алгоритмы.
Просмотров 4,3 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 4. Лекция 14 На последней лекции мы поговорили про параллельные вычисления. Разобрали основные модели и алгоритмы. Университет ИТМО, 2022 г.
АиСД S02E15. Сложность задач. Классы сложности.
Просмотров 2,6 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 2. Лекция 12. На последней лекции мы поговорили о том, какие задачи решаются за полиномиальное время, какие за неполиномиальное, и какие не решаются совсем. Также обсудили, как одни задачи сводятся к другим, и показали, что задача о рюкзаке является NP-полной Университет ИТМО, 2022 г.
A&DS S04E13. Approximation Algorithms
Просмотров 1,6 тыс.2 года назад
Algorithms and data structures. Semester 4. Lecture 13 In the thirteenth lecture, we discussed approximation algorithms, that is, algorithms that find not an exact solution, but some solution that approximates the optimal one with some accuracy. ITMO University, 2022
АиСД S04+. Primal-Dual. Взвешенное недвудольное паросочетание
Просмотров 8172 года назад
Алгоритмы и структуры данных. Семестр 4. Бонусная лекция На дополнительной лекции мы разобрали Primal-Dual алгоритм для нахождения недвудольного паросочетания минимального веса. Университет ИТМО, 2022 г.
АиСД S04E13. Приближенные алгоритмы
Просмотров 1,1 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 4. Лекция 13 На тринадцатой лекции мы поговорили о приближенных алгоритмах, то есть алгоритмах, которые находят не точное решение, но какое-то решение, которое с какой-то точностью приближает оптимальное. Университет ИТМО, 2022 г.
A&DS S04E12. Fast Fourier Transform
Просмотров 1,9 тыс.2 года назад
Algorithms and data structures. Semester 4. Lecture 12. In the twelfth lecture, we talked about how to multiply polynomials fast and why this is needed. We discussed the Karatsuba algorithm and the Fast Fourier Transform. ITMO University, 2022
АиСД S04E12. Быстрое преобразование Фурье
Просмотров 2,7 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 4. Лекция 12. На двенадцатой лекции мы поговорили о том, как быстро перемножать полиномы и зачем это нужно. Разобрали алгоритм Карацубы и быстрое преобразование Фурье. Университет ИТМО, 2022 г.
АиСД S02E11. Центроидная декомпозиция
Просмотров 2,1 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 2. Лекция 11. На одиннадцатой лекции мы поговорили о центроидной декомпозиции дерева. Университет ИТМО, 2022 г.
A&DS S04E11. Basic Cryptography Algorithms
Просмотров 1,3 тыс.2 года назад
Algorithms and data structures. Semester 4. Lecture 11. In the eleventh lecture, we talked about the basic algorithms of cryptography. We discussed RSA and El Gamal protocols, digital signatures. ITMO University, 2022
АиСД S04E11. Базовые алгоритмы криптографии
Просмотров 9672 года назад
Алгоритмы и структуры данных. Семестр 4. Лекция 11. На одиннадцатой лекции мы поговорили о базовых алгоритмах криптографии. Разобрали, как работают схемы RSA и Эль Гамаля, цифровая подпись, как работает шифрование в интернете и зачем нужны центры сертификации. Университет ИТМО, 2022 г.
АиСД S02E10. Heavy-Light декомпозиция, Link-Cut дерево
Просмотров 1,7 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 2. Лекция 10. На десятой лекции мы изучили как отвечать на запросы на дереве с помощью Heavy-Light декомпозиции Link-Cut дерева. Университет ИТМО, 2022 г.
A&DS S04E10. Number Theory Algorithms
Просмотров 3,1 тыс.2 года назад
Algorithms and data structures. Semester 4. Lecture 10. In this lecture we talked about basic number theory algorithms: primality testing, factorization, greatest common divisor, diophantine equations, and the chinese remainders theorem. ITMO University, 2022
АиСД S04E10. Базовые алгоритмы теории чисел
Просмотров 2,5 тыс.2 года назад
Алгоритмы и структуры данных. Семестр 4. Лекция 10. На десятой лекции мы поговорили о базовых алгоритмах теории чисел, проверке числа на простоту, факторизации чисел, нахождении наибольшего общего делителя, решении диофантовых уравнений и китайской теореме об остатках. Университет ИТМО, 2021 г.
АиСД S02E09. Двоичные подъемы. LCA. Алгоритм Фарах-Колтона и Бендера
Просмотров 1,8 тыс.2 года назад
АиСД S02E09. Двоичные подъемы. LCA. Алгоритм Фарах-Колтона и Бендера
АиСД S04E09. Линейное программирование
Просмотров 2 тыс.2 года назад
АиСД S04E09. Линейное программирование
АиСД S02E08. Scapegoat Tree, List Order Maintenance
Просмотров 1,3 тыс.2 года назад
АиСД S02E08. Scapegoat Tree, List Order Maintenance
АиСД S04E08. Алгоритмы Штор-Вагнера и Каргера-Штейна
Просмотров 1,2 тыс.2 года назад
АиСД S04E08. Алгоритмы Штор-Вагнера и Каргера-Штейна
АиСД S04E07. Поток минимальной стоимости
Просмотров 1,6 тыс.2 года назад
АиСД S04E07. Поток минимальной стоимости
АиСД S02E06. Декартово дерево, дерево по неявному ключу
Просмотров 3,8 тыс.2 года назад
АиСД S02E06. Декартово дерево, дерево по неявному ключу
A&DS S04E06. Assignment Problem. Hungarian Algorithm
Просмотров 1,3 тыс.2 года назад
A&DS S04E06. Assignment Problem. Hungarian Algorithm
АиСД S04E06. Задача о назначениях. Венгерский алгоритм
Просмотров 1,8 тыс.2 года назад
АиСД S04E06. Задача о назначениях. Венгерский алгоритм
АиСД S02E05. Дерево поиска. АВЛ-дерево
Просмотров 3,5 тыс.2 года назад
АиСД S02E05. Дерево поиска. АВЛ-дерево
A&DS S04E05. Hopcroft-Karp algorithm, Push-Relabel
Просмотров 1,3 тыс.2 года назад
A&DS S04E05. Hopcroft-Karp algorithm, Push-Relabel
АиСД S04E05. Потоки. Алгоритм Хопкрофта-Карпа, Push-Relabel
Просмотров 1,7 тыс.2 года назад
АиСД S04E05. Потоки. Алгоритм Хопкрофта-Карпа, Push-Relabel
В питоне почему-то нет -- ++,但是но можно использовать := array[a := a+1]
В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 1981 году. Сейчас существует методология программирования на этой основе - v-agent oriented programming (VAOP) - и множество примеров её реализации. Лучше начать знакомство с VAOP с этой статьи на Medium: "Bagels and Muffins of Programming or How Easy It Is to Convert a Bagel into a Black Hole" или на Хабре: "Бублики и Коржики Программирования".
Отличная лекция. Но я не понял yf 1:16:00 почему PQ = (P1x^n/2 + P2)(Q1x^n/2 + Q2). Что такое P1, P2, Q1, Q2
Делим каждый из полиномов на две части, например P(x)=1*x^3+2*x^2+3*x+4, делим его так: (1*x^3+2*x^2)+(3*x+4), теперь из левой части можно вынести x^2 за скобки: (1*x+2)*x^2+(3*x+4)
Спасибо за отличное видео. Как программист с 50-летним опытом, скажу, что уже около 40 лет мы утратили понимание алгоритмов в том смысле, о котором я пишу в своих статьях на Medium: "Bagels and Muffins of Programming or How Easy It Is to Convert a Bagel into a Black Hole" или на Хабре: "Бублики и Коржики Программирования". Алгоритмически мыслить и жить в алгоритмо-центричном мире программирования и писать программы-коржики - это удел одиночек. Сегодняшний мир программирования все больше фокусируется на кодо-центричном подходе, где алгоритмы не рассматриваются как отдельные сущности. Этот переход привел к значительным изменениям в подходах к разработке и сопровождению программного обеспечения. Когда-то алгоритмы были сердцем любой программы, обеспечивая четкую и понятную структуру для разработки. Они помогали нам строить логичные и эффективные решения. Однако с ростом популярности высокоуровневых языков программирования и фреймворков, акцент сместился на быстрое написание кода и внедрение новых функций, часто в ущерб структурированному алгоритмическому мышлению. Сегодня все чаще встречаются программы-бублики, где код существует отдельно от алгоритма, создавая внутренние несогласованности и сложности в поддержке. В таких условиях трудно добиться стабильности и надежности программного обеспечения. Возвращение к алгоритмо-центричному подходу и создание программ-коржиков, где алгоритм и код интегрированы, могут значительно улучшить качество программного обеспечения. Это не только упростит тестирование и поддержку, но и позволит создавать более гибкие и устойчивые системы. Я надеюсь, что больше разработчиков начнут осознавать важность алгоритмов и перейдут к более структурированному и осмысленному подходу к программированию. Только так мы сможем создать программное обеспечение, которое будет надежным, понятным и легко поддерживаемым.
please give link to your competitive programming course in English :(
ужасная подача материала. чел может и крут в соревнованиях, но как препод никакущий
What was the intended answer for problem 2.6 from the homework?
great job. Looking forward to hear more lectures from you.
на лекциях итмо говорят 'господи боже мой' чаще, чем в храме
Отлично!
какой-то идиот клацает по своему идиотскому компьютеру, так и хочется подщечину дать)
наш слоняра
херово объясняешь. нихера не понял, куда тараторишь
гораздо приятнее слушать лекцию, когда никто не выкрикивает и не перебивает
These lectures are worth their weight in gold.
High quality content!!
is that means that we can sort an array in o(n)?
no
какое же огромное вам хочу спасибо я сказать, что обратили внимания на числа при объяснении бинпоиска по ответу, это дало главный толчок к пониманию данного типа бинпоиска мне
Спасибо большое! Очень полезная лекция для того чтобы понять суффиксный массив.
крутяк
теперь очень хочется узнать, что за статья на 1 часу 15 минуте?
Predicate search....
Mera bhai mera dost... tu prepare kar sin(ya)/cos(ya) ka answer tujhe mil jayega
Понятно когда СНМ храним в виде дерева, мы каждым элементом подмножества ссылаемся на корень дерева, это быстро брать и поправлять если что. А когда нам надо смерджить два множества то есть дерева, это же будет долго потому что надо каждую ссылку в одном из деревьев менять, это считается ли долго и так ли как я понял объединять два дерева? Просто акцент на этом не сделан или я не заметил
а зачем нам while на 37:50 ??
годно
годнота
Как же я понимаю чувака на 44:40: "Всё плохо.."
годнота
Подскажите пожалуйста, когда мы хотим отсортировать массив при помощи кучи, но внутри одного массива, мы хотим преобразовать массив в кучу а потом пройти делая shift-down. Но разве цикл из sift-up делает из массива кучу?
годнота
awesome
I do not understand how is O( ✓n * log²(n) ) = O(n) I think it is greater than linear complexity. Example: If n=64, ✓n * log²(n) = 8 * 6² = 288 Am I missing something ? Please help
He's legend!
Есть курсач: Моделирование решения задачи о рюкзаке на языке C++ Arturchik777 - TG
Есть курсач: Моделирование решения задачи о рюкзаке на языке C++ Arturchik777 - TG
Есть курсач: Моделирование решения задачи о рюкзаке на языке C++ Arturchik777 - Moй TG
Looks like your solution of the bacteria problem is not a hammer, since it's very technic and requires a deep understanding of what is going on. Maybe even deeper than it was expected :D
You speak in English in the similar manner as in Russian. I like this! Do not disappear, please.
We subscribed on you together family!
sir Could you plz explain time complecity of recursion f(m,n) = f(m-1,n)+f(m,n-1)+O(1) of this type
THIS IS THE BEST COURSE EVER .THANKS SENPAI.
На 14:40 непонятно, что значит "добавить b". Разве его не в верхнюю строку надо добавить? Просто выглядит так, словно вы отрезаете b из второй строки, хотя говорите при этом, что добавляете.
Да, мы добавляем b к первой строчке, по продолжению, кстати, понятно, что именно это и происходит
Почему на 11:11 именно сравнивается A[i-1] и B[i-1]? Почему не "Если A[i]==B[i]" И почему тогда наше d[i][j]==d[i-1][j-1]? Вот эти два момента вообще непонятны, и, соответственно, непонятно всё, что идет дальше.
in 2024 this video is still very useful and well done. Congrats to the lecturer
почему не использовать __builtin_clz в 26:35 для поиска старшего бита? вместо штуки с прошлого раза
Ну это все теоретические структуры данных, понятно что на практике нужно по-другому все делать. А с точки зрения теории интересно обойтись минимальным множеством доступных операций
Отличный канал, спасибо! Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
кажется здесь нужен SIMD
1:08:00 топологическая сортировка
Hey pashka, Thanks for this wonderful tutorial. I had a query watching the video, hope you will answer: In partially persistent linked list, if we store a list of pointers at each node (based on version). Then the time complexity to add and remove would be O(1). Also the worst case time complexity of iteration will be Σlog(size(i)) for 1<=i<=n, where n is the number of nodes and size(i) is the size of ith node. We can observe Σsize(i) will be of order v (no of versions). The worst case doesn't seem like n*log(v) in this case. The worst case I could come up with was O(n + sqrt(v)*log(sqrt(v)) ) which is equivalent to O(n). Could you add your opinion here. Thanks