| Россия, Москва, МВТУ им. Баумана Н.Э. |
Инспектор
Спонсор: Школа анализа данных (Яндекс)
Вы можете этот курс.
Опубликован: 01.01.2015 | Уровень: для всех | Доступ: платный | ВУЗ: Московский государственный университет имени М.В.Ломоносова
Лекция 1:
Сложность и модели вычислений. Анализ учетных стоимостей
Лекция 1
Аннотация: Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
Лекция 1
