10. Общие представления о задачах

Под задачейпринято понимать необходимость сознательного поис-

ка, соответствующего (адекватного) способа и средств для дости-

жения ясно видимой, но непосредственно недоступной цели.

Постановка задачи

Для того, чтобы реализовать понятие "ясно видимой цели", нуж-

но произвести конкретизацию задачи, которую принято определять

как постановка задачи.

Цель задачи

Первый шаг на пути к результату при определении задачи - оп-

ределение ее цели:

- Что требуется, что надо определить?

Но цель невозможно достичь, если не имеется исходной информации,

следовательно следующий вопрос:

- Какова исходная информация для достижения цели? (Что дано?)

- Определить условия, при которых может быть достигнута цель.

В них включаются возможные методы, способы, средства достижения

цели, а также, если это необходимо, начальные условия и сущест-

вующие ограничения. Перечисленные условия, связанные в единую

систему, являются постановкой задачи.

Вспомогательная задача

В тех случаях, когда поставленная задача непосредственно ("в

лоб") не решается, целесообразно обратиться к некоторой вспомо-

гательной задаче. Под вспомогательной задачей понимают аналогич-

ную, близкую к исходной, но более легкую задачу. Обычно берут

такую, которая уже имеет решение или ее решение более доступно,

опираясь на результат которой, можно решить основную задачу.

Пойа сказал: "Вспомогательная задача - это средство для дос-

тижения поставленной цели - решения основной задачи".

Эквивалентные задачи

Две задачи называются эквивалентными, если решение одной из

них вытекает из решения другой.

Прерход от одной задаче к другой, эквивалентной исходной, на-

зывается двусторонней редукцией.

Пример:

| x-y = 4 | -x+y =- 4

A | x+y+z= 5 B | 2(x+y)= 36

| x+y-z=31 | 2z=-26

переход от системы A к системе B осуществляется следующим об-

разом:

-1a=1b

2a+3a=2b

2a-3a=3b,

где 1a, 2a, 3a - уравнения системы A, а 1b, 2b, 3b - уравне-

ния системы B.

Классификация задач

Классификация задач необходима для того, чтобы идентифициро-

вать поставленную задачу.

.

. Рис. 3

.

Классификаци предполагает разбиение задач таким образом, что

выделенные класы (типы) предопределяют методы решения такой за-

дачи. Более широкая классификация проводит разбиение на 2 базо-

вых вида (Пойа):

1) задачи на нахождение;

2) задачи на доказательство.

1. Задачи на нахождение.

Цель - определение (отыскание, построение, получение проведе-

ние, отождествление) некоторого объекта или определение неизвес-

тного данной задачи, удовлетворяющего условию, связывающему не-

известные с данными этой задачи.

R=F:{(Z|C) --> (R|I)}.

2. Задачи на доказательство.

Конечной целью задач на доказательство является установление

правильности или ложности некоторого утверждения или его опро-

вержение.

Строго решаемые задачи

При реализации цели Z возможно строгое решение задачи. Под

строго решаемыми задачами понимают определение одного из подмно-

жеств в формальной записи.

.

. Рис 4.

.

Решаемая задача. Решаемой или задачей, имеющей решение назы-

вают такую задачу, для которой элементы системы кортежей (1) со-

вместимы.

Определенная задача - это решающая задача, в которой три эле-

мента кортежа (M, A, P) заданы точно.

Неопределенная задача - это задача, в которой M, A, P, и

может быть частично I, либо полностью неопределены, либо частич-

но.

В зависимости от возможных комбинаций элементов кортежей, не-

определенные задачи различают, как информационные.

Цель информационных задач - получить ответ на вопрос:

- Что истинно?

Организационные задачи. Целью организационных задач является

получение решения с ответом на вопрос - "Каким быть?".

Оперативные задачи. Решение оперативной задачи должно отве-

чать на вопрос: "Как действовать?".

Классификация задач по признаку связности

Задачи можно разбить на подзадачи:

1. Конгломерат.

2. Аддитивный.

3. Эмерджентный.

4. Монолит.

Для задач можно выделить:

1. Несвязанные задачи (конгломерат).

2. Слабосвязанные задачи.

3. Сильносвязанные задачи (монолит).

1. Сильносвязанные задачи.

Выход не связан со входом.

.

. Рис 5. Конгломерат: Несвязанные задачи.

.

2. Слабосвязанные задачи.

Разбиение исходной, целостной задачи на подзадачи осуществ-

ляется таким образом, что информационный обмен между подзадача-

ми имеет низкую интенсивность.

Pij --> N операций.

Iе --> Объем информации.

Количество операций на информационный обмен много меньше чем

количество операций, приводящих к решению данной задачи:

I