Часть 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 = ........... т.е. одно лишнее возведение в степень двойки.
Препод хороший, но как он называет имена и названия!!! По его произношению просто невозможно найти источник. Хоть бы в презентацию вставлял. Или в описание добавили бы с временными метками.
Спасибо! Интересная лекция! PS. Только вот один момент, краткость кода - это хорошо, скорость выполнения - тоже хорошо, но вопрос читаемости кода, за пример с множественными присвоениями в одном выражении могут и побить на работе...
Если рассуждать логически, то всё понятно и без сложных мат. преобразований: представь, что у тебя есть двоичное число разрядностью N, где N - количество предметов. Каждый предмет может либо присутствовать в комбинации (1), либо нет (0), т.е. для каждого предмета существует 2 состояния. Пусть, например, 0 разряд - телевизор, 1 разряд - кофемолка, 2 разряд - кошелёк, тогда мы можем составить следующие комбинации: Если бы у нас был только 1 предмет: - 0 (т.е. не берём ничего); - 1 (берём телевизор). Если бы было 2 предмета: - 0 0 (ничего); - 0 1 (берём телевизор); - 1 0 (берём кофемолку); - 1 1 (берём всё). Для 3-х предметов: - 0 0 0 (ничего); - 0 0 1 (только телевизор); - 0 1 0 (только кофемолка); - 0 1 1 (кофемолка и телевизор); - 1 0 0 (только кошелёк); - 1 0 1 (кошелёк и телевизор); - 1 1 0 (кошелёк и кофемолка); - 1 1 1 (берём всё). Очевидно, что для каждого нового предмета в группе кол-во возможных комбинаций удваивается, т.к. существующие комбинации умножаются на 2 возможных состояния нового предмета. Т.е. общее кол-во комбинаций = 2ⁿ. p.s.: ролик не смотрел, только пробежался по комментариям, поэтому не знаю, что и как объяснил преподаватель. Но это объяснение кажется настолько интуитивно понятным, что проблем быть не должно.
удаление массива: delete c; в плюсиках некорректно. Очень легко убедиться в этом, создав класс со счетчиком созданных элементов. Если потом склепать массив через Class *c = new Class[n] удалить: delete c; а потом посмотреть, сколько выжило экземпляров класса, то увидим, что помер всего один (н-1 выжили)
Отличная лекция, спасибо! А где домашние задания? честно говоря стал изучать алгоритмы по corsera, но ваши лекции гораздо понятнее, эх почему я не пошел на ВМК!
@@Das.Kleine.Krokodil для таких -нехороших- персонажей, без надобности использующих по несколько отрицаний в одном предложении, в аду должна быть предусмотрена специальная комната, наподобие той, в которую попал один из героев фильма "Евротур". Вот только слова на бумажке должны быть сложнее, чем пресловутое _"Flugegeheimen"..._
+MrRadiostep кому-то проще посмотреть такую лекцию, чтобы приобрести начальное представление об анализе алгоритмов и самих алгоритмах, чем читать книги.
чет какая-то древняя лекция, а ниче, что задачю о рюкзаке можно через 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ть тактов ... о Боги ... ох уж эти алгоритмисты - хотя лекции норм но не нада народ пугать
andru shevchenko xmm регистры предназначены для операций над числами с плавающей точкой, здесь же идет речь о целочисленной арифметике. чуть позже лектор как раз это и говорит
не верно в корне ... ХММ/УММ/ZMM это векторные регистры (ru.wikipedia.org/wiki/SIMD - тут про это пишут) с ними (c векторными регистрами) можно выполнять как потоковые операции целочисленные так и с плавающей точкой
andru shevchenko, современные процессоры - это частный случай. Есть тонна микроконтроллеров, которые не обладают такими свойствами, а им, к примеру, нужно много операций совершать с unix time. Или работать с числами, во много раз превосходящими длину процессорного слова. Так что это вышесказанное замечание мимо кассы.
на ~51:xx не верная инфа - товарищ сильный алгоритмист - это понятно ... Но вот на асме пишет вряд ли. и так пояснение: есть на Intel/Cortex такая команда как CMP, которая передает/преобразует не измененные биты регистра флагов состояния в необходимые. И опять же все просто: он написал в первом примере сравнение и исполнение одного из действий (двух действий) и во втором приятие первого и подправка второго - но вот в чем тут закавыка - все очень сильно зависит от а) архитектуры процессора (RISC - Cortex-A15/53 или CISC - Intel i3-i7) и б) зависит от набора переданных флагов компилятору (какой компиялятор и в каком режиме была скомпилированна программа - Релиз(-O3 -ffast-math и т.п.)/Дебаг). Итак почему я не согласен: 00) Смена флага состояния 01) джамп на нужное место в локальном участке памяти (для реализации подИфного условия - одного из) 10) джамп на далее (под далее следует понимать, как следующую итерацию в цикле, так и продолжение исполнения - Т.Е. ДЖАМП ПО ЛЮБОМУ) Вывод - вы либо прропускаете джам и выполняете операцию (если условие возвращает состояние true(1)) и потом прыгаете на исполнение программы далее; или прыгаете и исполняете операции (если условие возвращает состояние false(0)) и просто продолжаете выполнение (не прыгаете) программы далее. Т.Е. утверждение не верно - но если вы пишете и тестите производительность программы в дебаге то тогда ... ну ... шош я могу сказать ... успехов
+MrRadiostep Лекции ведутся в рамках двухгодичного образования на наших проектах Технопарк, Техносфера и Технотрек. Так как у нас образование полностью бесплатное, мы делимся записью лекций со всеми.
много лишних слов ни о чем. здравствуйте, тема, определения, понятия, терема и по ходу неформальное объяснение (на пальцах)... а тут говорит, говорит, а еще ничего не сказал - надо же понимать, что это не детский сад целевая аудитория
Часть 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 - Оценка сложности быстрого умножения
Спасибо, помогло
1
как же доступно он объясняет ☺ хороший препод, ждём некст лекции
Спасибо большое! Очень интересная лекция! Безусловно, для меня, как для школьника, было несколько сложных моментов, однако спустя некоторое время они стали мне понятны. Алгоритмы быстрого вычисления степени и быстрого умножения, действительно, удивили меня! Постараюсь посмотреть и вникнуть в следующие лекции, которые, как мне кажется, будут еще более интересными!
Какой замечательный препод!
На 2x идеально идёт, под чаёк с конфетками. Прям кайфанул)))
спасибо. все доступно. лекция и препод супер
Спасибо вам за лекции!
Очень интересно и все понятно, спасибо!
тот момент когда все вокруг считают тебя недостижимо умным, а ты, после просмотра видосика на Ютубе осознаешь, что все твои знания на уровне дворовой кошки..
__(:з」∠)__
Тссс)) не пали контору)))
А вот и синдром самозванца
я могу тебе 2+2 объяснить так что ты себя глупым почувствуешь, сложно объяснять несложно)))
Люблю такие лекции, которые не понять очень сложно). Супер! А то есть такие, которые начнут сразу формулы писать
Здравствуйте.
На слайде 2:08:59 , наверное, опечатка во втором выражении. Там написано
x^18 = (x^9)^2 = ((x^8 * x)^2)^2 = ...........
А должно быть
x^18 = (x^9)^2 = (x^8 * x)^2 = ...........
т.е. одно лишнее возведение в степень двойки.
там в формуле ошибка на 22:14. sum(1 до N) = N * (N +1) / 2. ПЛЮС там нужен. Плюс, а не минус.
Да ошибка, но сути не меняет
все правильно так как индексы в массиве начинаются с нуля (99 + 0) * 100 / 2
Препод хороший, но как он называет имена и названия!!! По его произношению просто невозможно найти источник.
Хоть бы в презентацию вставлял. Или в описание добавили бы с временными метками.
Спасибо! Интересная лекция!
PS. Только вот один момент, краткость кода - это хорошо, скорость выполнения - тоже хорошо, но вопрос читаемости кода, за пример с множественными присвоениями в одном выражении могут и побить на работе...
в данном случае вполне допустимо, здесь уже, где как принято, но я за более длинный, но и более понятный код
32:45 объясните плиз, как там получается 2 в степени N? Матан давно уже был, я подзабыл(
Если рассуждать логически, то всё понятно и без сложных мат. преобразований: представь, что у тебя есть двоичное число разрядностью N, где N - количество предметов. Каждый предмет может либо присутствовать в комбинации (1), либо нет (0), т.е. для каждого предмета существует 2 состояния.
Пусть, например, 0 разряд - телевизор, 1 разряд - кофемолка, 2 разряд - кошелёк, тогда мы можем составить следующие комбинации:
Если бы у нас был только 1 предмет:
- 0 (т.е. не берём ничего);
- 1 (берём телевизор).
Если бы было 2 предмета:
- 0 0 (ничего);
- 0 1 (берём телевизор);
- 1 0 (берём кофемолку);
- 1 1 (берём всё).
Для 3-х предметов:
- 0 0 0 (ничего);
- 0 0 1 (только телевизор);
- 0 1 0 (только кофемолка);
- 0 1 1 (кофемолка и телевизор);
- 1 0 0 (только кошелёк);
- 1 0 1 (кошелёк и телевизор);
- 1 1 0 (кошелёк и кофемолка);
- 1 1 1 (берём всё).
Очевидно, что для каждого нового предмета в группе кол-во возможных комбинаций удваивается, т.к. существующие комбинации умножаются на 2 возможных состояния нового предмета. Т.е. общее кол-во комбинаций = 2ⁿ.
p.s.: ролик не смотрел, только пробежался по комментариям, поэтому не знаю, что и как объяснил преподаватель. Но это объяснение кажется настолько интуитивно понятным, что проблем быть не должно.
Подскажите, откуда получилось (1+1)^N на 32:47.
Вот 2^N - понимаю, 2 варианта (0 и 1), а (1+1)^N - не пойму.
Спасибо
удаление массива:
delete c;
в плюсиках некорректно. Очень легко убедиться в этом, создав класс со счетчиком созданных элементов. Если потом склепать массив через
Class *c = new Class[n]
удалить:
delete c;
а потом посмотреть, сколько выжило экземпляров класса, то увидим, что помер всего один (н-1 выжили)
Бум смотреть )
Благодарю
Эта задача с мешком) мы такие в экселе решали через поиск решений)
Есть там у кого алгоритм решения задачи с мешками?)очь нужно)
на 18 минуте сдаюсь
Отличная лекция, спасибо! А где домашние задания?
честно говоря стал изучать алгоритмы по corsera, но ваши лекции гораздо понятнее, эх почему я не пошел на ВМК!
да, домашки интересно бы прорешать
даже я б сказал, нужно
35:19 в экспоненте
Когда Ходорковский успел стать специалистом по алгоритмам
Наверное, пока сидел 😀
@@AlexBukreev1234 да нееее... Его ж за это и посадили, был слишком силен в алгоритмах))
пока был барак... Обама
1:39:26: -O3 или -Ofast вам в помощь для ускорения)))
andru shevchenko от того что ты укажешь такие ключи компиляции процессор не станет складывать числа быстрее
ru.wikipedia.org/wiki/SIMD
ds163ify
станет еще и как)) ... учить нада не только мат часть
задача комивояжера решается и не с помощью не очень сложного алгоритма
Отрицание отрицания?
@@Das.Kleine.Krokodil для таких -нехороших- персонажей, без надобности использующих по несколько отрицаний в одном предложении, в аду должна быть предусмотрена специальная комната, наподобие той, в которую попал один из героев фильма "Евротур". Вот только слова на бумажке должны быть сложнее, чем пресловутое _"Flugegeheimen"..._
про машину всем известно, а кто такой Мышонок Тьюринга ?
на микрофоне носок забыли
Для чего эти лекции делаются?
+MrRadiostep кому-то проще посмотреть такую лекцию, чтобы приобрести начальное представление об анализе алгоритмов и самих алгоритмах, чем читать книги.
чет какая-то древняя лекция, а ниче, что задачю о рюкзаке можно через 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ть тактов ...
о Боги ... ох уж эти алгоритмисты - хотя лекции норм но не нада народ пугать
andru shevchenko xmm регистры предназначены для операций над числами с плавающей точкой, здесь же идет речь о целочисленной арифметике. чуть позже лектор как раз это и говорит
не верно в корне ... ХММ/УММ/ZMM это векторные регистры (ru.wikipedia.org/wiki/SIMD - тут про это пишут) с ними (c векторными регистрами) можно выполнять как потоковые операции целочисленные так и с плавающей точкой
andru shevchenko, современные процессоры - это частный случай. Есть тонна микроконтроллеров, которые не обладают такими свойствами, а им, к примеру, нужно много операций совершать с unix time. Или работать с числами, во много раз превосходящими длину процессорного слова. Так что это вышесказанное замечание мимо кассы.
на ~51:xx не верная инфа - товарищ сильный алгоритмист - это понятно ... Но вот на асме пишет вряд ли.
и так пояснение: есть на Intel/Cortex такая команда как CMP, которая передает/преобразует не измененные биты регистра флагов состояния в необходимые. И опять же все просто: он написал в первом примере сравнение и исполнение одного из действий (двух действий) и во втором приятие первого и подправка второго - но вот в чем тут закавыка - все очень сильно зависит от а) архитектуры процессора (RISC - Cortex-A15/53 или CISC - Intel i3-i7) и б) зависит от набора переданных флагов компилятору (какой компиялятор и в каком режиме была скомпилированна программа - Релиз(-O3 -ffast-math и т.п.)/Дебаг).
Итак почему я не согласен:
00) Смена флага состояния
01) джамп на нужное место в локальном участке памяти (для реализации подИфного условия - одного из)
10) джамп на далее (под далее следует понимать, как следующую итерацию в цикле, так и продолжение исполнения - Т.Е. ДЖАМП ПО ЛЮБОМУ)
Вывод - вы либо прропускаете джам и выполняете операцию (если условие возвращает состояние true(1)) и потом прыгаете на исполнение программы далее; или прыгаете и исполняете операции (если условие возвращает состояние false(0)) и просто продолжаете выполнение (не прыгаете) программы далее.
Т.Е. утверждение не верно - но если вы пишете и тестите производительность программы в дебаге то тогда ... ну ... шош я могу сказать ... успехов
Для чего эти лекции снимают и вакладывают?
+MrRadiostep Лекции ведутся в рамках двухгодичного образования на наших проектах Технопарк, Техносфера и Технотрек. Так как у нас образование полностью бесплатное, мы делимся записью лекций со всеми.
+MrRadiostep Реклама mail.ru
Santiago Silva ясно. А я то думаю, почему так непонятно объясняют.
+MrRadiostep ты знаешь что-то получше?
Xyz Null я знаю, пользуйся.
class.coursera.org/algo-004/lecture
косплей на щелкунчика
много лишних слов ни о чем.
здравствуйте, тема, определения, понятия, терема и по ходу неформальное объяснение (на пальцах)... а тут говорит, говорит, а еще ничего не сказал - надо же понимать, что это не детский сад целевая аудитория
просто это первая лекция
потом все что нужно, без воды
ни хрена не понятно.
Спасибо огромное за лекцию!
Спасибо огромное за лекцию!