Видео

Огромная благодарность Андрею! Предлагаю книгу "Графомания" (Деревенец О.В.). Алгоритмы на графах реализованы на языке Delphi (Object Pascal) Все исходники и контрольные примеры в наличии. Скачивается бесплатно. Содержание: Знакомство с объектами, отношениями и множествами Представление объектов в языке Delphi Представление множеств, операции с множествами Понятие о сложности (трудоёмкости) алгоритмов Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Представление отношений графами Программная реализация графов, ввод и вывод графов Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (цикл); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.

спасибо!

Как всегда топ лекция!! Мой любимый ютубер!!! <3

нейтральный элемент относительно Умножения... возможно послышалось.... Тем неменее... Очень достойный курас, таких удачных компоновок материала и достойного изложения мало. Нет посттравматических истерик, неопрятной одежды самолюбования от кокнутых от словоблудья. Чистая и ясная речь. Конечно весь доказательный объём впихнуть в один семестр невозможно, но сюда минобраз ещё не добрался и тут полноценно 4 семестра. Это просто мастхэв!!!

формулировка задач ужасно кривая, ощущение что русский язык которым пользуюсь я и авторы задач - разные

Житель из майнкрафта объясняет грамматику

Максимально неинтересная и непонятная лекция 👍

По теме графов рекомендую свободно распространяемую электронную книгу «Графомания» (Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.

Потрепало илона маска..

И так, начнём))😂

Дзякуй

Спасибо за лекцию 😃

Очень не аккуратно называть векторным произведением длину векторного произведения. Грубая ошибка первокурсника.

Отличный разбор задачи!

Отличная задача

Если кому-нибудь несложно, подскажите, в чём ошибка в таком простом решении за O(N): Циклически сдвинем массив расстояний между соседними платформами так, чтобы максимальным было расстояние между n-й платформой и 1-й (для упрощения дальнейших рассуждений). Т.е. максимальное max(d(i)) = d(n) Если робот стартует свой путь с n-й платформы, то его начальная ловкость должна быть ровно a(n) = d(n). Дальше итеративно определяем стартовую ловкость для всех платформ: a(i) = max(a(i+1) - 1, d(i)) для всех i от n-1 до 1 включительно. Выбираем наименьшее a(i) и соответствующую платформу.

Спасибо! Я смотрел ваши лекции, когда увлекался олимпиадным программированием в школе, а теперь вы помогаете мне сдать экзамены в университете.

Очень коротко и понятно!! Спасибо большое!

Интересно, а учитывает ли теория расписаний празничные дни. К примеру, если есть всего 1 работник, у него N заказов, заданы оценки заказов и дедлайны. нужно минимизировать число просроченных заказов с учетом праздников и выходных дней. Без праздников и выходных был бы алгоритм Мура, а с ними - не знаю...

Где можно найти продолжение?

Вот что нужно для учебы)

Первое решение Е только на 64 балла?

А эти задачи есть на informatics или codeforces?

Спасибо большое за лекцию 🙏 Было бы очень здорово показать на практике, как добавлять в проект систему сборки Maven или Gradle

Вот это я понимаю новый клип фейса, качает!

На мой взгляд данное условие (dp[n][k][t-1]) не требуется, так как число должно быть составлено строго из t чисел. Тогда, зачем пытаться составить из t-1 чисел?

Добрый день, можете показать полное решение последней задачи?

💚

обожаю этого ютубера, жду сходку в среду

спасибо за предугадывание моих вопросов)

Наконец то понятное объяснение поиск г. цикла. Лектор сам понимает что рассказывает.

я из лкш

Разве не 2n+1(14:46)? т.к. необходимо сохранить ещë и указатель на верхний узел.

прикольно. я думал что можно просто в середину вставить, что получить максимальную длину. ez +9

Очень интересно,НО ,мне кажется,что чересчур много синтаксиса Теории Множеств на первом занятии,поэтому сложно понять материал. К примеру,смысл функции был объяснен через синтаксис ,поэтому сложно было вникнуть в материал. Но это скорее мой косяк,я не знаю теорию множеств на первом занятии,но думаю ,такая проблема не только у меня. А так очень интересно и необычно,здорово ,что дискретка рушит просто всё банальное представление о математике и дает возможность посмотреть на предмет по другому.

Добрый день, у меня один вопрос: почему в функции Accept для НКА мы в конце для получения результата итерируемся по всему массиву состояний, а не проверяем лишь те состояния, которые являются терминальными?

автомат ищущий подстроку в строке на c# сначала ввод строки, потом подстроки ест любые буквы алфавита int[] suf; Dictionary<(int , char) , int> go; string p; int n , j = 0; int get_go(int j , char c) { if (go.ContainsKey((j, c))) return go[(j, c)]; int temp = get_suf(j , c); if (j < n && c == p[j]) go[(j, c)] = j + 1; else if (j > 0) go[(j, c)] = go[(temp, c)]; else go[(j, c)] = 0; return go[(j, c)]; } int get_suf(int i , char c) { if (i == 0 || i == 1) suf[i] = 0; else suf[i] = get_go(suf[i - 1], c); return suf[i]; } string s = Console.ReadLine(); p = Console.ReadLine(); n = p.Length; go = new Dictionary<(int, char), int>(); suf = new int[n + 1]; for (int i = 0; i < n; i++) suf[i] = -1; int answer = 0; for (int i = 0; i < s.Length; i++) { j = get_go(j, s[i]); if (j == p.Length) answer++; } Console.WriteLine(answer);

ПАДИИ мощь!!!

а можно ли так, чтобы определялось больше 2k ошибок за счет того, что исправить удастся меньше k. В пределе - исправлять 0 ошибок - но зато больше определять

Можно ли где-то увидеть продолжение этого курса?

Спасибо большое за видео, очень помогли!

22:00 чтобы было очевиднее, можно было сказать, что суммарное число 'не' не превышает число листьев. Потому что потенциальное удвоение и увеличение дерева может немного сбить мысль о том, что это полином

Спасибо за лекцию, пересмотрел 15 раз :) Алгоритмом Томпсона обычно называется алгоритм построения эпсилон-НКА по регулярному выражению (en.wikipedia.org/wiki/Thompson's_construction). Собственно, он и используется в док-ве теоремы Клини. Впрочем, судя по статье Томпсона 1968 года, складывается ощущение, что он эту конструкцию не представлял таким красивым образом, и это уже Хопкрофт и Ульман докрутили в своей книге 1979 (рекомендую всем первое издание!). В свою очередь алгоритм построения ДКА по НКА называется просто "конструкция подмножеств Рабина-Скотта" (en.wikipedia.org/wiki/Powerset_construction). По-моему, в их статье 1959 года не прослеживается "ленивая" версия этого алгоритма. Так что вероятно, что именно ленивый алгоритм предложил кто-то другой, это затерялось во времени, и теперь подход называется просто "powerset construction".

Спасибо за лекцию!

Хороший мужик

1:02:54 мне кажется должно быть сторогае равно k>(n-p-1)! так как мы может пропустить и саму к - ю перестановку, нет ?

Вышлите пожалуйста сами задачи которые были на Олимпиаде(условия)

Здравствуйте, спасибо за лекции. Можно узнать год выпуска и автора задачника/учебника для домашних заданий студентам?

Жесть

Спасибо!