Часть 1. 1:04 - Содержание лекции 2:07 - Исполнитель и введение понятия алгоритма 5:20 - Описание исполнителя Часть 2. 7:42 - Сложность алгоритма. О - и Θ - нотации 10:53 - Главный параметр сложности 12:02 - Нотация сложности. Символ Θ 13:51 - Нотация сложности. Символ О 15:17 - Приближенное вычисление сложности 19:20 - Асимптотика основных зависимостей Часть 3. Практические примеры 21:44 - Зависимость времени исполнения от исходных данных. Пример 24:28 - Второй пример 25:48 - Задача на доске, решите их и вашу фотографию повесят рядом с Перельманом 31:13 - Неполиномиальные задачи 32:06 - Задача о рюкзаке 33:38 - Одно из решений задачи о рюкзаке 34:11 - Свойства данного алгоритма 35:20 - Время выполнения алгоритма решения в секундах 36:45 - Пример с графами 38:53 - Второй пример 40:13 - NP задачи Часть 4. 41:25 - Исполнитель алгоритма. Описание языка С++ 45:26 - Цикл for 46:43 - Представление типов Часть 5. 51:41 - Инварианты. Индуктивные функции 56:45 - Инварианты и предикаты алгоритма 1:00:01 - Абстракции. Интерфейс абстракции 1:02:04 - Пример: абстракция массива 1:06:10 - Абстракция стек 1:10:35 - Абстракция множество Часть 6. 1:14:10 - Рекурсия. Принцип разделяй и властвуй 1:15:29 - Числа Фибоначчи. Рекуррентная форма 1:16:27 - Рекуррентность и рекурсия 1:18:32 - Дерево вызовов функции 1:20:10 - Оценка времени вычисления алгоритма 1:22:25 - Оценка требуемой для исполнения памяти 1:24:40 - Определение порядка числа вызовов 1:26:36 - Как ускорить? 1:32:37 - Дерево вызовов модифицированной функции 1:34:17 - Проблема с представлением данных 1:40:17 - Как работать с длинными числами 1:41:39 - Как умножать длинные числа? Школьный алгоритм 1:43:25 - Алгоритм быстрого умножения Анатолия Карацубы Часть 7 1:49:54 - Основная теорема о рекурсии 1:50:16 - Оценка асимптотического времени алгоритма 1:53:18 - Сама теорема о рекурсии 1:56:01 - Оценка сложности алгоритма Карацубы 2:00:22 - Еще о сложности. Умножаем матрицы 2:03:11 - Возведение матрицы в степень 2:08:56 - Быстрое вычисление степеней 2:09:18 - Рекурсивная функция быстрого умножения 2:12:16 - Оценка сложности быстрого умножения

тот момент когда все вокруг считают тебя недостижимо умным, а ты, после просмотра видосика на Ютубе осознаешь, что все твои знания на уровне дворовой кошки.. __(:з」∠)__

как же доступно он объясняет ☺ хороший препод, ждём некст лекции

Какой замечательный препод!

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

спасибо. все доступно. лекция и препод супер

Очень интересно и все понятно, спасибо!

Спасибо огромное за лекцию!

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

Благодарю

Спасибо

Люблю такие лекции, которые не понять очень сложно). Супер! А то есть такие, которые начнут сразу формулы писать

Бум смотреть )

Препод хороший, но как он называет имена и названия!!! По его произношению просто невозможно найти источник. Хоть бы в презентацию вставлял. Или в описание добавили бы с временными метками.

Эта задача с мешком) мы такие в экселе решали через поиск решений)

Здравствуйте. На слайде 2:08:59 , наверное, опечатка во втором выражении. Там написано x^18 = (x^9)^2 = ((x^8 * x)^2)^2 = ........... А должно быть x^18 = (x^9)^2 = (x^8 * x)^2 = ........... т.е. одно лишнее возведение в степень двойки.

Есть там у кого алгоритм решения задачи с мешками?)очь нужно)

удаление массива: delete c; в плюсиках некорректно. Очень легко убедиться в этом, создав класс со счетчиком созданных элементов. Если потом склепать массив через Class *c = new Class[n] удалить: delete c; а потом посмотреть, сколько выжило экземпляров класса, то увидим, что помер всего один (н-1 выжили)

