Прикладные алгоритмы на языке ООП C# [С. Е. Иванов] (pdf) читать онлайн

54

С.Е. Иванов
ПРИКЛАДНЫЕ АЛГОРИТМЫ НА ЯЗЫКЕ
ООП C#

Санкт-Петербург
2022

1

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
УНИВЕРСИТЕТ ИТМО

С.Е. Иванов
ПРИКЛАДНЫЕ АЛГОРИТМЫ НА ЯЗЫКЕ
ООП C#
УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
РЕКОМЕНДОВАНО К ИСПОЛЬЗОВАНИЮ В УНИВЕРСИТЕТЕ ИТМО
по направлению подготовки 09.03.03 Прикладная информатика
в качестве Учебно-методическое пособие для реализации основных
профессиональных образовательных программ высшего образования
бакалавриата

Санкт-Петербург
2022

2

Иванов С.Е., Прикладные алгоритмы на языке ООП C#– СПб:
Университет ИТМО, 2022. – 52 с.
Рецензент(ы):
Мельников Виталий Геннадьевич, доктор технических наук, профессор,
Федеральное государственное бюджетное образовательное учреждение высшего
образования «Санкт-Петербургский горный университет»;
Пособие включает лабораторные работы, выполняемые в рамках курса
«Объектно-ориентированное программирование». Представлено описание,
блок-схемы и реализация различных прикладных алгоритмов на языке ООП C#.
Пособие предназначено для бакалавров по направлению подготовки 09.03.03
Прикладная информатика по программе «Мобильные и сетевые технологии» и
содержит материалы лабораторных работ по дисциплине «Объектноориентированное программирование».

Университет ИТМО – ведущий вуз России в области информационных и
фотонных технологий, один из немногих российских вузов, получивших в 2009
году статус национального исследовательского университета. С 2013 года
Университет ИТМО – участник программы повышения конкурентоспособности
российских университетов среди ведущих мировых научно-образовательных
центров, известной как проект «5 в 100». Цель Университета ИТМО –
становление
исследовательского
университета
мирового
уровня,
предпринимательского по типу, ориентированного на интернационализацию
всех направлений деятельности.
© Университет ИТМО, 2022
© Иванов С.Е., 2022

3

Содержание

Введение................................................................................................................... 4
Лабораторная работа №1. Алгоритмы хеширования .......................................... 6
Лабораторная работа №2. Алгоритм генетический .......................................... 10
Лабораторная работа №3. Алгоритмы с бинарными деревьями ..................... 16
Лабораторная работа №4. Алгоритмы на графах .............................................. 24
Лабораторная работа №5. Алгоритм метода «разделяй и властвуй» .............. 37
Лабораторная работа №6. Алгоритмы сортировки ........................................... 40
Лабораторная работа №7. Алгоритмы поиска ................................................... 45
Лабораторная работа №8. Анализ сложности алгоритмов ............................... 48
Литература ............................................................................................................. 50

4

Введение
В методическом пособии представлены задачи для реализации средствами
ООП C# различных прикладных алгоритмов, таких как алгоритм хеширования,
генетический алгоритм, алгоритмы обхода деревьев, поисковые алгоритмы на
графах, нахождения кратчайших путей и минимального остова на графах, метод
«разделяй и властвуй», алгоритмы сортировки и поиска. Также рассмотрена задача
оценки сложности алгоритмов. При выполнении работ обучающийся приобретает
соответствующие компетенции для понимания схем работы алгоритмов, навыки
программирования и умения реализовывать алгоритмы средствами ООП.
В предлагаемом пособии представлены лабораторные работы, выполняемые
в рамках курса «Объектно-ориентированное программирование» для
профессиональных
образовательных
программ
высшего
образования
бакалавриата по направлению подготовки 09.03.03 Прикладная информатика.
Перед выполнением лабораторных работ обучающемуся необходимо
изучить теоретический материал по рассматриваемому курсу.
Пособие содержит восемь лабораторных работ, включающих постановку
задачи, состав отчета по работе, пример реализации алгоритма посредством ООП
C# и контрольные вопросы. Также при выполнении лабораторной работы восемь
обучающийся приобретает навыки оценки сложности алгоритмов.
После выполнения работы обучающийся предоставляет отчет, который
защищает в семестре. В ходе защиты обучающийся поясняет свой отчет и отвечает
на вопросы преподавателя. В конце пособия представлен список рекомендуемой
литературы по рассмотренным темам.
Методические рекомендации для выполнения представленных в пособии
лабораторных работ:
1. Ознакомиться с алгоритмом метода.
2. Разработать схему работы алгоритма.
3. Реализовать алгоритм средствами ООП C#.
4. Выполнить расчет примера с помощью разработанной программы.
5. Проверить результаты работы программы на примерах.
Шаблон отчета по лабораторной работе №____
«__________________________________»
(название лабораторной работы)
1.
2.
3.
4.

