Практическое занятие № 23 Массовая и индивидуальная задача

Тема программы: Задачи и алгоритмы

Цели работы:

1) Обобщить теоретические знания по теме «Задачи и алгоритмы».

2) Рассмотреть алгоритмы решений заданий теме «Задачи и алгоритмы», решить задачи в ОС МЕГАПЛАН.

3) Формировать тактичность; терпимость; умение доказать свою точку зрения при работе в коллективе.

Время выполнения: 2 часа.

Теоретические основы

Массовая задача

Под массовой задачей (или просто задачей) будем понимать некоторый
общий вопрос, на который следует дать ответ:

- Есть ли в задаче гамильтонов цикл?

- Существует ли в графе клика мощности не менее K?

Задача задается следующей информацией:

1) списком всех ее параметров;

2) формулировкой свойств, которым должен удовлетворять ответ

Индивидуальная задача получается из массовой присвоением конкретных значений всем параметрам.

Алгоритмы

Под алгоритмом будем понимать общую, выполняемую шаг за шагом процедуру решения задачи. Для определенности можно считать ее программой на Си или другом языке.

Будем выделять

· точные алгоритмы, которые для любой индивидуальной задачи всегда дают точное решение;

· приближенные алгоритмы с гарантированной оценкой точности;

· аппроксимационные схемы — семейство алгоритмов, позволяющих получать решения с любой наперед заданной точностью e > 0, время работы которых растет с ростом величины 1/ e;

· итерационные методы локального поиска (метаэвритстики), для которых вероятность получить точное решение растет с ростом числа итераций;

· быстрые конструктивные эвристики без гарантии получить точное решение или решение с заданной погрешностью.

Не нашли, что искали? Воспользуйтесь поиском: