1. Алгоритмы и структуры данных. Введение

[@gennadygennady3458]

Часть 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 - Оценка сложности быстрого умножения

[@Boykotron]

Спасибо, помогло

[@pavelkazerskii6418]

1

[@zazx6185]

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

[@MN1R]

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

[@СашаАлександр-е4м]

На 2x идеально идёт, под чаёк с конфетками. Прям кайфанул)))

[@liudmilam1287]

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

[@timsteel1060]

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

[@kravtcovivan438]

Тссс)) не пали контору)))

[@ДавидРибак-щ4ь]

А вот и синдром самозванца

[@shlopaiushiy-po-popke]

я могу тебе 2+2 объяснить так что ты себя глупым почувствуешь, сложно объяснять несложно)))

[@zoni196]

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

[@MegaHacker342]

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

[@Govindachandradas]

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

[@nktnsmn]

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

[@EshkinKot1980]

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

[@xagent]

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

[@deniskhakimov]

Если рассуждать логически, то всё понятно и без сложных мат. преобразований: представь, что у тебя есть двоичное число разрядностью 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.: ролик не смотрел, только пробежался по комментариям, поэтому не знаю, что и как объяснил преподаватель. Но это объяснение кажется настолько интуитивно понятным, что проблем быть не должно.

[@alextokarev7562]

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

[@МаксимАлексеев-ч4й]

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

[@alexl6255]

Да ошибка, но сути не меняет

[@IldarSadykov-f6e]

все правильно так как индексы в массиве начинаются с нуля (99 + 0) * 100 / 2

[@andreyevlash725]

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

[@crashoverride9681]

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

[@NikolayMishin]

в данном случае вполне допустимо, здесь уже, где как принято, но я за более длинный, но и более понятный код

[@suvar8667]

Спасибо

[@ImmortalBest]

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

[@MsMReff]

Благодарю

[@pro100SOm]

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

[@NikolayMishin]

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

[@Das.Kleine.Krokodil]

да, домашки интересно бы прорешать даже я б сказал, нужно

[@xagent]

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

[@AlexBukreev1234]

Наверное, пока сидел 😀

[@ДедМопед-ш8ъ]

​@@AlexBukreev1234 да нееее... Его ж за это и посадили, был слишком силен в алгоритмах))

[@CantPickTheNameIwant]

пока был барак... Обама

[@volirvag7648]

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

[@ОляНикитина-й4п]

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

[@hypergloom600]

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

[@olgapolka168]

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

[@momylove5704]

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

[@Das.Kleine.Krokodil]

Отрицание отрицания?

[@deniskhakimov]

@@Das.Kleine.Krokodil для таких -нехороших- персонажей, без надобности использующих по несколько отрицаний в одном предложении, в аду должна быть предусмотрена специальная комната, наподобие той, в которую попал один из героев фильма "Евротур". Вот только слова на бумажке должны быть сложнее, чем пресловутое _"Flugegeheimen"..._

[@lllbenderlll]

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

[@ds163ify]

andru shevchenko от того что ты укажешь такие ключи компиляции процессор не станет складывать числа быстрее

[@lllbenderlll]

ru.wikipedia.org/wiki/SIMD ds163ify

[@lllbenderlll]

станет еще и как)) ... учить нада не только мат часть

[@MrRadiostep]

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

[@m110h1986]

+MrRadiostep кому-то проще посмотреть такую лекцию, чтобы приобрести начальное представление об анализе алгоритмов и самих алгоритмах, чем читать книги.

[@dmitryponyatov2158]

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

[@dmitryponyatov2158]

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

[@lllbenderlll]

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

[@lllbenderlll]

(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ть тактов ... о Боги ... ох уж эти алгоритмисты - хотя лекции норм но не нада народ пугать

[@ds163ify]

andru shevchenko xmm регистры предназначены для операций над числами с плавающей точкой, здесь же идет речь о целочисленной арифметике. чуть позже лектор как раз это и говорит

[@lllbenderlll]

не верно в корне ... ХММ/УММ/ZMM это векторные регистры (ru.wikipedia.org/wiki/SIMD - тут про это пишут) с ними (c векторными регистрами) можно выполнять как потоковые операции целочисленные так и с плавающей точкой

[@ivan.kulenko]

andru shevchenko, современные процессоры - это частный случай. Есть тонна микроконтроллеров, которые не обладают такими свойствами, а им, к примеру, нужно много операций совершать с unix time. Или работать с числами, во много раз превосходящими длину процессорного слова. Так что это вышесказанное замечание мимо кассы.

[@MrRadiostep]

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

[@vkteamchannel]

+MrRadiostep Лекции ведутся в рамках двухгодичного образования на наших проектах Технопарк, Техносфера и Технотрек. Так как у нас образование полностью бесплатное, мы делимся записью лекций со всеми.

[@AbuSalmanAngoli]

+MrRadiostep Реклама mail.ru

[@MrRadiostep]

Santiago Silva ясно. А я то думаю, почему так непонятно объясняют.

[@XyzNull9]

+MrRadiostep ты знаешь что-то получше?

[@AbuSalmanAngoli]

Xyz Null я знаю, пользуйся. class.coursera.org/algo-004/lecture

[@sergioostanioni5390]

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

[@Das.Kleine.Krokodil]

просто это первая лекция потом все что нужно, без воды

[@hooked74]

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

[@pro100SOm]

а в чем противоречие? асимптотика только хуже и выигрыш происходит на малых н... лектор об этом и говорил

[@VSsoviet]

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

[@ВиталийСитников-э3б]

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

[@olgaermolaeva5207]

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

[@rugeneus]

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