1. Алгоритмы и структуры данных. Введение
HTML-код
- Опубликовано: 12 сен 2024
- «Техносфера Mail.ru Group» при МГУ им. М. В. Ломоносова.
Подготовительный курс «Алгоритмы и структуры данных».
Лекция № 1 «Введение. Исполнители. Абстракции интерфейсов. Рекурсия».
Лектор - Сергей Бабичев.
Содержание лекции:
Сложность алгоритмов. O-нотация. Задача о наполнении рюкзака. Ресурсы исполнителя. Эффективность алгоритма. Язык С++ как исполнитель алгоритма. Отображение алгоритма на исполнителей. Инварианты. Абстракция интерфейсов «стек» и «множество». Рекурсия и итерация. Основная теорема о рекурсии.
Цель курса - ознакомить слушателей с основными алгоритмами, применяемыми для разработки программного обеспечения. Научить выбирать подходящие структуры данных и алгоритмы для реализации возникающих задач. Научить использовать языки С и С++ как инструмент для реализации алгоритмов.
Получаемые навыки
• Знание основных понятий: исполнитель, абстракция, объекты, методы, итерация, рекурсия, жадные алгоритмы, динамическое программирование, сортировка, поиск, графы.
• Умение анализировать основные свойства алгоритмов.
• Умение выбирать необходимые структуры данных для решения задач и обосновывать свой выбор.
• Уметь эффективно реализовывать алгоритмы на языках С и С++.
Смотрите также:
• Другие лекции курса: bit.ly/1QP7zVq
• Курс «Введение в анализ данных»: bit.ly/1V1ONMw
• Курс «Информационный поиск»: bit.ly/1TWc2IO
VK Team - это безграничные возможности проявить себя. Мы делаем современные и быстрые интернет-сервисы, доступные каждому. На этом канале делимся опытом компании VK, рассказываем о технологиях, наших образовательных проектах и жизни команды.
😎 Сообщество ВКонтакте: vkteam
👨🎓 VK Education: education.vk.c...
🏆 Чемпионаты: cups.online/
👨💻 Карьера в VK: team.vk.company/
Часть 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
как же доступно он объясняет ☺ хороший препод, ждём некст лекции
Спасибо большое! Очень интересная лекция! Безусловно, для меня, как для школьника, было несколько сложных моментов, однако спустя некоторое время они стали мне понятны. Алгоритмы быстрого вычисления степени и быстрого умножения, действительно, удивили меня! Постараюсь посмотреть и вникнуть в следующие лекции, которые, как мне кажется, будут еще более интересными!
тот момент когда все вокруг считают тебя недостижимо умным, а ты, после просмотра видосика на Ютубе осознаешь, что все твои знания на уровне дворовой кошки..
__(:з」∠)__
Тссс)) не пали контору)))
А вот и синдром самозванца
я могу тебе 2+2 объяснить так что ты себя глупым почувствуешь, сложно объяснять несложно)))
Люблю такие лекции, которые не понять очень сложно). Супер! А то есть такие, которые начнут сразу формулы писать
Какой замечательный препод!
Спасибо вам за лекции!
Очень интересно и все понятно, спасибо!
спасибо. все доступно. лекция и препод супер
Препод хороший, но как он называет имена и названия!!! По его произношению просто невозможно найти источник.
Хоть бы в презентацию вставлял. Или в описание добавили бы с временными метками.
Спасибо! Интересная лекция!
PS. Только вот один момент, краткость кода - это хорошо, скорость выполнения - тоже хорошо, но вопрос читаемости кода, за пример с множественными присвоениями в одном выражении могут и побить на работе...
в данном случае вполне допустимо, здесь уже, где как принято, но я за более длинный, но и более понятный код
Здравствуйте.
На слайде 2:08:59 , наверное, опечатка во втором выражении. Там написано
x^18 = (x^9)^2 = ((x^8 * x)^2)^2 = ...........
А должно быть
x^18 = (x^9)^2 = (x^8 * x)^2 = ...........
т.е. одно лишнее возведение в степень двойки.
Отличная лекция, спасибо! А где домашние задания?
честно говоря стал изучать алгоритмы по corsera, но ваши лекции гораздо понятнее, эх почему я не пошел на ВМК!
да, домашки интересно бы прорешать
даже я б сказал, нужно
там в формуле ошибка на 22:14. sum(1 до N) = N * (N +1) / 2. ПЛЮС там нужен. Плюс, а не минус.
Да ошибка, но сути не меняет
все правильно так как индексы в массиве начинаются с нуля (99 + 0) * 100 / 2
удаление массива:
delete c;
в плюсиках некорректно. Очень легко убедиться в этом, создав класс со счетчиком созданных элементов. Если потом склепать массив через
Class *c = new Class[n]
удалить:
delete c;
а потом посмотреть, сколько выжило экземпляров класса, то увидим, что помер всего один (н-1 выжили)
Бум смотреть )
Спасибо
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.: ролик не смотрел, только пробежался по комментариям, поэтому не знаю, что и как объяснил преподаватель. Но это объяснение кажется настолько интуитивно понятным, что проблем быть не должно.
Благодарю
Эта задача с мешком) мы такие в экселе решали через поиск решений)
на 18 минуте сдаюсь
Есть там у кого алгоритм решения задачи с мешками?)очь нужно)
Когда Ходорковский успел стать специалистом по алгоритмам
Наверное, пока сидел 😀
@@AlexBukreev1234 да нееее... Его ж за это и посадили, был слишком силен в алгоритмах))
пока был барак... Обама
Подскажите, откуда получилось (1+1)^N на 32:47.
Вот 2^N - понимаю, 2 варианта (0 и 1), а (1+1)^N - не пойму.
про машину всем известно, а кто такой Мышонок Тьюринга ?
35:19 в экспоненте
задача комивояжера решается и не с помощью не очень сложного алгоритма
Отрицание отрицания?
@@Das.Kleine.Krokodil для таких -нехороших- персонажей, без надобности использующих по несколько отрицаний в одном предложении, в аду должна быть предусмотрена специальная комната, наподобие той, в которую попал один из героев фильма "Евротур". Вот только слова на бумажке должны быть сложнее, чем пресловутое _"Flugegeheimen"..._
на микрофоне носок забыли
1:39:26: -O3 или -Ofast вам в помощь для ускорения)))
andru shevchenko от того что ты укажешь такие ключи компиляции процессор не станет складывать числа быстрее
ru.wikipedia.org/wiki/SIMD
ds163ify
станет еще и как)) ... учить нада не только мат часть
Для чего эти лекции делаются?
+MrRadiostep кому-то проще посмотреть такую лекцию, чтобы приобрести начальное представление об анализе алгоритмов и самих алгоритмах, чем читать книги.
на ~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ть тактов ...
о Боги ... ох уж эти алгоритмисты - хотя лекции норм но не нада народ пугать
andru shevchenko xmm регистры предназначены для операций над числами с плавающей точкой, здесь же идет речь о целочисленной арифметике. чуть позже лектор как раз это и говорит
не верно в корне ... ХММ/УММ/ZMM это векторные регистры (ru.wikipedia.org/wiki/SIMD - тут про это пишут) с ними (c векторными регистрами) можно выполнять как потоковые операции целочисленные так и с плавающей точкой
andru shevchenko, современные процессоры - это частный случай. Есть тонна микроконтроллеров, которые не обладают такими свойствами, а им, к примеру, нужно много операций совершать с unix time. Или работать с числами, во много раз превосходящими длину процессорного слова. Так что это вышесказанное замечание мимо кассы.
Для чего эти лекции снимают и вакладывают?
+MrRadiostep Лекции ведутся в рамках двухгодичного образования на наших проектах Технопарк, Техносфера и Технотрек. Так как у нас образование полностью бесплатное, мы делимся записью лекций со всеми.
+MrRadiostep Реклама mail.ru
Santiago Silva ясно. А я то думаю, почему так непонятно объясняют.
+MrRadiostep ты знаешь что-то получше?
Xyz Null я знаю, пользуйся.
class.coursera.org/algo-004/lecture
ни хрена не понятно.
Спасибо огромное за лекцию!
Спасибо огромное за лекцию!