Цель и задачи лабораторной работы:
Задание на лабораторную работу:
Результаты лабораторной работы:
Выводы:

5

Отчет по лабораторной работе представляется в электронном виде в
формате, предусмотренном шаблоном отчета по лабораторной работе. Защита
отчета проходит в форме доклада обучающегося с демонстрацией результатов и
ответов на вопросы преподавателя.
Если оформление отчета и доклад обучающегося во время защиты
соответствуют указанным требованиям, обучающийся получает максимальное
количество баллов.
Основаниями для снижения количества баллов являются:
 небрежное выполнение,
 низкое качество оформления,
 замечания при ответе на контрольные вопросы преподавателя.
Отчет не может быть принят и подлежит доработке в случае:
 отсутствия необходимых разделов,
 отсутствия результатов выполнения.
При выполнении работ обучающийся закрепляет теоретические знания и
получает практические навыки по реализации алгоритмов.
В результате выполнения работ обучающийся приобретает:
Знания: принципов построения алгоритмов; основных этапов решения
задачи на компьютере; основ языка программирования высокого уровня С#;
технологий работы с информационными системами, техническими средствами
хранения информации, ее кодирование; типовых структур данных и способов их
записи средствами языка высокого уровня.
Умения: принимать участие в разработке задания на программный продукт;
выбирать способ представления данных, определять спецификации на отдельные
классы, модули и подпрограммы; по математическому описанию задачи
разрабатывать алгоритм работы программы; выбирать способ организации
программы, на языке высокого уровня.
Навыки: выбирать язык программирования высокого уровня для реализации
поставленной задачи; анализировать и алгоритмизировать задачи в различных
областях знаний; выбирать технологии разработки для решения поставленных
задач; выбирать способ представления данных и алгоритм решения задачи.
Для самостоятельной работы обучающимся рекомендуется предоставить в
соответствии с планом СРО 91.2 часа в семестре на подготовку и выполнение
лабораторных работ.

6

Лабораторная работа №1. Алгоритмы хеширования
ЦЕЛЬ РАБОТЫ
Изучить алгоритмы хеширования, реализовать алгоритм Рабина-Карпа
поиска подстроки в строке с применением хеширования.
ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Алгоритмы хеширования применяют хеш-функцию для преобразования
входных данных в выходную битовую строку заданной длины. В результате
преобразования получается хеш или хеш-код. Хеш-функции применяют для
поиска дублирующих данных, вычисления контрольных сумм, создания
уникальных идентификаторов, хранения паролей, для электронной подписи и
многих других задачах. В соответствии с правилом Дирихле нет строгого
однозначного соответствия между хешем и исходными данными, поэтому
возникают коллизии. Любая хорошая хеш-функция должна быстро выполняться и
иметь минимальное число коллизий. Для разрешения коллизий разработаны
различные методы: цепочек, метод открытой адресации. Хеширование
применяется в алгоритме поиска подстроки в тексте, разработанном Майклом
Рабином и Ричардом Карпом. Алгоритм Рабина-Карпа применяют для поиска
плагиата и совпадений шаблонов одинаковой длины. Этот алгоритм основывается
на хешировании строк. Дана строка S и текст T, состоящие из маленьких латинских
букв. Требуется найти все вхождения строки S в текст T.
Алгоритм состоит из следующих шагов. Посчитаем хеш для строки S. Посчитаем
значения хешей для всех префиксов строки T. Далее переберём все подстроки T
длины |S| и каждую сравним с |S|.
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
1.Реализовать поиск одинаковых строк.
Дан список строк S[1..n], каждая длиной не более m символов. Требуется найти все
повторяющиеся строки и разделить их на группы, чтобы в каждой группе были
только одинаковые строки.
2. Реализовать алгоритм Рабина-Карпа поиска подстроки в строке за O (n).
ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ
Этапы работы:

