Алгоритмы и структуры данных (1)

О практиках
Работа в группах из 3-х человек.
Постарайтесь сформировать группы, в которых будет хотя бы один уверенный программист.
Каждая практика – решение основных задач + задачи повышенной сложности (для повышения баллов за практики).
То, что не успеете решить – выносится на дз, с обязательной защитой в начале следующей практики, иначе работа принята не будет.
Используем любой известный Вам язык программирования, но все алгоритмы пишем самостоятельно, не берём готовые библиотеки, и методы.
Оценивание будет производиться за каждую задачу каждому человеку в команде по результатам защиты кода (по необходимости), алгоритма и тестов (по необходимости) в трёхзначной шкале (+ ; +/- ; -).
03.10.2022
НИУ ВШЭ - Пермь

Практика №1
«Программирование рекурсивных процедур и функций»

Основная задача
Понять и реализовать 3 различных
алгоритма нахождения
чисел Фибоначчи.
Подсказка: один алгоритм рекурсивный, два – итерационных.
Сравните эффективность (по времени, используемой памяти и т.п.) каждого алгоритма и докажите, какой будет лучше и почему.
Помните, что рекурсию не всегда можно свести к итерации, но эта задача – не тот случай, тут всё хорошо!
03.10.2022
НИУ ВШЭ - Пермь

Задача повышенной сложности
Рекурсивно вычислить определитель матрицы разложением по строке/столбцу.
Возможно ли вычислить итерационно?
03.10.2022
НИУ ВШЭ - Пермь

Практика №2
«Продолжение работы с рекурсивными и итерационными алгоритмами»

Задача с прошлого занятия
Рекурсивно вычислить определитель матрицы разложением по строке/столбцу.
Возможно ли вычислить итерационно?
03.10.2022
НИУ ВШЭ - Пермь

Задача на определитель матрицы
Вычислить рекурсивно определитель матрицы с помощью метода Гаусса.
Какой метод более точный и почему?
Какой метод более быстрый и почему?
03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

Практика №3
«Рекуррентные соотношения и итерационный алгоритм»

Задача по генерации перестановок
Рекурсивная генерация всех n-факториал перестановок. Параметр n задаётся от 0 до 9.
n – входной параметр (количество разрядов).
Два варианта (посчитать количество перестановок):
перестановка без повторений (всего n! перестановок);
перестановка с повторениями (всего nn перестановок) – дополнительное задание.
Вывод в лексикографическом порядке или другом (объяснить выбор).
03.10.2022
НИУ ВШЭ - Пермь

Задача по генерации перестановок
Например, найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:
1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1
03.10.2022
НИУ ВШЭ - Пермь

Задача по генерации перестановок
Дополнительно дублирую слайды с лекции:
03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

Задача по вычислению ленточного определителя
Вычисление ленточного определителя (из презентации с лекции):
итерационный способ;
на основе выведенной математической формулы.
Вспомогательные материалы по ленточной матрице:
Исходное состояние – Трёхдиагональная матрица: https://ru.wikipedia.org/wiki/Трёхдиагональная_матрица, решается с помощью метода прогонки: https://ru.wikipedia.org/wiki/Метод_прогонки. Можно попробовать подумать над вариантом пяти и более диагональных матриц (по желанию).
Математическая выкладка: https://scask.ru/i_book_alg_s.php?id=420&ysclid=l88lafgae453071270
Далее продублированы слайды из презентации с лекции.
03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

03.10.2022
НИУ ВШЭ - Пермь

Практика №4
«Рекурсивное (по двум параметрам) и итерационное вычисление НОД и НОК (быстрый и медленный алгоритм Евклида)»

Задача по вычислению НОД и НОК
Вычислить НОД (англ. greatest common divisor) и НОК (англ. least common multiple):
реализовать итерационный алгоритм;
реализовать рекурсивный алгоритм.
оцените время работы алгоритмов.
Алгоритм Евклида для нахождения НОД - один из первых алгоритмов в истории, использовался ещё в Древней Греции, и дошёл до наших дней. В изначальном виде он назывался “взаимным вычитанием”, так как заключался в поочерёдном вычитании меньшего числа из большего, пока одно из них не станет равным 0. Сегодня чаще всего вместо вычитания используется взятие остатка от деления, но суть алгоритма сохранилась. Алгоритм заключается в построении ряда чисел следующего вида (a>b):
03.10.2022
НИУ ВШЭ - Пермь

Задача по вычислению НОД и НОК
Где каждое последующее число является остатком от деления предпредыдущего на предыдущее:
Ряд заканчивается, когда остаток от деления предпоследнего числа на последнее становится равным 0:
В таком случае утверждается, что:
03.10.2022
НИУ ВШЭ - Пермь

Задача по вычислению НОД и НОК
Дополнительно можете доказать описанное ранее утверждение, а также попробуйте реализовать другой / другие алгоритмы.
Для вычисления НОК используется нахождение НОД, тогда в общем виде формула нахождения НОК будет выглядеть так:
03.10.2022
НИУ ВШЭ - Пермь

Практика №5
«Взаимная и двойная рекурсия»

Задача по взаимной рекурсии
Необходимо сгенерировать все строки длины n в алфавите {0, 1}, в которых нет двух подряд идущих нулей.
Например, при n = 3, результатом будет {010, 011, 110, 101, 111}.
Задача: реализовать рекурсивный алгоритм генерации таких строк, при этом если будет выбран переборный алгоритм, то максимальная оценка за это задание 0,4 балла (т.к. сложность алгоритма экспоненциальная). Перебор можно использовать для проверки.
Воспользуйтесь материалами из лекции по взаимной рекурсии.
03.10.2022
НИУ ВШЭ - Пермь

Задача по двойной рекурсии
03.10.2022
НИУ ВШЭ - Пермь

Задача по двойной рекурсии (продолжение)
03.10.2022
НИУ ВШЭ - Пермь