Домашнее задание к лекции 3

Короткий текст в LaTeX про инвариант сортировки. Этот ноутбук — условие, его заполнять и присылать не нужно.

Сдаёте лектору файлы .tex и PDF до дедлайна. Семинаристу это задание не отправляйте: ему — ноутбук семинара 3. В LMS этого ДЗ нет. Код программы присылать не нужно.

Что такое LaTeX

Набор текста командами. Формулы — часть документа, не картинки. Для конспектов алгоритмов так удобно писать инварианты, $\Theta$ и нумерованные шаги.

Тема

Подбросьте монетку и разберите тот алгоритм, который выпал. Сами не выбирайте.

• орёл — сортировка вставками;
• решка — сортировка выбором.

В текст:

• инвариант своими словами;
• 4–5 шагов внешнего цикла на массиве из пяти чисел (не отдельных сравнений);
• чем это не пузырёк;
• время и дополнительная память.

Fool, пузырёк и LSD сюда не подходят: их уже разбирали на лекции.

Шаблон и образец

Шаблон (титул, монетка, кусок align, место под шаги):

https://learn.ai.msu.ru/algo/1/03/hw-lecture.tex

Образец оформления — поразрядная LSD (псевдокод, зачем метод, инвариант, время и память). Домашнее задание при этом не про LSD:

https://learn.ai.msu.ru/algo/1/03/lsd-example.tex

Собираете где получится: браузерный сервис, если открывается; любой другой онлайн-компилятор; локальный TeX, если уже стоит. Ставить компилятор и заводить конкретный сайт не требуется.