Спасибо! Интересная лекция! PS. Только вот один момент, краткость кода - это хорошо, скорость выполнения - тоже хорошо, но вопрос читаемости кода, за пример с множественными присвоениями в одном выражении могут и побить на работе...

Отличная лекция, спасибо! А где домашние задания? честно говоря стал изучать алгоритмы по corsera, но ваши лекции гораздо понятнее, эх почему я не пошел на ВМК!

там в формуле ошибка на 22:14. sum(1 до N) = N * (N +1) / 2. ПЛЮС там нужен. Плюс, а не минус.

32:45 объясните плиз, как там получается 2 в степени N? Матан давно уже был, я подзабыл(

Подскажите, откуда получилось (1+1)^N на 32:47. Вот 2^N - понимаю, 2 варианта (0 и 1), а (1+1)^N - не пойму.

на микрофоне носок забыли

на 18 минуте сдаюсь

задача комивояжера решается и не с помощью не очень сложного алгоритма

про машину всем известно, а кто такой Мышонок Тьюринга ?

35:19 в экспоненте

1:39:26: -O3 или -Ofast вам в помощь для ускорения)))

Когда Ходорковский успел стать специалистом по алгоритмам

Для чего эти лекции делаются?

на ~51:xx не верная инфа - товарищ сильный алгоритмист - это понятно ... Но вот на асме пишет вряд ли. и так пояснение: есть на Intel/Cortex такая команда как CMP, которая передает/преобразует не измененные биты регистра флагов состояния в необходимые. И опять же все просто: он написал в первом примере сравнение и исполнение одного из действий (двух действий) и во втором приятие первого и подправка второго - но вот в чем тут закавыка - все очень сильно зависит от а) архитектуры процессора (RISC - Cortex-A15/53 или CISC - Intel i3-i7) и б) зависит от набора переданных флагов компилятору (какой компиялятор и в каком режиме была скомпилированна программа - Релиз(-O3 -ffast-math и т.п.)/Дебаг). Итак почему я не согласен: 00) Смена флага состояния 01) джамп на нужное место в локальном участке памяти (для реализации подИфного условия - одного из) 10) джамп на далее (под далее следует понимать, как следующую итерацию в цикле, так и продолжение исполнения - Т.Е. ДЖАМП ПО ЛЮБОМУ) Вывод - вы либо прропускаете джам и выполняете операцию (если условие возвращает состояние true(1)) и потом прыгаете на исполнение программы далее; или прыгаете и исполняете операции (если условие возвращает состояние false(0)) и просто продолжаете выполнение (не прыгаете) программы далее. Т.Е. утверждение не верно - но если вы пишете и тестите производительность программы в дебаге то тогда ... ну ... шош я могу сказать ... успехов

чет какая-то древняя лекция, а ниче, что задачю о рюкзаке можно через Meet-in-the-middle решить, где O(2^(N/2) * N), что в разы быстрее получиться или методом динамического программирования, где при небольших размерах сумки он летать будет

Для чего эти лекции снимают и вакладывают?

много лишних слов ни о чем. здравствуйте, тема, определения, понятия, терема и по ходу неформальное объяснение (на пальцах)... а тут говорит, говорит, а еще ничего не сказал - надо же понимать, что это не детский сад целевая аудитория

косплей на щелкунчика

(1:39:04) какие нафиг "в 19/30/20ть раз" вы каким компилятором пользуетесь ... боже зачем народ пугать ... в современном процессоре (пусть будет Core i3-i7) есть векторные регистры ХММ0/УММ0-ХММ15/УММ15 которые шириной (для интела переменная: ХММ-128 bit / УММ - 256 bit / ZMM - 512 bit все сильно зависит от стоимости) в которые с лихвой влазит ваши 64х-битные типы и есть спец команды которые перемалывают 64 bit*ные не напрягаясь особо за 3-5ть тактов ... о Боги ... ох уж эти алгоритмисты - хотя лекции норм но не нада народ пугать

ни хрена не понятно.

Спасибо огромное за лекцию!