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

Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах. Лекция №1 в курсе “Алгоритмы и структуры данных, часть 1“, осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: Все видео курса по порядку: