АиСД S01E01. Алгоритмы. Оценка времени. Сортировка слиянием.

• Алгоритм - это последовательность действий, приводящих к определенному результату.  

• Алгоритм принимает входные данные, обрабатывает их и выдает выходные данные.  

• В реальной жизни алгоритмы могут быть сложнее, например, работать с данными в сети или на нескольких процессорах.  

• Алгоритмы описываются с помощью псевдокода, а не блок-схем.  

• Псевдокод позволяет структурировать и понятно описывать алгоритмы.  

• Пример: алгоритм поиска максимума в массиве.  

• Эффективность алгоритма измеряется временем работы.  

• Время работы зависит от количества операций, которые выполняет алгоритм.  

• Операции могут быть разными для разных процессоров и оптимизаций.  

• RAM модель предполагает, что все данные хранятся в одном большом массиве.  

• Операции включают чтение и запись элементов массива.  

• Время работы алгоритма зависит от количества операций и длины массива.  

• Время работы алгоритма можно оценить в операциях.  

• Оценка времени работы зависит от качества написания алгоритма и инструкций.  

• Линейное время работы означает, что время работы увеличивается пропорционально размеру массива.  

• Формальные оценки показывают, что время работы не превышает определенную константу.  

• Оценка сверху означает, что время работы не больше заданной константы.  

• Оценка снизу означает, что время работы не меньше заданной константы.  

• Обсуждение равенства и неравенства.  

• Пример с числами и их сравнением.  

• Введение в сортировку массивов.  

• Объяснение, как доказывать работу алгоритмов.  

• Пример доказательства для алгоритма сортировки вставками.  

• Использование метода эмпатической индукции.  

• Объяснение работы алгоритма вставки.  

• Пример вставки элемента в отсортированный массив.  

• Обсуждение времени работы алгоритма.  

• Обсуждение времени работы алгоритмов в худшем случае.  

• Пример оценки времени работы алгоритма для массива.  

• Важность оценки времени работы в худшем случае.  

• Объяснение оценки времени работы снизу.  

• Пример доказательства, что время работы не меньше, чем в квадрате.  

• Важность оценки времени работы сверху и снизу.  

• Подведение итогов и переход к другим моделям.  

• Обсуждение времени работы в зависимости от модели.  

• Введение в следующий алгоритм - слияние.  

• Сортировка слиянием работает быстрее, чем сортировка в квадрате.  

• Процедура слияния объединяет два отсортированных массива в один большой массив.  

• Пример: массивы 1, 4, 8 и 72, 6 объединяются в массив 1, 2, 4, 6, 8.  

• Выбираем минимальный элемент из массивов A и B.  

• Убираем минимальный элемент из массивов и добавляем его в новый массив.  

• Повторяем процесс для оставшихся элементов массивов A и B.  

• Пишем код для слияния массивов.  

• Проверяем, закончился ли один из массивов, и если да, то добавляем элемент из другого массива.  

• Увеличиваем счетчик итераций для каждого массива.  

• Подсчитываем количество итераций для слияния.  

• Время работы зависит от количества итераций и размера массивов.  

• Метод "разделяй и властвуй" используется для сортировки массивов.  

• Массив делится пополам, и каждая половина сортируется отдельно.  

• Затем отсортированные части объединяются в один большой отсортированный массив.  

• Делим массив на две части: левую и правую.  

• Вызываем сортировку для каждой части.  

• Объединяем отсортированные части в один массив.  

• Если массив пустой, останавливаем рекурсию.  

• Добавляем условие для обработки пустых массивов.  

• Завершаем рекурсию и объединяем массивы.  

• Рассматривается рекурсивный алгоритм и его время работы.  

• Необходимо оценить суммарное время всех рекурсивных запусков.  

• Используется метод "картинки" для визуализации времени работы.  

• Время работы пропорционально длине прямоугольников.  

• Каждый слой рекурсии требует времени, пропорционального длине прямоугольников.  

• Суммарное время работы равно сумме длин всех прямоугольников.  

• Время работы можно записать с помощью рекуррентных функций.  

• Рассматривается пример с действиями и их стоимостью.  

• Раскрываются скобки и оценивается время работы алгоритма.  

• Переход к более строгому доказательству с помощью математической индукции.  

• Важно подобрать правильное вложение и доказать индукционное положение.  

• Пример с доказательством для случая, когда массив делится на два.  

• Обсуждение замены логарифмов и формул.  

• Упоминание о том, что формула должна быть простой и понятной.  

• Пример с логарифмом по основанию два.  

• Объяснение, почему важно явно писать константы.  

• Пример с логарифмами по любому основанию.  

• Указание на то, что константы не влияют на симметрию.  

• Обсуждение возможных ошибок в сортировке вставками.  

• Пример с функцией, которая не равна большой.  

• Доказательство, что сортировка вставками работает с линейным временем.  

• Объяснение работы сортировки вставками.  

• Указание на ошибки в индукции.  

• Пример с бесконечностью и константами.  

• Подведение итогов и обсуждение непонятных моментов.  

• Объявление о практике на следующей неделе.  

• Призыв к студентам готовиться к практике.