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

Подготовительный курс «Алгоритмы и структуры данных».
Лекция № 1 «Введение. Исполнители. Абстракции интерфейсов. Рекурсия».
Лектор — Сергей Бабичев.

Содержание лекции:
Сложность алгоритмов. O-нотация. Задача о наполнении рюкзака. Ресурсы исполнителя. Эффективность алгоритма. Язык С++ как исполнитель алгоритма. Отображение алгоритма на исполнителей. Инварианты. Абстракция интерфейсов «стек» и «множество». Рекурсия и итерация. Основная теорема о рекурсии.

Цель курса — ознакомить слушателей с основными алгоритмами, применяемыми для разработки программного обеспечения. Научить выбирать подходящие структуры данных и алгоритмы для реализации возникающих задач. Научить использовать языки С и С++ как инструмент для реализации алгоритмов.

Получаемые навыки
• Знание основных понятий: исполнитель, абстракция, объекты, методы, итерация, рекурсия, жадные алгоритмы, динамическое программирование, сортировка, поиск, графы.
• Умение анализировать основные свойства алгоритмов.
• Умение выбирать необходимые структуры данных для решения задач и обосновывать свой выбор.
• Уметь эффективно реализовывать алгоритмы на языках С и С++.

Смотрите также:

VK Team — это безграничные возможности проявить себя. Мы делаем современные и быстрые интернет-сервисы, доступные каждому. На этом канале делимся опытом компании VK, рассказываем о технологиях, наших образовательных проектах и жизни команды.

[gennadygennady]

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

[zazx]

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

[zoni]

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

[nktnsmn]

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

[timsteel]

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

[MNR]

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

[MegaHacker]

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

[volirvag]

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

[crashoverride]

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

[EshkinKot]

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

[alextokarev]

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

[hypergloom]

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

[proSOm]

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

[NikolayMishin]

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

[xagent]

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

[ssrjwzs]

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

[andreyevlash]

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

[momylove]

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

[dmitryponyatov]

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

[lllbenderlll]

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