матлаб 3 работы

Лабораторная работа №1

Тема: «Алгоритмы поиска подстрок»

1.    В системе MATLAB разработать и отладить три алгоритма поиска подстроки в строке: наивный алгоритм, алгоритм Рабина - Карпа и алгоритм Кнута – Морриса – Пратта.

2.    Разработать вычислительные эксперименты по сравнению производительности различных алгоритмов поиска.

3.    Построить графики зависимости времени работы каждого алгоритма от размеров входных данных

Лабораторная работа №2

Тема: «Динамическое программирование»

1.    Описать ситуации, в которых применяется метод ДП (в отчёте)

2.    Разработать алгоритм нахождения максимальной общей подпоследовательности для двух последовательностей.

3.    Разработать алгоритм вычисления расстояния редактирования между двумя строками символов

4.    Разработать алгоритм решения задачи о рюкзаке для двух случаев:

      А) Каждый предмет имеется в неограниченном количестве

      Б) Имеется только по одному предмету каждого типа.

Лабораторная работа №3

Тема: «Вычислительная геометрия»

1.  Разработать алгоритм сложности для определения наличия пересечений в системе отрезков на плоскости

2.  Разработать алгоритм сложности  для нахождения множества максимальных (минимальных) элементов для множества точек на плоскости

3.  Разработать алгоритм сложности  для построения выпуклой оболочки множества точек на плоскости