- 45
- 178 242
Denis Kirienko
Russia
Приєднався 17 тра 2007
ЛКШ-2024, параллель 6. Лекция 13: Матрицы, динамическое программирование. ДП по профилю.
Матрицы. Операции с матрицами. Умножение, возведение в степень, быстрое возведение в степень. Линейные рекуррентные последовательности, их вычисление при помощи возведения матрицы в степень. Использование матриц для решения задач динамического программирования.
Динамическое программирование по профилю и по изломанному профилю на примере задачи "Замощение доски домино".
Динамическое программирование по профилю и по изломанному профилю на примере задачи "Замощение доски домино".
Переглядів: 121
Відео
ЛКШ-2024, параллель 6. Лекция 12: Динамическое программирование. Читает Олег Кононов.
Переглядів 1134 місяці тому
Динамическое программирование на подотрезках, поддеревьях, подмножествах. Задача нахождения гамильтонова цикла. Задача коммивояжёра. Задача о количестве рюкзаков, необходимых для переноса данного множества предметов. Meet-in-the-middle. Задача о рюкзаке со стоимостями. Задача о наибольшей клике в графе.
ЛКШ-2024, параллель 6. Лекция 12: Динамическое программирование. Читает Владислав Бурмистров.
Переглядів 1024 місяці тому
Динамическое программирование на подотрезках, поддеревьях, подмножествах. Задача нахождения гамильтонова цикла. Задача коммивояжёра. Задача о количестве рюкзаков, необходимых для переноса данного множества предметов. Meet-in-the-middle. Задача о рюкзаке со стоимостями. Задача о наибольшей клике в графе.
ЛКШ-2024. Спецкурс "Устойчивые паросочетания".
Переглядів 754 місяці тому
Немного о паросочетаниях. Постановка "задачи о марьяже". Устойчивые паросочетания. Наличие различных устойчивых паросочетаний. Алгоритм Гэйла-Шепли. Свойства алгоритма. Упорядоченность устойчивых паросочетаний. "Задача о соседях", отсутствие устойчивого решения в общем случае. Рассуждения о применении алгоритма Гэйла-Шепли для зачисления выпускников школ в вузы в России.
ЛКШ-2024, параллель 6. Лекция 11: Алгоритмы на строках. Бор. Алгоритм Ахо-Корасик.
Переглядів 724 місяці тому
Бор. Построение бора. Некоторые применения бора. Алгоритм Ахо-Корасик поиска множества строк в строке.
ЛКШ-2024, параллель 6. Лекция 9: Геометрия: окружности, многоугольники. Читает Владислав Бурмистров.
Переглядів 624 місяці тому
Окружности. Пересечение прямой и окружности, пересечение окружностей, касательная к окружности из точки, общая касательная к двум окружностям. Многоугольники. Площадь многоугольника. Проверка принадлежности точки многоугольнику. Принадлежность точки выпуклому многоугольнику. Построение выпуклой оболочки (алгоритм Грэхема). Касательные к выпуклому многоугольнику, параллельные данной прямой и про...
ЛКШ-2024, параллель 6. Лекция 10: Алгоритмы на строках. z-функция, префикс-функция, алгоритм КМП.
Переглядів 734 місяці тому
z-функция. Определение, алгоритм вычисления за линейное время. Применения: поиск подстроки в строке, количество различных подстрок, поиск периода в подстроке. Подсчёт количества подстрок-палиндромов. Алгоритм Манакера. Префикс-функция. Определение, алгоритм вычисления за линейное время. Применения. Поиск подстроки в строке - алгоритм Кнута-Морриса-Пратта. Автомат КМП.
ЛКШ-2024, параллель 6. Лекция 9: Геометрия: окружности, многоугольники. Читает Николай Ведерников.
Переглядів 774 місяці тому
Окружности. Пересечение прямой и окружности, пересечение окружностей, касательная к окружности из точки, общая касательная к двум окружностям. Многоугольники. Площадь многоугольника. Проверка принадлежности точки многоугольнику. Принадлежность точки выпуклому многоугольнику. Построение выпуклой оболочки (алгоритм Грэхема). Касательные к выпуклому многоугольнику, параллельные данной прямой и про...
ЛКШ-2024, параллель 6. Лекция 8: Вычислительная геометрия на плоскости: точки, вектора, углы, прямые
Переглядів 1024 місяці тому
Декартова система координат. Точки, вектора. Полярные координаты, переход между декартовыми координатами и полярными. Функция atan2. Скалярное произведение. Векторное (псевдоскалярное, "косое") произведение векторов на плоскости. Их свойства, нахождение через координаты. Применение: принадлежность точки прямой, лучу, отрезку. Площадь треугольника, расстояние от точки до прямой, от точки до отре...
ЛКШ-2024, параллель 6. Лекция 7: Паросочетания.
Переглядів 894 місяці тому
Двудольные графы. Паросочетания. Максимальное и наибольшее паросочетание. Удлиняющий путь. Алгоритм Куна. Реализация и оптимизация алгоритма Куна. Теорема Холла (теорема о женихах и невестах). Минимальное вершинное покрытие. Теорема Кёнига. Построение минимального вершинного покрытия на основе наибольшего паросочетания. Максимальное независимое множество. Разбиение ориентированного ациклическог...
ЛКШ-2024, параллель 6. Лекция 6: Нахождение компонент сильной связности. Задача 2-SAT. Эйлеров цикл.
Переглядів 1,3 тис.4 місяці тому
Нахождение компонент сильной связности в ориентированном графе и построение конденсации графа. Алгоритм Косарайю (с двумя DFS). Алгоритм Тарьяна (с одним DFS). Задача 2-SAT, решение с использованием компонент сильной связности. Критерий отсутствия решения. Построение эйлерова цикла в графе.
ЛКШ-2024, параллель 6. Лекция 5: Свойства и применения DFS, поиск мостов и точек сочленения.
Переглядів 7234 місяці тому
Алгоритм обхода в глубину. Времена входа и времена выхода, их свойства. Классификация рёбер. Нахождение циклов в ориентированном и неориентированном графе. Мосты, нахождение мостов при помощи одного DFS. Компоненты рёберной двусвязности, алгоритм построения при помощи одного DFS. Точки сочленения, нахождение при помощи одного DFS. Компоненты вершинной двусвязности, нахождение при помощи одного ...
ЛКШ-2024, параллель 6. Лекция 4: LCA, LA. Читает Олег Кононов.
Переглядів 9064 місяці тому
Задача LCA (Lowest common ancestor, наименьший общий предок). Алгоритм с использованием двоичный подъёмов. Алгоритм с использованием эйлерова обхода. Алгоритм Тарьяна для offline-запросов. Задача LA (Level ancestor, предок на заданной высоте). Алгоритм с использованием двоичных подъёмов. Алгоритм с использованием "длинных путей". Алгоритм с использованием Ladders ("лестницы", удвоенные длинные ...
ЛКШ-2024, параллель 6. Лекция 3: Корневая декомпозиция (структуры данных, запросы, алгоритм Мо).
Переглядів 1874 місяці тому
Корневая декомпозиция. Структуры данных, с использованием корневой декомпозиции. Split rebuild. Корневая декомпозиция по запросам. "Легкие" и "тяжёлые" объекты. Алгоритм Мо.
ЛКШ-2024, параллель 6. Лекция 2: Декартово дерево.
Переглядів 2344 місяці тому
Двоичное дерево поиска, проблема балансировки. Идея декартова дерева. Построение и единственность декартова дерева. Операции split и merge. Добавление и удаление элементов при помощи split и merge. Поддержка размеров поддеревьев. Нахождение k-го элемента в поддереве. Разбиение поддерева на деревья заданного размера. Декартово дерево по неявному ключу, операции с ним. Групповые запросы (сумма, м...
ЛКШ-2024, параллель 6. Лекция 1: Структуры данных. sparse table, дерево Фенвика, дерево отрезков.
Переглядів 5025 місяців тому
ЛКШ-2024, параллель 6. Лекция 1: Структуры данных. sparse table, дерево Фенвика, дерево отрезков.
Что едят преподаватели в Сириусе? Дегустация десерта "Вагаси Моти" с фруктовой начинкой
Переглядів 1,3 тис.9 місяців тому
Что едят преподаватели в Сириусе? Дегустация десерта "Вагаси Моти" с фруктовой начинкой
Установка компиляторов и сред разработки в Windows для использования на олимпиадах
Переглядів 61911 місяців тому
Установка компиляторов и сред разработки в Windows для использования на олимпиадах
ЛКШ-2023-зима, параллель 5+. Лекция 7: Кодирование с исправлением ошибок, задачи с двойным запуском.
Переглядів 37411 місяців тому
ЛКШ-2023-зима, параллель 5 . Лекция 7: Кодирование с исправлением ошибок, задачи с двойным запуском.
ЛКШ-2023-зима, параллель 5+. Лекция 4: Алгоритм A*.
Переглядів 186Рік тому
ЛКШ-2023-зима, параллель 5 . Лекция 4: Алгоритм A*.
ЛКШ-2023-зима, параллель 5+. Лекция 1: Стереометрия.
Переглядів 197Рік тому
ЛКШ-2023-зима, параллель 5 . Лекция 1: Стереометрия.
ЛКШ-2023, параллель 5. Лекция 12: Алгоритмы на корневых деревьях (LCA, LA и другие задачи).
Переглядів 383Рік тому
ЛКШ-2023, параллель 5. Лекция 12: Алгоритмы на корневых деревьях (LCA, LA и другие задачи).
ЛКШ-2023, параллель 5. Лекция 11: Минимальное остовное дерево. Система непересекающихся множеств.
Переглядів 342Рік тому
ЛКШ-2023, параллель 5. Лекция 11: Минимальное остовное дерево. Система непересекающихся множеств.
ЛКШ-2023, параллель 5. Лекция 10: Вычислительная геометрия: окружности, многоугольники.
Переглядів 323Рік тому
ЛКШ-2023, параллель 5. Лекция 10: Вычислительная геометрия: окружности, многоугольники.
ЛКШ-2023, параллель 5. Лекция 9: Вычислительная геометрия: вектора, углы, прямые.
Переглядів 320Рік тому
ЛКШ-2023, параллель 5. Лекция 9: Вычислительная геометрия: вектора, углы, прямые.
ЛКШ-2023, параллель 5. Лекция 8: Алгоритмы на строках.
Переглядів 282Рік тому
ЛКШ-2023, параллель 5. Лекция 8: Алгоритмы на строках.
ЛКШ-2023, параллель 5. Лекция 7: Динамическое программирование, часть 2. Читает Александр Чистяков.
Переглядів 286Рік тому
ЛКШ-2023, параллель 5. Лекция 7: Динамическое программирование, часть 2. Читает Александр Чистяков.
ЛКШ-2023, параллель 5. Лекция 6: Динамическое программирование. Читает Хетаг Дзестелов.
Переглядів 393Рік тому
ЛКШ-2023, параллель 5. Лекция 6: Динамическое программирование. Читает Хетаг Дзестелов.
ЛКШ-2023, параллель 5. Лекция 5: Декартово дерево по неявному ключу. Сканирующая прямая.
Переглядів 350Рік тому
ЛКШ-2023, параллель 5. Лекция 5: Декартово дерево по неявному ключу. Сканирующая прямая.
ЛКШ-2023, параллель 5. Лекция 4: Декартово дерево.
Переглядів 415Рік тому
ЛКШ-2023, параллель 5. Лекция 4: Декартово дерево.
Он как-будто стыбзил из музея первый прототип микрофона конца XIX в.
Настолько понятно тема рекурсий подана!
Спасибо за туториал, помогло на МКОШП установить VS Code!!!!!
очень познавательно - спасибо
Cупер подача информации ...спасибо
A gde eto primenimo? spasibo.
Очень хорошая подача материала, Денис Павлович
У вас название лекции неверное: в лекции говорится про двудольные графы, а в названии вычислительная геометрия
Исправил, спасибо!
Очень крутая тема! 69 подборов константы из 10!!!!
а бывают лицемерные массивы ?
Разбудите когда Bank of Armenika ломать будем
👍
Выкладывайте больше видео в таком формате! ❤🎉
Очень интересная лекция!! Всем советую!! Спасибо автору!!
Здраствуйти можно участвоват лагере ребят из Узбе кистана
блестяще
Спасибо за занятие
Огромное спасибо
на впемени 1.05 про факториалы. С решением что-то не то. Ответ не 120 должен получиться. Никто даже не заметил )
Зачем добавлять минус 1, если: a = int(input()) d = int(input()) print((a + d - 1) // d) print(((a + d) // d)) 112876 532 213 213 15 4 4 4 2098 300 7 7 про отрезки или вычисление этажа на котором расположена квартира, или купэ с номером сиденья... Зачем добавлять -1 к переменной b, если разницы не видно????
Привет от калихины
Великолепно)
спасибо большое!
Тот самый туториал, которого мы так долго ждали🥰
elem=str(elem) elem=" "*(2-len(elem)) Здесь мне кажется есть ошибка .Я прав?(22 мин 50 сек лекция) Забыл добавить elem=" "*(2-len(elem))+elem Лекция отличная спасибо
Доброго времени суток, подскажите пожалуйста смысл выполнения вышеупомянутых циклов на php такой-же? Разница только в синтаксисе языка?
Очень круто, спасибо большое!!!! Вы классный !
В задачи дни, часы, минуты, секунды. вроде ошибка. Чтобы вычислить полное количество часов из секунд без дней. нужно не h = t%(60*60)... А h = t//(60*60). или я ошибаюсь?
Тимофей Федорович прекрасный преподаватель. Преподаватель от Бога. Я не учился в МФТИ, но сложные вещи декомпозировать так искусно, большая благодарность за интереснейшие лекции, которые помогают в учебе.
"вы 8-й класс, вам это еще рано".... ))
1:14:36 Задача со строками и текстом
8:15 Частное 20//3=6 и Остаток 20%3=2 12:53 Задача 1 (рубли и копейки) 18:19 Задача 2 (часы и минуты) Конец К-го урока 21:55 Комментарии в Питоне через # 25:06 Задача 3 (Дни, часы, минуты, секунды) 27:58 Операторы присваивания 31:22 Задача 4 (Деление с округлением вверх) 43:54 Задача 5 "МКАД" (на остаток) 52:31 Задача 6 (Отделение сотен, десяток, единиц) 54:52 Задача 7 (Сумма цифр трехзначного числа) 58:07 Задача 8 (Обмен переменных местами) 59:59 Понятие "Кортежа" 1:01:15 Задача 9 (Обмен переменных 2) 1:03:39 Задача 10 (Часы) 1:14:25 Задача "МКАД" (объяснение, отрицательные числа)
Привет Андрею Бойко!
На фразе "вы 8 класс" захотелось все бросить, пришла мысль, что я безнадежно отстала 😂
Уже скидываю сыну видео.
Это урок в интернате для даунов?
Кочнев топ, спасибо за -2 часа жизни🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉😊😊😊😊😊😊😊❤❤❤❤
Прекрасный урок! В первый раз пытался осознать def на основе программы обучалки Sololearn и ничего не понял. Но этот урок открыл глаза, все стало гораздо яснее и понятнее!
не допёр как бинарные числа получать, в итоге выходит так: s = 0 x = int(input()) while x > 0: binDigit = x % 2 s += binDigit # if binDigit == 1: \s+=1 print(s) x //= 2 print(s) Ввод: 433 Вывод: 1 1 1 1 2 3 3 4 5
Олень! Кучу времени рассказывает не нужный материал.
спасибо
Единственное, что я не понял - это почему тут так мало лайков. Спасибо автор, самое доходчивое объяснение с самыми понятными аналогиями.
🤙🤙🤙🤙
Нереально крутая подача информации ... лучше всяких «современных ютуберов» Спасибо большое 😊
А что за сайт с задачами?
я в детстве проходил Киранлдию 2, там в конце задание было: Ханойская башня. Тоже, только башня перевернута))) Долго думал, но разобрался))) 11 лет))
В тот момент, когда я понял, что это рассказывают восьмиклассникам, я понял свою никчемность!
Спасибо за лекцию! Смотрю в 2022 г.. ПОскажите, для Питона 3.10-3.11 работает эта конструкция: for row in a: for elem in row: - ?
Первый идет по строкам, второй по элементам строки.
Спасибо вам за ваш труд 👍🏻
👍🏻👍🏻👍🏻