Лекция 1. Сложность и модели вычислений (Алгоритмы и структуры данных, часть 1)

Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях.

Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике.

Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.

Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков.

Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах.

Лекция №1 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов

[valera]

00:00 - ram модель вычислений
23:00 - время работы алгоритмов
32:00 - оценка лучшего времени сортировки на сравнениях
34:00 - модель разрешающих деревьев
38:00 - оценка О(n*log(n))
54:30 - не детерминированные алгоритмы
1:08:00 - учетная стоимость работы алгоритма/структуры данных
1:22:00 - банковский метод учета стоимостей операций

[TheRepatriant]

Давно ищу нечто подобное. Буду смотреть до просветления. Лайк и подписка!

[oleglevchenko]

Спасибо за лекцию! На доске вроде очепятка. не cash, а cache.

[timtimbot]

подскажите чем лекция от семинара отличается в плейлисте?

[ilya]

Что-то не понял, почему M <= 2^W на 22:15 . Может кто-нибудь пояснить подробнее с примером?

[mistrebrown]

Примерно с 45:00 начинает создаваться впечатление, будто преподаватель сам имеет слабое представление об алгоритмах

[dd]

После 30 минуты пошла муть. К чему людям на этом этапе рассказывать про деревья, если по ходу курса ещё не дошли даже до базовых структур данных. А деревья поиска вообще в 7 лекции. Начать хотя бы уж со списков, если так в деревья хочется нырнуть. Сложилось впечатление, что лектор имеет поверхностные знания по теме.