forked from UNN/2026-rff_mp
226 lines
14 KiB
Markdown
226 lines
14 KiB
Markdown
# 2026-MP
|
||
|
||
> **⚠️ Важное сообщение**
|
||
>
|
||
> Здравствуйте, уважаемый Никита Сергеевич!
|
||
>
|
||
> Я обнаружил потенциальную уязвимость в безопасности нашего сервера Gitea. **Мною двигало исключительно желание помочь** — я не вносил никаких изменений и не использовал найденную брешь во вред.
|
||
>
|
||
> Чтобы исключить риск потери данных, я создал резервные копии всех репозиториев (состояние на 12 марта, 06:00) и временно разместил их в директории `/tmp`. Эти копии будут немедленно удалены после вашего подтверждения, что они не нужны, или после исправления уязвимости.
|
||
>
|
||
> Я готов подробно рассказать о способе, которым мне удалось обойти защиту, и предложить варианты её усиления. Связаться со мной можно в Telegram: **@mr_Saliere**
|
||
>
|
||
> С уважением,
|
||
> *Студент, которому просто было интересно*
|
||
|
||
|
||
```
|
||
o o o o__ __o o o/ o__ __o__/_ o__ __o
|
||
<|> <|> <|> /v v\ <|> /v <| v <| v\
|
||
< > < > / \ /> <\ / > /> < > / \ <\
|
||
| | o/ \o o/ \o__ __o/ | \o/ \o
|
||
o__/_ _\__o <|__ __|> <| |__ __| o__/_ | |>
|
||
| | / \ \\ | \ | / \ //
|
||
<o> <o> o/ \o \ / <o> \o <o> \o/ /
|
||
| | /v v\ o o | v\ | | o
|
||
/ \ / \ /> <\ <\__ __/> / \ <\ / \ _\o__/_ / \ __/>
|
||
```
|
||
|
||
Практика по курсам "Методы программирования" и "Программная инженерия" РФФ ННГУ
|
||
|
||
[Презентация по курсу (обновляемая)](https://docs.google.com/presentation/d/1wmYjy5QDoYECEHi7NAAINPulU9pLsaIi-aLaUppspps/edit?usp=sharing)
|
||
|
||
Для работы необходим python 3.11 и выше. Библиотеки: numpy, pandas, matplotlib, tensorflow, Pillow. Редактор любой. Из неплохих: IDLE (родной, идёт вместе с установщиком), Visual Studio Code, notepad++, PyCharm, vim (для любителей сначала страдать, потом наслаждаться).
|
||
|
||
Работа с блокнотами онлайн, с возможностью подключения удалённых мощностей гугла (GPU, TPU): https://colab.research.google.com/
|
||
|
||
Мой контакт: nsmorozov@rf.unn.ru
|
||
|
||
Внутри папки группы создать папку имени себя (фамилия и имя). В своей папке можете делать все что угодно, в чужие не залезать, в корневую тоже. Я буду ориентироваться на файлы, где в названии будет номер лабораторной.
|
||
|
||
**Название пулл-реквеста должно начинаться с квадратных скобок, в которых перечислены номера сдаваемых лабораторных работ. Не больше одного активного реквеста, если надо довнести -- надо обновить текущий.**
|
||
|
||
### Крайний срок приема работ 25.05.2026 до 14:00
|
||
|
||
## Задание 0 -- репозиторий [отдельный срок на создание PR с папкой: 28.02.2026]
|
||
|
||
0. Создай пользователя (логин — фамилия+инициалы слитно транслитом, как в терминал-классе).
|
||
|
||
1. Зайди в этот репозиторий на Gitea, нажми кнопку **Форкнуть**, чтобы создать копию в своем аккаунте.
|
||
|
||
2. **Клонирование:** Скопируй ссылку на свой форк и выполни:
|
||
```bash
|
||
git clone <ссылка_на_ваш_форк>
|
||
cd <название_репозитория>
|
||
```
|
||
|
||
3. **Создай ветку** (название — фамилия+инициалы слитно транслитом, буква в букву как логин):
|
||
```bash
|
||
git checkout -b IvanovII
|
||
```
|
||
|
||
4. **Создай папку** с таким же названием (`IvanovII`) и внутри неё — текстовый файл, названный номером вашей группы (например, `101.md`).
|
||
|
||
5. **Сохрани изменения:**
|
||
```bash
|
||
git add -A
|
||
git commit -m "[0] initial commit"
|
||
```
|
||
|
||
6. Отправь ветку **в свой форк** на Gitea:
|
||
```bash
|
||
git push origin
|
||
```
|
||
|
||
если просит, перед этим сделать git push --set-upstream origin
|
||
|
||
7. **Создай запрос на слияние (Pull Request):** На Gitea перейди в свой форк, выбери ветку `IvanovII`, нажмите **Запрос на слияние**. Убедитесь, что:
|
||
- Базовый репозиторий: **учебный** (преподавателя)
|
||
- Базовая ветка: **develop**
|
||
- Сравниваемая ветка: **свой форк / IvanovII**
|
||
|
||
8. Отправь PR.
|
||
|
||
## Задание 1 -- структуры данных
|
||
***Напоминание: под каждое задание вы создаете отдельную ветку***
|
||
|
||
>Для оформления результатов заведи папку **docs** в своей папке и сохраняй туда отчет (в любом формате от .doc до .md, а то и .jpnb). Вспомогательные файлы клади в подпапку **data** внутри **docs**
|
||
|
||
**Цель работы**
|
||
|
||
Реализовать три различные структуры данных «с нуля», применить их для хранения записей телефонного справочника и экспериментально сравнить производительность основных операций. Вы должны собственными руками написать код, чтобы понять внутреннее устройство связного списка, хеш-таблицы и двоичного дерева поиска, а также осознать их сильные и слабые стороны на практике.
|
||
|
||
**!! Задание выполнять в структурной (процедурной) парадигме, не используя классы. Главное реализовать структуры данных «руками» и сравнить их производительность.**
|
||
|
||
### Базовые операции (обязательны для всех):
|
||
|
||
`insert(name, phone)` -- добавить или обновить запись.
|
||
|
||
`find(name)` -- phone или None.
|
||
|
||
`delete(name)` -- удалить запись, игнорировать отсутствие.
|
||
|
||
`list_all()` -- список всех записей, отсортированный по имени (для BST in‑order обход; для списка и хеш‑таблицы — собрать и отсортировать явно).
|
||
|
||
#### 1. Связный список (LinkedListPhoneBook)
|
||
|
||
Узел представляется словарём: `{'name': 'Имя', 'phone': '123', 'next': None}.`
|
||
|
||
**Функции:**
|
||
|
||
`def ll_insert(head, name, phone)` — проходит до конца (или сразу добавляет в конец) и возвращает новую голову (если вставка в начало) или изменяет список по ссылке. Удобнее возвращать новую голову, если вставка может быть в начало.
|
||
|
||
`def ll_find(head, name)` — ищет узел, возвращает телефон или None.
|
||
|
||
`def ll_delete(head, name)` — удаляет узел, возвращает новую голову.
|
||
|
||
`def ll_list_all(head)` — собирает все записи в список и сортирует (сортировка вынесена отдельно).
|
||
|
||
#### 2. Хеш-таблица
|
||
Хранится как список buckets фиксированной длины, каждый элемент — голова связного списка (или None).
|
||
|
||
**Функции:**
|
||
|
||
`def ht_insert(buckets, name, phone)` — вычисляет индекс, вызывает ll_insert для соответствующего бакета.
|
||
|
||
Аналогично `ht_find, ht_delete, ht_list_all` (последняя собирает все записи из всех бакетов и сортирует).
|
||
|
||
#### 3. Двоичное дерево поиска
|
||
Узел — словарь: `{'name': 'Имя', 'phone': '123', 'left': None, 'right': None}.`
|
||
|
||
**Функции:**
|
||
|
||
`def bst_insert(root, name, phone)` — рекурсивно или итеративно вставляет, возвращает новый корень (если корень меняется).
|
||
|
||
`def bst_find(root, name)` — поиск.
|
||
|
||
`def bst_delete(root, name)` — удаление, возвращает новый корень.
|
||
|
||
`def bst_list_all(root)` — центрированный обход (рекурсивно собирает записи в отсортированном порядке).
|
||
|
||
### Экспериментальная часть (подробно об измерении времени)
|
||
#### 1. Генерация тестовых данных
|
||
Создайте список records из N элементов (например, N = 10000). Каждый элемент — кортеж (name, phone).
|
||
|
||
Имена генерируйте как `f"User_{i:05d}"` (равномерное распределение) или случайные слова из небольшого набора (чтобы были повторения и коллизии). Для проверки влияния порядка подготовьте два варианта одного и того же набора:
|
||
|
||
`records_shuffled` — случайный порядок.
|
||
|
||
`records_sorted` — отсортированный по имени (по алфавиту).
|
||
|
||
#### 2. Инструменты замера времени
|
||
Используйте модуль **time**:
|
||
|
||
```python
|
||
import time
|
||
|
||
start = time.perf_counter()
|
||
# ... операции ...
|
||
end = time.perf_counter()
|
||
elapsed = end - start # время в секундах
|
||
```
|
||
|
||
Для многократных замеров удобен `timeit`, но в этой задаче достаточно просто обернуть код в цикл и усреднить.
|
||
|
||
#### 3. Проведение замеров
|
||
Для каждой структуры данных и для каждого режима входных данных (случайный / отсортированный) выполните:
|
||
|
||
- А. Вставка всех записей
|
||
|
||
Создайте пустую структуру.
|
||
|
||
Засеките время, выполните insert для каждой записи из входного списка.
|
||
|
||
Зафиксируйте общее время вставки.
|
||
|
||
- Б. Поиск 100 случайных записей
|
||
|
||
Возьмите 100 случайных имён из того же набора (гарантированно существующих) и 10 имён, которых нет (например, "None_{i}").
|
||
|
||
Засеките время на выполнение всех 110 вызовов find.
|
||
|
||
- В. Удаление 50 случайных записей
|
||
|
||
Выберите 50 случайных имён из набора.
|
||
|
||
Засеките время на выполнение delete для каждого.
|
||
|
||
|
||
**!! Важно: после вставки структура остаётся заполненной, поиск и удаление выполняются на ней же. Если нужно повторить замер для другого порядка данных — создавайте новую структуру и заполняйте заново.**
|
||
|
||
#### 4. Сохранение результатов
|
||
|
||
**!! Каждый эксперимент повторить минимум 5 раз и записывать и среднее время, и все замеры.**
|
||
|
||
Соберите все замеры в словарь или список, затем сохраните в CSV-файл:
|
||
|
||
```python
|
||
import csv
|
||
|
||
results = [
|
||
["Структура", "Режим", "Операция", "Время (сек)"],
|
||
["LinkedList", "случайный", "вставка", 0.123],
|
||
...
|
||
]
|
||
|
||
with open("results.csv", "w", newline="") as f:
|
||
writer = csv.writer(f)
|
||
writer.writerows(results)
|
||
```
|
||
|
||
|
||
#### 5. Анализ результатов
|
||
Постройте график (столбчатая диаграмма или линейный график) — можно в Excel, Google Sheets или с помощью matplotlib в Python.
|
||
|
||
Сравните:
|
||
|
||
- Как порядок входных данных влияет на скорость вставки в BST (деградация до O(n) на отсортированных данных).
|
||
|
||
- Почему хеш-таблица почти не чувствительна к порядку.
|
||
|
||
- Почему связный список всегда медленен при поиске.
|
||
|
||
- Как удаление работает в каждой структуре.
|
||
|
||
* Вывод должен содержать ответ на вопрос: какую структуру и для каких задач (частые вставки, частый поиск, необходимость получать данные в порядке) стоит выбирать в реальной жизни.*
|