Визуализация алгоритма поиска подстроки. Отчет по учебной, ознакомительной практике

1. МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение

высшего образования
«Кузбасский государственный технический университет им. Т.Ф. Горбачева»
Институт информационных технологий, машиностроения и автотранспорта
Кафедра прикладных информационных технологий
Отчет
по учебной, ознакомительной практике
Визуализация алгоритма поиска подстроки.
Алгоритм Кнута-Морриса-Пратта (KMP)
Выполнили: студент гр. ПИб-231
Базаев Егор Николаевич
Руководитель практики:
Глебова Екатерина Андреевна,
ст. преподаватель
Кемерово 2025

2. Технические требования

1. Языки программирования: JavaScript (Frontend),
Python (Backend).
2. Разработка пользовательского интерфейса (UI):
HTML5, CSS.
3. Сторонние вспомогательные библиотеки.
4. Возможность работы в браузере.
2

3. Аппаратные средства вычислительной техники

Рабочий ноутбук-сервер:
1. Процессор: 6 ядерный, 12 поточный AMD Ryzen 5 6600H with Radeon
Graphics
2. Память: 16 (8*2) ГБ DDR5, 4800 МГц
3. Чипсет: AMD K19.4 IMC
4. Шины системной платы (PCI, PCI-E и т. д.): отсутствуют
5. Интерфейсы: USB 2.0 Type A, USB 3.1 Type A, USB 3.1 Type-С, выход
HDM
6. Накопители на магнитооптических дисках: отсутствуют
7. Магнитные и твердотельные накопители: 1 ТБ NVMe накопитель ADATA
XPG S11 Pro
8. Видеокарта: NVIDIA GeForce RTX 3050 Laptop GPU
9. Доп. оборудование: отсутствует
3

4. Системное программное обеспечение

1.Операционная система: Microsoft Windows 10
Корпоративная 2021 LTSC. Версия 21H1
4

5. Прикладное программное обеспечение

1.Редактор исходного кода Microsoft Visual
Studio Code
2.Компилятор Python версии выше 3.6
3.Фреймворки Python:
1.flask==3.1.1
2.flask-core==2.9.0
4.Командная строка Windows
5

6. Задачи и цели учебной, ознакомительной практики

1. Ознакомится с алгоритмом поиска подстроки.
2. Визуализировать работу алгоритма КнутаМорриса-Пратта с помощью графических
элементов.
3. Реализовать пользовательский интерфейс,
позволяющий пользователю: вводить строку и
подстроку, запускать поиск и видеть анимацию.
4. Обеспечить возможность пошагового выполнения
алгоритма, чтобы пользователь мог видеть, как
алгоритм работает на каждом этапе.
6

7. UML-модель алгоритма

7

8. Код программы

def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i=1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
8

9. Пример работы алгоритма

10. Выводы

В результате прохождения практики были получены навыки работы с такими языками
программирования как: Python, JavaScript, языком разметки HTML5, языком стилей CSS и
фреймворками Flask для языка Python. Были закреплены навыки написания кода, интеграции
библиотек Python, веб-разработки, верстки и отладки.
Учебно-ознакомительная практика дала мне полезный опыт, который позволил мне глубже
взглянуть на процесс разработки и реализации веб-приложений и алгоритмов.
10