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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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