Denis Kirienko
Denis Kirienko
  • 45
  • 178 242
ЛКШ-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: Декартово дерево.

КОМЕНТАРІ

  • @Nikita-bd1oc
    @Nikita-bd1oc Місяць тому

    Он как-будто стыбзил из музея первый прототип микрофона конца XIX в.

  • @user-qs4js9tf7c
    @user-qs4js9tf7c Місяць тому

    Настолько понятно тема рекурсий подана!

  • @ДикийОгурчик-ъ2д
    @ДикийОгурчик-ъ2д 2 місяці тому

    Спасибо за туториал, помогло на МКОШП установить VS Code!!!!!

  • @dimtka2492
    @dimtka2492 2 місяці тому

    очень познавательно - спасибо

  • @oxac999
    @oxac999 2 місяці тому

    Cупер подача информации ...спасибо

  • @dorjarslan
    @dorjarslan 4 місяці тому

    A gde eto primenimo? spasibo.

  • @АлександрК-о5я
    @АлександрК-о5я 4 місяці тому

    Очень хорошая подача материала, Денис Павлович

  • @Lexonixeo
    @Lexonixeo 4 місяці тому

    У вас название лекции неверное: в лекции говорится про двудольные графы, а в названии вычислительная геометрия

    • @dkirienko
      @dkirienko 4 місяці тому

      Исправил, спасибо!

  • @mrKaf-zs4gy
    @mrKaf-zs4gy 4 місяці тому

    Очень крутая тема! 69 подборов константы из 10!!!!

  • @xmetris
    @xmetris 5 місяців тому

    а бывают лицемерные массивы ?

  • @alfasteel9437
    @alfasteel9437 5 місяців тому

    Разбудите когда Bank of Armenika ломать будем

  • @systy3844
    @systy3844 5 місяців тому

    👍

  • @ЛизаДроздова-б9э
    @ЛизаДроздова-б9э 5 місяців тому

    Выкладывайте больше видео в таком формате! ❤🎉

  • @wisik1479
    @wisik1479 5 місяців тому

    Очень интересная лекция!! Всем советую!! Спасибо автору!!

  • @SergiAguer
    @SergiAguer 5 місяців тому

    Здраствуйти можно участвоват лагере ребят из Узбе кистана

  • @c-8715
    @c-8715 5 місяців тому

    блестяще

  • @Гузель-к8р
    @Гузель-к8р 6 місяців тому

    Спасибо за занятие

  • @Гузель-к8р
    @Гузель-к8р 6 місяців тому

    Огромное спасибо

  • @ЕгорХрамышев-й2ц
    @ЕгорХрамышев-й2ц 7 місяців тому

    на впемени 1.05 про факториалы. С решением что-то не то. Ответ не 120 должен получиться. Никто даже не заметил )

  • @ВладимирКоркунов-о3л
    @ВладимирКоркунов-о3л 8 місяців тому

    Зачем добавлять минус 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, если разницы не видно????

  • @Хлебушек-ч2д
    @Хлебушек-ч2д 8 місяців тому

    Привет от калихины

  • @mr_ell7151
    @mr_ell7151 8 місяців тому

    Великолепно)

  • @soraln
    @soraln 9 місяців тому

    спасибо большое!

  • @BobZinin
    @BobZinin 11 місяців тому

    Тот самый туториал, которого мы так долго ждали🥰

  • @nasserhujyrah8834
    @nasserhujyrah8834 Рік тому

    elem=str(elem) elem=" "*(2-len(elem)) Здесь мне кажется есть ошибка .Я прав?(22 мин 50 сек лекция) Забыл добавить elem=" "*(2-len(elem))+elem Лекция отличная спасибо

  • @mrpaukov9533
    @mrpaukov9533 Рік тому

    Доброго времени суток, подскажите пожалуйста смысл выполнения вышеупомянутых циклов на php такой-же? Разница только в синтаксисе языка?

  • @SvetlanaGarcia
    @SvetlanaGarcia Рік тому

    Очень круто, спасибо большое!!!! Вы классный !

  • @vladmix77
    @vladmix77 Рік тому

    В задачи дни, часы, минуты, секунды. вроде ошибка. Чтобы вычислить полное количество часов из секунд без дней. нужно не h = t%(60*60)... А h = t//(60*60). или я ошибаюсь?

  • @structureelement
    @structureelement Рік тому

    Тимофей Федорович прекрасный преподаватель. Преподаватель от Бога. Я не учился в МФТИ, но сложные вещи декомпозировать так искусно, большая благодарность за интереснейшие лекции, которые помогают в учебе.

  • @MrMargincall
    @MrMargincall Рік тому

    "вы 8-й класс, вам это еще рано".... ))

  • @musecollaboration
    @musecollaboration Рік тому

    1:14:36 Задача со строками и текстом

  • @musecollaboration
    @musecollaboration Рік тому

    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 Задача "МКАД" (объяснение, отрицательные числа)

  • @ilyapreduniversariy
    @ilyapreduniversariy Рік тому

    Привет Андрею Бойко!

  • @ЕленаБей-х3г
    @ЕленаБей-х3г Рік тому

    На фразе "вы 8 класс" захотелось все бросить, пришла мысль, что я безнадежно отстала 😂

  • @ulna122
    @ulna122 Рік тому

    Уже скидываю сыну видео.

  • @andynaz7044
    @andynaz7044 Рік тому

    Это урок в интернате для даунов?

  • @danielwildon8601
    @danielwildon8601 Рік тому

    Кочнев топ, спасибо за -2 часа жизни🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉😊😊😊😊😊😊😊❤❤❤❤

  • @romang.7015
    @romang.7015 Рік тому

    Прекрасный урок! В первый раз пытался осознать def на основе программы обучалки Sololearn и ничего не понял. Но этот урок открыл глаза, все стало гораздо яснее и понятнее!

  • @DenisrcekgDenisrcekg
    @DenisrcekgDenisrcekg Рік тому

    не допёр как бинарные числа получать, в итоге выходит так: 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и

    Олень! Кучу времени рассказывает не нужный материал.

  • @ЗНАКОМЫЙСВАРЩИК

    спасибо

  • @John-ok4vi
    @John-ok4vi Рік тому

    Единственное, что я не понял - это почему тут так мало лайков. Спасибо автор, самое доходчивое объяснение с самыми понятными аналогиями.

  • @alex_unknown55
    @alex_unknown55 2 роки тому

    🤙🤙🤙🤙

  • @alex_unknown55
    @alex_unknown55 2 роки тому

    Нереально крутая подача информации ... лучше всяких «современных ютуберов» Спасибо большое 😊

  • @ДядяСлава-в5ю
    @ДядяСлава-в5ю 2 роки тому

    А что за сайт с задачами?

  • @СтасВолодин-ъ5ч
    @СтасВолодин-ъ5ч 2 роки тому

    я в детстве проходил Киранлдию 2, там в конце задание было: Ханойская башня. Тоже, только башня перевернута))) Долго думал, но разобрался))) 11 лет))

  • @barlisey
    @barlisey 2 роки тому

    В тот момент, когда я понял, что это рассказывают восьмиклассникам, я понял свою никчемность!

  • @Fravije
    @Fravije 2 роки тому

    Спасибо за лекцию! Смотрю в 2022 г.. ПОскажите, для Питона 3.10-3.11 работает эта конструкция: for row in a: for elem in row: - ?

    • @user-qs4js9tf7c
      @user-qs4js9tf7c 11 днів тому

      Первый идет по строкам, второй по элементам строки.

  • @azizaakh5443
    @azizaakh5443 2 роки тому

    Спасибо вам за ваш труд 👍🏻

  • @azizaakh5443
    @azizaakh5443 2 роки тому

    👍🏻👍🏻👍🏻