7

1. Реализовать поиск одинаковых строк
Дан список строк S[1..N], каждая длиной не более M символов. Необходимо найти
все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были
только одинаковые строки.
Ниже представлен листинг для считывания строк

Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0p +
p2s1 + p3s2 +… + pnsn-1, где p - некоторое натуральное число, а si - код i-ого
символа строки s (он записывается s[i]).
Ниже представлен листинг для вычисления степеней p:

Ниже представлен листинг для вычисления хешей строк:

Ниже представлен листинг для сортировки по хешам и вывод ответа:

8

Ниже представлен вывод результатов: хеши и список групп:

2. Реализовать алгоритм Рабина-Карпа поиска подстроки в строке за O(N).
Дана строка S и текст T, состоящие из маленьких латинских букв.
Требуется найти все вхождения строки S в текст T за время O (|S| + |T|).
Сначала так же считаем степени P. Затем хеши подстрок текста и хеш строки.
Ниже представлен листинг для вычисления степеней и хешей:

9

Используя формулу hash(s0..R) = hash(s0..L-1) + pLhash(sL..R), найдем индексы, где в
тексте появляется нужная строка.
Ниже представлен листинг для вывода ответа:

Ниже представлены результаты поиска строки в тексте:

Выводы:
В ходе выполнения работы изучены и реализованы средствами ООП C# алгоритмы
хеширования.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Какие задачи решаются с помощью алгоритма хеширования?
2. Как решается проблема коллизий при хешировании?

10

3. Какие ограничения и условия на применение алгоритма хеширования?
4. Какие конструкции ООП C# применяются для реализации алгоритма
хеширования?
5. Как оценивается сложность алгоритма хеширования?
6. Как можно оценить точность алгоритма хеширования?
Лабораторная работа №2. Алгоритм генетический
ЦЕЛЬ РАБОТЫ
Изучить генетический алгоритм и реализовать алгоритм средствами ООП для
решения Диофантова уравнения.
ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Генетический алгоритм аналогичен процессу естественного отбора в
природе и широко применяется в оптимизационных задачах.
Ниже представлена блок схема генетического алгоритма.

Рисунок 1 – Блок-схема генетического алгоритма

11

В алгоритме важную роль играют операторы кроссинговера, наследования,
мутаций и селекции, которые подбираются под определенную задачу. Решение
задачи кодируется вектором генов или генотипом. В алгоритме оценивается
множество решений (поколение) посредством функции приспособленности или
целевой функции в задаче оптимизации. Алгоритм итерационно повторяется до
выполнения критерия остановки – нахождения оптимума, прохождения числа
поколений или времени.
Алгоритм
состоит
из
следующих
шагов:
задания
функции
приспособленности, генерации начального множества решений, в цикле пока
критерий остановки не выполнен выполняются операторы кроссинговера,
наследования, мутаций, селекции, для сознания нового множества решений.
Алгоритм широко применяется для задач оптимизации.
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
Реализовать средствами ООП генетический алгоритм для решения задачи:
найти решение Диофантова (только целые решения) уравнения: a+2b+3c+4d=30,
где a, b, c и d - некоторые положительные целые.
ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ
В данном случае посредством генетического алгоритма реализуется решение
Диофантова уравнения. Дано уравнение с целыми коэффициентами, определить
целое решение.
Диофантово уравнение имеет вид:
D(a, b, c, d) = a + 2b + 3c + 4d = 30,
где a, b, c и d – некоторые положительные целые.
Должно выполняться условие 1