Практические задания по курсам "Методы программирования" и "Программная инженерия" РФФ ННГУ
Практика рассчитана на закрепление навыков программирования, работы с алгоритмами и проектирования программных систем. Задания охватывают структуры данных, сортировку, поиск маршрутов, моделирование и объектно-ориентированный подход.
Для выполнения работ потребуется Python версии 3.9 или новее. В зависимости от выбранного задания могут понадобиться библиотеки NumPy, Pandas, Matplotlib, TensorFlow и Pillow. Разрабатывать программы можно в любом удобном редакторе: IDLE, Visual Studio Code, Notepad++, PyCharm или Vim.
Отдельные задания удобно выполнять в интерактивных блокнотах с возможностью подключения удалённых вычислительных ресурсов. Это особенно актуально для экспериментов, связанных с обработкой данных, визуализацией и машинным обучением.
Организация файлов
Для каждого студента необходимо создать отдельную директорию внутри папки своей учебной группы. Название каталога должно содержать фамилию и имя. Работать следует только в собственной папке: изменять файлы других студентов, а также содержимое корневого каталога запрещено.
При проверке основное внимание будет уделяться названиям файлов. Поэтому в имени каждого решения рекомендуется указывать номер лабораторной работы, например `lab_1.py`, `lab_2.py` и так далее. Такой подход упрощает сортировку материалов и снижает риск потери нужного файла.
Крайний срок приёма работ - 27 мая 2024 года, 11:00.
Лабораторная работа 1. Структуры данных
В первой работе необходимо изучить базовые структуры данных и показать, как они применяются при решении практических задач. Следует обратить внимание на списки, кортежи, множества, словари, стеки и очереди.
В отчёте или программном коде желательно продемонстрировать:
- создание и заполнение структур;
- добавление и удаление элементов;
- поиск значений;
- изменение порядка элементов;
- обработку пустых и некорректных входных данных;
- сравнение удобства применения разных структур.
Важно не ограничиваться вызовом готовых функций. Нужно понимать, какие операции выполняются внутри программы и как меняется сложность алгоритма при увеличении объёма данных.
Лабораторная работа 2. Алгоритмы сортировки
Для каждого исходного списка требуется реализовать один из предложенных алгоритмов сортировки. Конкретный набор из четырёх алгоритмов определяется индивидуально случайным образом.
Для выбора четырёх номеров можно использовать следующий код:
```python
import random
selected = random.sample(range(1, 18), 4)
print(selected)
```
Команда сформирует четыре неповторяющихся значения из диапазона от 1 до 17. Полученные номера определяют алгоритмы, которые необходимо реализовать.
При выполнении задания важно:
1. написать самостоятельную реализацию каждого алгоритма;
2. проверить её на массивах разного размера;
3. протестировать уже отсортированные и обратно отсортированные данные;
4. добавить наборы со случайными и повторяющимися элементами;
5. сравнить время работы методов;
6. убедиться, что исходный список не изменяется без необходимости.
Для анализа можно использовать модуль `timeit`. Результаты желательно представить в виде таблицы или графика. Это позволит сопоставить теоретическую оценку сложности алгоритмов с практическим временем выполнения.
Лабораторная работа 3. Поиск пути и структурное программирование
В папке `_3` находится скрипт `gen_lab_origin.py`. Его необходимо запустить и дождаться завершения генерации. Обработка может занимать несколько минут.
После завершения работы программы появится файл `maze-for-u.txt`. Его следует переместить в личную папку студента и использовать как исходную карту лабиринта.
Требуется найти путь от начальной позиции персонажа до ключа. Для решения можно выбрать один алгоритм либо использовать вариант, назначенный в соответствии с сезоном рождения: отсчёт начинается с зимы. Возможные методы:
- алгоритм Дейкстры;
- поиск в ширину;
- поиск в глубину;
- жадный алгоритм.
Каждый способ обладает своими особенностями. Поиск в ширину гарантированно находит кратчайший путь в невзвешенном лабиринте, тогда как поиск в глубину может быстро углубиться в тупиковую ветвь. Алгоритм Дейкстры подходит для карт с различной стоимостью переходов, а жадный поиск ориентируется прежде всего на расстояние до цели и не всегда гарантирует оптимальный результат.
Затем необходимо применить алгоритм A*. Параметры алгоритма должны включать:
- вес функции `g(x)`;
- вес эвристической функции `h(x)`;
- максимальный размер списка возможных шагов.
С помощью A* нужно определить оптимальный маршрут от ключа до ближайшего выхода. Итог следует сохранить в файл `maze-for-me-done.txt`. В готовой карте:
- ключ обозначается символом `*`;
- участок от начальной позиции до ключа отмечается точками;
- путь от ключа к выходу обозначается запятыми.
Дополнительно рекомендуется проверить, что программа корректно работает при отсутствии маршрута, при наличии нескольких одинаково коротких путей и при расположении выхода рядом с границей карты.
Лабораторная работа 4. Моделирование радиолокационной системы
Последняя работа посвящена моделированию радара и движущихся воздушных объектов. Необходимо создать систему, в которой один радар излучает радиоимпульсы в направлении, заданном азимутом от 0 до 360 градусов и углом места от 0 до 90 градусов. Сигнал отражается от летящих объектов и возвращается к радару через время `t`.
Исходные данные должны включать:
- декартовы координаты радара в метрах;
- количество воздушных объектов;
- координаты каждого объекта;
- проекции скоростей объектов по осям координат;
- время, прошедшее после излучения импульса.
Программу следует разделить на классы. Как минимум потребуются:
- класс радара;
- класс летающего объекта;
- класс, отвечающий за расчёты координат или преобразования;
- при необходимости - отдельный компонент для управления моделью и вывода результатов.
Класс радара необходимо реализовать с применением паттерна Singleton. Это означает, что в системе может существовать только один экземпляр радара, к которому обращаются все остальные компоненты программы.
Для каждого воздушного объекта нужно рассчитывать сферические координаты относительно радара:
- дальность;
- азимут;
- угол места.
На первом этапе программа выводит текущие координаты объектов. Затем пользователь вводит с клавиатуры время в секундах, после чего система рассчитывает новые положения с учётом скоростей и повторно выводит сферические координаты.
Рекомендации по реализации
Перед написанием кода стоит разделить задачу на небольшие функции. Например, отдельно можно реализовать преобразование декартовых координат в сферические, обновление положения объекта, проверку допустимых углов и форматирование результата.
Для повышения надёжности следует проверять входные данные. Координаты должны быть числовыми, время - неотрицательным, а количество объектов - целым положительным значением. Также нужно учитывать особые случаи: объект может находиться непосредственно над радаром, на одной вертикали с ним или совпадать с его положением.
В коде желательно придерживаться единого стиля именования, добавлять комментарии к нетривиальным участкам и избегать дублирования. Повторяющиеся вычисления лучше вынести в отдельные методы или вспомогательные классы.
Что должно быть в готовой работе
Перед сдачей необходимо убедиться, что:
- все файлы находятся в личной папке;
- названия содержат номера лабораторных работ;
- программы запускаются без критических ошибок;
- присутствуют тестовые примеры;
- обработаны некорректные входные данные;
- результаты работы можно воспроизвести;
- итоговый файл лабиринта сохранён под требуемым именем;
- для радиолокационной модели соблюдён объектно-ориентированный подход;
- Singleton для радара реализован корректно;
- вычисления координат после заданного промежутка времени выполняются с учётом скорости объектов.
Такой порядок выполнения позволяет последовательно пройти путь от базовых операций со структурами данных до создания полноценной программной модели с алгоритмами поиска, визуальным представлением результатов и объектной архитектурой.
