Методы решения задач реферат

Обновлено: 05.07.2024

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

Решается задача минимизации функции j(x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности k>. Â качестве начального приближения выбирается любая точка x₀ÎE_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

1) в точке x_k выбирают направление спуска — S_k;

Направление S_k выбирают таким образом, чтобы обеспечить неравенство j(x_k+1) 0.

В случае, если =0, полагают x_k+1=x_k и переходят к следующей итерации.

Нужна помощь в написании реферата?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x₀ выбирают S₀=±e, и определяет величину b₀ способом удвоения так, чтобы было j(x₁)=j(x₀-b₀S₀) 2 +y 2 -xy-3y c точностью e, используя описанные выше методы.

Нахождение минимума моей функции с помощью метода покоординатного спуска.

Для получения результата программой было выполнено 24 итерации.

Нужна помощь в написании реферата?

Нахождение минимума с помощью метода градиентного спуска.

Программа, использованная мной для выполнения этой задачи представлена ниже.

Поскольку входные параметры этой программы совпадают со входными параметрами задачи №1, то я взял их такие же, что и для первой задачи, чтобы, сравнив полученные результаты и количество итераций, необходимых для поиска минимума, я смог сделать какие-либо выводы о преимуществах и недостатках обеих задач из практики.

Итак, взяв те же начальные условия я получил следующие результаты:

Количество итераций, которое потребовалось для нахождения точки минимума равно 20. Видно, что количество итераций, потребовавшееся первой программе больше, чем количество итераций, необходимых второй программе. Это следует из того, что антиградиент указывает направление наискорейшего убывания функции.

Нужна помощь в написании реферата?

Ниже также представлен график сходимости вышеописанного процесса для моей функции и моих начальных условий.

Необходимо также добавить несколько важных моментов. Во-первых, из того, что количество итераций, потребовавшееся для нахождения минимума в первой задаче больше, чем во второй не следует тот факт, что вторая программа работает быстрее, чем первая, поскольку для второй задачи необходимо вычислять не только значение функции в какой-либо точке, но и её производной в этой точке, которая может быть более громоздка, чем сама функция.

Наконец, второй метод плох ещё и потому, что для произвольной функции производную вычислить невозможно; придётся сначала аппроксимировать её, а затем искать минимум (за счёт аппроксимации значительно вырастает время и погрешность измерений).

Основная задача современного учителя математики не создание у учащихся механического применения полученных навыков, а умения их применения в нестандартных ситуациях. Поэтому в данной работе попытаемся проследить процесс обучения методам решения задач в школьном курсе математики, рассмотреть структуру обучения их решению в школьных учебниках, а также выделить преимущества и недостатки при обучении решению задач конкретным методом. Также необходимо выделить основные составные части задачи в школьном курсе, и на что, при обучении их решению, следует обратить внимание. Вообще чтобы научиться решать задачи надо их решать, причем решать различные задачи и по-разному (то есть разными способами), анализировать решения, сравнивать, находить преимущества и недостатки в каждом конкретном случае.

В том или ином виде в школе встречаются следующие методы решения задач:

- анализ и синтез

- метод сведения к ранее решённым

- метод математической индукции

- метод исчерпывающих проб

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

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

При обучении математике задачи имеют большое и многостороннее значение. Образовательное значение математических задач. Решая математическую задачу, человек познает много нового: знакомится с новой ситуацией, описанной в задаче, с применением математической теории к ее решению, познает новый метод решения или новые теоретические разделы математики, необходимые для решения задачи, и т. д. Иными словами, при решении математических задач человек приобретает математические знания, повышает свое математическое образование. При овладении методом решения некоторого класса задач у человека формируется умение решать такие задачи, а при достаточной тренировке - и навык, что тоже повышает уровень математического образования.

1.2 Составные части задачи и этапы её решения в школьном курсе.

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

Если прочитать условие любой задачи то можно выделить некий вопрос, другими словами требование, на который необходимо получить ответ, опираясь на условие. Если же внимательно изучить формулировку задачи то можно увидеть в ней определенные утверждения (то, что дано), они ещё называются условиями, и определенные требования (то, что нужно найти).

Далее рассмотрим составные части задачи и рекомендации к учащимся при их решении.

1) Вопросы и советы для усвоения содержания задачи (1-й этап-анализ условия). Нельзя приступать к решению задачи, не уяснив четко, в чем заключается задание, т. е. не установив, каковы данные и искомые или посылки и заключения. Первый совет учителя: не спешить начинать решать задачу. Этот совет не означает, что задачу надо решать как можно медленней. Он означает, что решению задачи должна предшествовать подготовка, заключающаяся в следующем:

а) сначала следует ознакомиться с задачей, внимательно прочитав ее содержание. При этом схватывается общая ситуация, описанная в задаче;

б) ознакомившись с задачей, необходимо вникнуть в ее содержание. При этом нужно следовать такому совету: выделить в задаче данные и искомые, а в задаче на доказательство -посылки и заключения.

в) Если задача геометрическая или связана с геометрическими фигурами, полезно сделать чертеж к задаче и обозначить на чертеже данные и искомые (это тоже совет, которому должен следовать ученик).

г) В том случае, когда данные (или искомые) в задаче не обозначены, надо ввести подходящие обозначения. При решении текстовых задач алгебры и начал анализа вводят обозначения искомых или других переменных, принятых за искомые.

д) Уже на первой стадии решения задачи, стадии анализа задания, рекомендуют ответить на вопрос: "Возможно ли решить задачу при таком условии?" Не всегда сразу удается ответить на этот вопрос, но иногда это можно сделать.

Отвечая на этот вопрос, полезно выяснить, однозначно ли сформулирована задача, не содержит ли она избыточных или противоречивых данных. При этом выясняют, достаточно ли данных для решения задачи.

2) Составление плана решения задачи (2-й этап – поиск пути решения). Составление плана решения задачи, пожалуй, является главным шагом на пути ее решения. Правильно составленный план решения задачи почти гарантирует правильное ее решение. Но составление плана может оказаться сложным и длительным процессом. Поэтому крайне необходимо предлагать ученику ненавязчивые вопросы, советы, помогающие ему лучше и быстрее составить план решения задачи, фактически определить метод её решения:

а) Известна ли решающему какая-либо подобная задача? Аналогичная задача? Если такая задача известна, то составление плана решения задачи не будет затруднительным. Другими словами можно ли применить метод сведения к ранее решенным. Но такая задача известна далеко не всегда . В этом случае может помочь в составлении плана решения совет.

б) Подумайте, известна ли вам задача, к которой можно свести решаемую. Если такая задача известна решающему, то путь составления плана решения данной задачи очевиден: свести решаемую задачу к решенной ранее. Может оказаться, что родственная задача неизвестна решающему и он не может свести данную задачу к какой-либо известной. План же сразу составить не удается.

В литературе советуют воспользоваться советом: "Попытайтесь сформулировать задачу иначе". Иными словами, попытайтесь перефразировать задачу, не меняя ее математического содержания.

При переформулировании задачи пользуются либо определениями данных в ней математических понятий (заменяют термины их определениями), либо их признаками (точнее сказать, достаточными условиями). Надо отметить, что способность учащегося переформулировать текст задачи является показателем понимания математического содержания задачи.

Некоторые авторы относят к переформулировке задачи и перевод ее на язык математики, т. е. язык алгебры, геометрии или анализа. Это, скорее, формализация задачи, "математизация" ее. К такому приему и приходится часто прибегать при решении многих текстовых задач.

г) Составляя план решения задачи, всегда следует задавать себе (или решающему задачу ученику) вопрос: "Все ли данные задачи использованы?" Выявление неучтенных данных задачи облегчает составление плана ее решения.

д) При составлении плана задачи иногда бывает полезно следовать совету: "Попытайтесь преобразовать искомые или данные". Часто преобразование искомых или данных способствует более быстрому составлению плана решения. При этом искомые преобразуют так, чтобы они приблизились к данным, а данные - так, чтобы они приблизились к искомым. Так, при каждом случае тождественных преобразований данные преобразуются, постепенно приближаясь к результату (искомому). Аналогично уравнение, систему уравнений, неравенство или систему неравенств преобразуют в равносильные, чтобы найти их корни или множество решений.

е) Нередко случается так, что, следуя указанным выше советам, решающий задачу все же не может составить план ее решения. Тогда может помочь еще один совет: "Попробуйте решить лишь часть задачи", т. е. попробуйте сначала удовлетворить лишь части условий, с тем чтобы далее искать способ удовлетворить оставшимся условиям задачи. Другими словами: может ли задача с помощью анализа быть разбита на части, а затем решения этих задач синтетическим путем объединяются в единое целое.

ж) Рекомендуют также в составлении плана решения задачи ответить на вопрос: "Для какого частного случая возможно достаточно быстро решить эту задачу?" Обнаружив такой частный случай, решающий ставит перед собой новую цель - воспользоваться решением задачи в найденном частном случае для более общего (но, может быть, не самого общего) случая.

3) Реализация плана решения задачи (3-й этап – непосредственно решение). План указывает лишь общий контур решения задачи. При реализации плана решающий задачу рассматривает все детали, которые вписываются в этот контур. Эти детали надо рассматривать тщательно и терпеливо. Но при этом ученику (решающему задачу) полезно следовать некоторым советам:

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

б) При реализации плана поможет и совет: "Замените термины и символы их определениями". Так, термин "параллелограмм" заменяется его определением: "Четырехугольник, у которого противоположные стороны попарно параллельны", термин "предел числовой последовательности" для доказательства, например, того предложения, что предел суммы двух последовательностей, имеющих пределы, равен сумме пределов этих последовательностей, можно заменить, и вполне успешно, его определением.

4) Анализ и проверка правильности решения задачи (4-й этап – проверка и исследование задачи). Даже очень хорошие ученики, получив ответ и тщательно изложив ход решения, считают задачу решенной. А ведь получение результата не означает еще, что задача решена правильно. Тем более не означает, что для решения выбран лучший, наиболее удачный, изящный, если можно так выразиться, вариант. По В. М. Брадису, задачу можно считать решенной, если найденное решение: 1) безошибочно, 2) обоснованно, 3) имеет исчерпывающий характер. Поэтому анализ решения задачи, проверка решения и достоверности результата должны быть этапом решения задачи. Итак, два совета: "Проверьте результат", "Проверьте ход решения". Проверка результата может производиться различными способами. Проверяя правильность хода решения, мы тем самым убеждаемся и в правильности результата.

Второй способ проверки результата заключается в получении того же результата применением другого метода решения задачи, поэтому полезно всегда задавать решающему вопрос: "Нельзя ли тот же результат получить иначе?" Иными словами, стоит последовать совету: "Решите задачу другим способом". Если при решении задачи другим способом получен тот же результат, что и в первом случае, задачу можно считать решенной правильно. Далее можно рассмотреть какой из использованных методов удобнее в данном случае. К тому же получение различных вариантов решения одной и той же задачи имеет важное обучающее значение.

2.1(а) Аналитико – синтетический метод.

Анализ – логический приём, метод исследования, состоящий в том, что изучаемый объект мысленно (или практически) разбивается на составные элементы (признаки, свойства, отношения), каждый из которых исследуется в отдельности как часть расчлененного целого.

Синтез – логический прием, с помощью которого отдельные элементы соединяются в единое целое (другими словами обратный анализу).

Не следует отделять эти методы друг от друга, так как они составляют единый аналитико-синтетический метод . Так при решении сложной задачи она с помощью синтеза разбивается на ряд более простых задач, а затем при помощи синтеза происходит соединение решений этих задач в единое целое.

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

Обучение данным методам важно ещё и потому что они выступают и как особые формы мышления.

При обучении анализу или синтезу следует тщательно подбирать задания, поскольку в каждом из них необходимо обоснование конкретного метода. Так при решении неравенств, как правило, используется аналитический метод, в этом случае использование синтеза затруднено.

Пример: (использование анализа при решении иррациональных уравнений)

1) рассмотрим левую часть: 0

4) приходим к противоречию, а значит -

5) уравнение решения не имеет.

Применение данного метода можно увидеть при решении следующих задач:

1) Анализ и синтез при решении задач на доказательство.

2) Анализ и синтез при решении текстовых задач. Текстовыми задачами здесь названы математические задачи, в которых входная информация содержит не только математические данные, но еще и некоторый сюжет (фабулу задачи).

При решении текстовых задач с помощью аппарата арифметики роль анализа сводится к составлению плана решения, задача же чаще всего решается синтетическим методом.

Пример: Два самолета с реактивными двигателями одновременно вылетели с двух аэродромов навстречу друг другу. Расстояние между аэродромами 1870км. Через сколько часов они встретятся, если один из них в 2/5 часа пролетает 360км, а скорость второго составляет 8/9 скорости первого.

Главная трудность при решении данной задачи это составление плана её решения разбиение условия на отдельные этапы. Для этого нужен глубокий анализ условия. Само решение отдельных задач трудности уже не вызывает но бывает трудно свести решения этих задач к ответу на основной вопрос задачи.

1.Какова скорость первого самолета?

2.Какова скорость второго самолета?

3.На сколько самолеты сближаются в течение часа?

4.Через сколько часов после вылета самолеты встретятся?

1870:1700 = 1.1 часа

3) Анализ и синтез при решении задач на построение в геометрии. Анализ и синтез применяются и при решении задач на построение в геометрии, иначе, конструктивных задач геометрии. Как известно, решение этих задач выполняется по следующему плану: анализ, построение, доказательство, исследование. Название первой части - анализ говорит само за себя: это действительно метод анализа, ведущий от искомых ("предположим, что искомая фигура построена") к данным, точнее, к их использованию в построении. При анализе намечается план построения, которое выполняется синтетическим путем. При доказательстве возможно использование, как анализа, так и синтеза, но чаще применяется последний метод. Исследование предполагает преимущественное применение метода анализа.

2.2(б) Метод сведения к ранее решенным.

Суть обучения данному методу заключается в обучении школьников увидеть в данной задаче ранее решенную и сведению решаемой задачи с помощью последовательных преобразований к ней.

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

Аналогично поступают и при решении различного вида уравнений, неравенств и систем уравнений. Особую роль этот метод играет при нахождении производной.

Пример:( из уч. Колмогорова )

Найдите производную f(x) = cos2x•sinx + sin2x•cosx

cos2x•sinx + sin2x•cosx = sin(2x+x) по формуле сложения

f(x) = sin(2x+x) => f(x) = sin3x

Из полученного равенства найти производную не составляет особого труда.

А ещё раньше использование этого метода можно увидеть при решении текстовых задач, когда исходная задача сводится к нескольким простым задачам. Здесь можно увидеть тесную связь метода сведения с аналитико – синтетическим методом.

В школьном курсе данный метод используется очень широко в тригонометрии (при решении уравнений и неравенств). Так в самом начале изучения данной темы учащимся предлагают заучить основные тригонометрические тождества, затем формулы сложения, приведения, суммы и разности. А в дальнейшем сначала вырабатываются умения и навыки решения простейших тригонометрических уравнений.

Пример: (из уч.Колмогорова). Найдите значение других трех основных тригонометрических функций, если sinα= - 0.8, Π 2 •МК ; V_ш =4/3π•ОК 3

По условию имеем V_K : V_ш =1/3•АК 2 •МК : 4/3π•ОК 3 . Отсюда можно перейти к следующему равенству: АК 2 •МК : 4π•ОК 3 = 2 (1)

Выразим все отрезки входящие в равенство (1) через угол МАК = х и отрезок АК=у.

Из ∆АМК находим МК = АК•tg(МАК) = y•tg(x) (2)

Из ∆АОК находим ОК = АК•tg(AOK)

Очевидно, ОА есть биссектриса угла МАК, поэтому

Подставим найденные выражения из (2),(3) в (1).

У 2 •У•tg(x) : 4•(y•tg(x)) 3 = 2 получаем tg(x) = 8•tg 3 (x/2)

Это тригонометрическое уравнение есть модель исходной задачи при условии, что 0 O О . Решив уравнение при этом условии, получим ответ задачи.

2.2 Заключение.

В этой работе были рассмотрены несколько методов решения задач и особенности каждого из них в преподавании школьного курса математики. Был произведен анализ некоторой методической и школьной литературы с точки зрения изучения общих методов решения задач в школе на уроках математики. В результате можно заключить, что в школьном курсе нет четкого разделения методов, в том смысле, что авторы школьных учебников не дают напрямую схему какого либо метода. Большинство учебников построено, так что при решении определенного рода заданий используется по сути один метод, наиболее удобный. Недостаток такого подхода состоит в том что учащийся столкнувшись с задачей подобного рода, решает её этим методом, а если ответ получить не удается, попадает в своего рода тупик.

Поэтому, решая задачи определённого типа, пусть даже наиболее удобным методом не стоит забывать о других способах её решения.

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

3.1 Список литературы.

1) Фридман Л.М. Турецкий Е.Н. Как научиться решать задачи. М. Просвещение. 1984.

2) Колягин Ю.М. Оганесян В.А. Учись решать задачи. М. Просвещение. 1980.

4) Р.С.Черкасов, А.А.Столяр Методика преподавания математики.

5) Репьев В.В. Методика преподавания математики. М. Просвещение. 1958.

* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.

МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ

Методы решения задач, основанные на сведении их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области:

объем пространства, в котором предстоит искать решение;

степень изменяемости области во времени и пространстве (статические и динамические области);

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

определенность данных о решаемой задаче, степень точности (ошибочности) и полноты (неполноты) данных.

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

количеством решений : одно решение, несколько решений, все решения.

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

Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом:

методы поиска в одном пространстве - методы, предназначенные для использования в следующих условиях: области небольшой размерности, полнота модели, точные и полные данные;

методы поиска в иерархических пространствах - методы, предназначенные для работы в областях большой размерности;

методы поиска при неточных и неполных данных ;

методы поиска, использующие несколько моделей, предназначенные для работы с областями, для адекватного описания которых одной модели недостаточно.

Предполагается, что перечисленные методам при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким параметрам.

3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ

Методы поиска решений в одном пространстве обычно делятся на:

поиск в пространстве состояний (рассмотрим подробно),

поиск методом редукции,

поиск методом "генерация-проверка".

3.1.1. Поиск в пространстве состояний

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.

Пусть задана тройка (S₀, F, S_Т), где S₀ - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, S_Т - множество конечных (целевых) состояний (решений задачи).

Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.

Процесс решения в виде графа G=(Х, Y), где X=0, х_1,. > - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (x_i, x_j), (x_i, x_j)X. Если каждая пара (x_i, x_j) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (x_i, x_j) задан порядок (направление), то пару (x_i, x_j) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (x_i, x_j) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (x_i, x_j) свидетельствует о существовании некоторого оператора f (fF), преобразующего состояние, соответствующее вершине x_i, в состояние x_j. Для некоторой вершины x_i выделяем множество всех направленных пар (x_i, x_j)Y, т.ь. множество дуг, исходящих из вершины х_i, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины x_i, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине х_i.

В множестве вершин X выделяют подмножество вершин Х₀Х, соответствующее множеству начальных состояний (S_o),, и подмножество вершин Х_тX, соответствующее множеству конечных (целевых) состояний (S_Т). Множество Х_т может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

Отметим, что граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х₀Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина х₀Х, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.

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

поиск в глубину (сначала раскрывается та вершина, которая была построена самой последней). Рис.3.1.а

поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рис.3.1.б.

Целевые вершины помечены черными квадратами, а терминальные - белыми квадратами. При использовании каждого из способов могут быть найдены все решения. При переборе всего пространства оба метода будут анализировать одинаковое количество вершин, однако метод поиска в ширину будет требовать существенно больше памяти, так как он запоминает все пути поиска (а не один, как при поиске в глубину).

3.1.2. Поиск методом редукции

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.

Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.

Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:

Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.

Вершина ИЛИ разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.

Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.

Решающий граф определяется как подграф из разрешимых вершин, который показывает, что начальная вершина разрешима (в соответствии с приведенным выше определением). На рис. 3.3. разрешимые вершины зачернены, а неразрешимые оставлены белыми.

Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. На рис. 3.4. приведен пример поиска в ширину (рис. 3.4., а) и поиска в глубину (рис. 3.4., б). На рисунке вершины пронумерованы в том порядке, в котором они раскрывались, конечные вершины обозначены квадратами, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями.

3.1.3. Эвристический поиск

При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и (или) памяти. Это привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию о предметной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят .к цели. '

3.1.4.Поиск методом "генерация-проверка"

Процесс поиска может быть сформулирован в терминах "генерация-проверка". Для осуществления процесса поиска необходимо генерировать очередное возможное решение (состояние или подзадачу) и проверить, не является ли оно результирующим.

3.2. ПОИСК В ИЕРАРХИИ ПРОСТРАНСТВ

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

Методы поиска решения в иерархических пространствах обычно делятся на:

поиск в факторизованном пространстве,

поиск в фиксированном множестве пространств

поиск в изменяющемся множестве пространств.

3.2.1. Поиск в факторизованном пространстве

Во многих приложениях требуется найти все решения. Например - постановка диагноза. Пространство называется факторизованным, если оно разбивается на непересекающиеся подпространства (классы) частичными (неполными) решениями. Причем по виду частичного решения можно определить, что оно не приведет к успеху, т.е. что все полные решения, образованные из него, не приведут к целевым решениям. Поиск в факторизованном пространстве осуществляется на основе метола "иерархическая генерация-проверка". Если пространство поиска удается факторизовать, то поиск даже в очень большом пространстве можно организовать эффективно.

3.2.2. Поиск в фиксированном множестве пространств

Применение метода факторизации пространства ограничено тем, что для ряда областей не удается по частичному решению сделать заключение о его непригодности. Например задачи планирования и конструирования. В этих случаях могут быть применены методы поиска, использующие идею абстрактного пространства. Абстракция должна подчеркнуть важные особенности рассматриваемой задачи, позволить разбить задачу на более простые подзадачи и определить последовательность подзадач (план решения), приводящую к решению основной задачи.

3.2.3. Поиск в изменяющемся множестве иерархических пространств

В ряде приложений не удается все решаемые задачи свести к фиксированному набору подзадач. План решения задачи в данном случае должен иметь переменную структуру и не может быть сведен к фиксированному набору подзадач. Для решения подобных задач может быть использован метод нисходящего уточнения. Этот метод базируется на следующих предположениях:

возможно осуществить частичное упорядочение понятий области, приемлемое для всех решаемых задач;

решения, принимаемые на верхних уровнях, нет необходимости отменять на более нижних.

3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ

Рассмотренные выше методы поиска исходят из молчаливой предпосылки, что знания о предметной области и данные о решаемой задаче являются точными и полными и для них справедливо следующее:

все утверждения, описывающие состояние, являются истинными;

применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из истинных фактов.

Однако при решении любых практических задач и особенно при решении неформализованных задач распространена обратная ситуация. Эксперту приходится работать в условиях неполноты и неточности знаний (данных) и, как правило, в условиях дефицита времени. Когда эксперт решает задачу, он использует методы, отличающиеся от формальных математических рассуждений. В этом случае эксперт делает правдоподобные предположения, которые он не может доказать; тем самым вопрос об их истинности остается открытым. Все утверждения, полученные на основе этих правдоподобных предположений, также не могут быть доказаны.

Итак, для того чтобы система могла делать умозаключения, основанные на здравом смысле, при работе с неполными (неточными) данными и знаниями, она должна быть способна делать предположения, а при получении новой информации, показывающей ошибочность предположений, отказываться как от сделанных предположений, так и от умозаключений, полученных на основе этих предположений. Мнение системы о том, какие факты имеют место, изменяется в ходе рассуждения, т.е. можно говорить о ревизии мнений. Таким образом, даже если рассматривать проблемную область как статическую, неполнота (и неточность) знаний и данных влечет за собой рассмотрение этой области при различных (и даже противоположных) предположениях, что, в свою очередь, приводит к представлению области в виде альтернативных пространств, соответствующих различным, возможно, противоречивым и (или) взаимодополняющим предположениям и мнениям.

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

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

Этот метод поиска называют поиском, направляемым зависимостью.

3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОДЕЛЕЙ

Все методы поиска, рассмотренные до сих пор, использовали при представлении проблемной области какую-то одну модель, т.е. рассматривали область с какой-то одной точки зрения. При решении сложных задач в условиях ограниченных ресурсов использование нескольких моделей может значительно повысить мощность системы. Объединение в одной системе нескольких моделей дает возможность преодолеть следующие трудности.

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

использование нескольких моделей позволяет в ряде случаев уменьшить вероятность потери хорошего решения (следствие неполного поиска, вызванного ограниченностью ресурсов) за счет конструирования полного решения из ограниченного числа частичных кандидатов путем их расширения и комбинации.

наличие нескольких моделей позволяет системе справляться с неточностью (ошибочностью) данных.

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

3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ

Выбор метода решения задачи зависит прежде всего от сложности задачи, которая определяется особенностями проблемной области и требованиями, предъявляемыми пользователем к решению задачи. Для преодоления трудностей, вызванных большим пространством поиска, используются методы, основанные на введении иерархии пространств (конкретных, абстрактных и метапространств). Простейший из этих методов основывается на факторизуемости пространства решений, что позволяет производить раннее отсечение. Метод обеспечивает получение всех решений. Если пространство поиска не удается факторизовать, но при этом не требуется получать все решения или выбирать лучшее, то могут быть применены методы, использующие иерархию однородных абстрактных пространств. Если пространство поиска таково, что любая задача может быть сведена к известной заранее последовательности подзадач, то используется фиксированное абстрактное пространство.

Эффективность этого метода определяется возможностью использовать безвозвратную стратегию. В случае, если подзадачи взаимозависимы, т.е. для решения некоторой подзадачи может требоваться информация, получаемая другой подзадачей, и подзадачи не могут быть упорядочены, целесообразно применять принцип наименьших свершений. Этот подход позволяет приостанавливать решение подзадачи, для которой недостает информации, переходить к решению другой подзадачи и возвращаться к исходной задаче, когда отсутствующая информация станет доступной. (поиск в иерархии пространстве)

Для преодоления трудностей, вызванных неполнотой и (или) неточностью данных (знаний), используют вероятностные, размытые и точные методы. Все эти методы основываются на идее увеличения надежности путем комбинирования фактов и использования метазнаний о возможностях комбинирования фактов.

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

3.2.3. Поиск в изменяющемся множестве иерархических пространств

· возможно осуществить частичное упорядочение понятий области, приемлемое для всех решаемых задач;

· решения, принимаемые на верхних уровнях, нет необходимости отменять на более нижних.

3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ

· все утверждения, описывающие состояние, являются истинными;

· применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из истинных фактов.

Этот метод поиска называют поиском, направляемым зависимостью.

3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОДЕЛЕЙ

· переход с одной модели на другую позволяет обходить тупики, возникающие при поиске в процессе распространения ограничений.

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

· наличие нескольких моделей позволяет системе справляться с неточностью (ошибочностью) данных.

3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Методы решения текстовых задач

Стандартные и нестандартные задачи……………………………………4

Теория и приведённые в примерах задачи взяты из книг таких авторов, как Соловейчик И., Фридман Л. М., Турецкий Е. Н., Потапом М. К. и др.

Задачи и их решения

Для начала узнаем, что такое задача:

Задача – это требование или вопрос, на который надо найти ответ, опираясь или учитывая те условия, которые в ней указаны.

Любая задача состоит из трёх частей : условие, объект, требование (вопрос) задачи.

Приступая к решению какой-либо задачи, надо её внимательно изучить, установить, в чем состоят её требования, каковы условия, исходя из которых надо её решать. Всё это называется анализом задачи .

Весь процесс решения задачи можно разделить на восемь этапов:

2-й этап: схематическая запись;

3-й этап: поиск способа решения;

4-й этап: осуществление решения:

5-й этап: проверка решения;

6-й этап: исследование задачи;

7-й этап: формулировка ответа;

Стандартные и нестандартные задачи

Как уже было сказано, по отношению к теории задачи делятся на стандартные и нестандартные.

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

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

Поиск решения состоит в составлении последовательности шагов решения задач этого вида.

Само решение стандартной задачи состоит в применении этой общей программы к её условиям.

Но всё-таки, чтобы правильно решать такие задачи, в первую очередь надо определить её вид.

Теперь рассмотрим нестандартные задачи. Исходя из определения стандартных задач, для них не имеется общих правил и положений.

Процесс решения любой нестандартной задачи состоит в последовательном применении двух основных операций:

Переформулировка нестандартной задачи к другой, ей эквивалентной, но уже стандартной.

Разбиение нестандартной задачи на несколько стандартных подзадач.

где P – производительность труда, т. е. часть работы, выполняемая в единицу времени;

t – время, необходимое для выполнения всей работы.

Пусть P  t =1 – взаимообратные величины, т. е. вся работа А=1, следовательно:

Решим задачу на производительность труда.

Три каменщика разной квалификации выложили кирпичную стену, причём первый каменщик работал 6 часов, второй – 4 часа, а третий – 7 часов. Если бы первый каменщик работал 4 часа, второй – 2 часа и третий – 5 часов, то было бы выполнено 2/3 всей работы. За сколько часов каменщики закончили бы кладку, если бы они работали вместе одно и то же время?

Решим эту задачу путём составления системы уравнений.

Пусть х – скорость выполнения работы первого каменщика, y – второго, z – третьего. Всю работу примем за 1. Составим систему уравнений по условию задачи (рис. 2а)

Надо найти , то есть

Умножим (2) на -2 и сложим почленно с (1). Получим (рис. 2а):

Затем умножим (2) на -1,5 и сложим почленно с (1). Получим (рис. 2б):

Следовательно, подставим в искомое выражение полученные значения для x , y , z (рис. 2в). В итоге получим 6.

Ответ: каменщики выполнят эту работу за 6 часов.

Мы решили эту задачу путём составления систем уравнений и решая их методом Гаусса.

При одновременной работе двух насосов разной мощности бассейн наполняется водой за 8 часов. После ремонта насосов производительность первого из них увеличилась в 1,2 раза., а второго – в 1,6 раза, и при одновременной работе насосов бассейн стал наполняться за 6 часов. За какое время наполнится бассейн при работе только первого насоса после ремонта?

Пусть объём бассейна равен 1, тогда время его заполнения до ремонта первым насосом – x , а вторым – y часов. Следовательно, - производительность первого насоса до ремонта, а - производительность второго насоса до ремонта. Зная, что бассейн до ремонта насосов заполняется за 8 часов, то составим первое уравнение (рис.3а).

- производительность первого насоса до ремонта, а - производительность второго насоса после ремонта. Зная, что бассейн после ремонта насосов заполняется за 6 часов, то составим второе уравнении (рис. 3б).

Решив оба уравнения можно составить систему:

Умножим (1) на 0,9 и вычтем из него (2) (рис. 3в).

В итоге получим y =24, x =12.

Из найденных значений для x и y вычислим производительность первого насоса после ремонта:

По формуле найдём время наполнения бассейна при работе только первого насоса после ремонта: ч.

Вывод: в результате решения задач двух разных видов мы выяснили, что все задачи на работу решаются по одной общей формуле (А= P  t ) и в большинстве случаев решаются путём составления систем уравнений.

Известно, что вклад, находящийся в банке, с начала года возрастает к концу года на определённый процент (свой для каждого банка). В начале года 5/6 некоторого количества денег положили в первый банк. К концу года сумма этих вкладов стала равной 670 у.е., а к концу второго года – 749 у.е. Было подсчитано, что если бы первоначально исходного количества денег положили во второй банк, то по истечении одного года сумма вкладов в эти банки стала бы равной 710 у.е. В предложении, что исходное количество денег первоначально целиком положено в первый банк, определить величину вклада по истечении двух лет.

Обозначим через x первоначальную сумму денег. Тогда через а обозначим процент, на который возрастает сумма за год в первом банке, а через b – во втором банке. К концу первого года сумму вклада в I банке стала равной , во II банке , а к концу второго года и . По условию задачи сумма вкладов в конце первого года составляет 670 у.е., а к концу второго года – 749 у.е., поэтому можно составить два уравнения:

Если во второй банк положить у.е., а в первый – у.е, то сумма вкладов к концу года составила бы:

что равнялось бы 710 у.е. Поэтому получим третье уравнение:

Для нахождения известного х составим систему уравнений из (1) и (3) и решим её (4а).

Подставляя вместо и вместо в уравнение (2), приходим к уравнению (рис. 4б), имеющему один корень: x=660 , но тогда:

Если исходное количество денег положить на два года, то к концу второго года величина вклада составит 726 у.е.

Рабочий положил на хранение в сберегательный банк 5000 руб. По истечении одного года к его вкладу были причислены процентные деньги, и в то же время он увеличил свой вклад ещё на 5000 руб., а по истечении ещё одного года попросил выдать ему накопленные процентные деньги. Сколько процентов в год начисляет сбербанк, если рабочий получил 1232 руб. процентных денег, оставив вклад в 10 000 руб. на новый срок?

Пусть x % в год начисляет сбербанк, а y % - процент за 2 года. x + x + y - весь начисленный процент. По условию задачи 2 x+y=1232 ( руб. )

За I и II начисленный процент равен 5000  0,01 x =50 x , а процент за оба года равен 0,01 x  (5000+50 x ).

50 x +50 x +0,01 x  (5000+50x)=1232

Решив это уравнение (рис. 5а), найдём два значения для х: х ₁ =-308 – не удовлетворяет условию задачи, х ₂ =8. Значит, сбербанк начисляет в год 8%.

Довольно часто приходится смешивать различные жидкости, порошки, разбавлять что-либо водой или наблюдать испарение воды. В задачах такого типа эти операции приходится проводить мысленно и выполнять расчёты.

Из сосуда ёмкостью 54 литра, наполненного кислотой, вылили несколько литров и доли сосуд водой. Потом опять вылили столько же литров смеси. Тогда в оставшейся в сосуде смеси оказалось 24 литра чистой кислоты. Сколько кислоты вылили в первый раз?

Пусть x литров кислоты вылили в первый раз. Тогда в сосуде осталось (54- x ) литров. Долив сосуд водой, получим 54 литра смеси, в которой растворилось (54-х) литров кислоты. Значит в одном литре смеси содержится литров кислоты. Всего за два раза вылили 54-24=30 литров кислоты. В результате получили уравнение (рис. 5в.):

Решив это уравнение, найдём два корня: х=90 и х=18. Ясно, что значение 90 не удовлетворяет условию задачи.

Ответ: в первый раз было вылито 18 литров воды.

При решении задач на смеси считается, что рассматриваемые смеси однородны: не делается различия между литром как единицей массы и как единицей ёмкости. Концентрацией вещества называется отношение массы этого вещества к массе всей смеси (раствора, сплава). Концентрация вещества, выраженная в процентах, называется процентным отношением вещества в смеси (растворе, сплаве).

В каких пропорциях нужно смешать раствор 50%-й и 70%-й кислоты, чтобы получить раствор 65%-1 кислоты?

Пусть х г – масса 50%-й кислоты, y г – масса 70%-й кислоты, 0,5х г – масса чистой кислоты в первом растворе, ( x + y )г – масса смеси, 0,65( x + y )г - масса чистой кислоты в смеси. Составим уравнение (рис. 6а):

0,5 x +0,7 y =0,65( x + y )

Получаем соотношение 1:3.

Существует и другой способ решения этой задачи. Он называется арифметическим (или старинным) способом.

Нарисуем схему (рис. 6б), по которой видно, что для получения 65%-й кислоты нужно взять 50%-й и 70%-й кислоты в отношении 5:15=1:3.

Пусть требуется смешать растворы а%-й и b %-й кислот, чтобы получить

Пусть х г – масса а%-го раствора, y г – масса b %-го раствора, г – масса чистой кислоты в первом растворе, а г – масса чистой кислоты во втором растворе, г – масса чистой кислоты в смеси.

при упрощении которого станет ясно, что x : y =( b - c ):( c - a ). Такой же вывод даёт схема (рис. 7б).

Но всё-таки при решении таких задач следует учитывать, что никаких химических процессов, влияющих на количественные соотношения задачи, не происходит.

Имеется два сплава, состоящие из цинка, меди и олова. Известно, что первый сплав содержит 40% олова, а второй – 26% меди. Процентное содержание цинка в первом и во втором сплавах одинаково. Сплавив 150 кг первого сплава и 250 кг второго, получили новый сплав, в котором оказалось 30% цинка. Определите, сколько килограммов олова содержится в получившемся новом сплаве.

Пусть х кг – количество олова в новом сплаве. Так как новый сплав весит 400 кг и в нём находится 30 % цинка, то он содержит кг, а во втором сплаве (120- y ) кг цинка. По условию задачи процентное содержание цинка в двух сплавах равно, следовательно можно составить уравнение (рис. 8):

Из этого уравнения находим, что у=45. Поскольку первый сплав содержит 40% олова, то в 150 кг первого сплава олова будет кг, а во втором сплаве олова будет (х-60) кг. Поскольку второй сплав содержит 26% меди, то во втором сплаве меди будет кг. Во втором сплаве олова содержится (х-60) кг, цинка 120-45=75 (кг), меди 65 кг и, так как весь сплав весит 250 кг, то имеем:

В 500 кг руды содержится некоторое количество железа. После удаления из руды 200 кг примесей, содержащих в среднем 12,5 % железа, содержание железа в оставшейся руде повысилось на 20 %. Определите, какое количество железа осталось ещё в руде?

Сначала составим таблицу (рис.9), в которой напишем массу руды, массу железа, концентрацию (долю железа в руде апишем массу руды, массу железа, концентрацию () руде?

нем 12,5 % железа, содержание железа в оставшейся руде повысилось на 20 ) до и после удаления примесей.

Пусть х кг – масса железа в руде. Так как масса всей руды равна 500 кг, то концентрация железа в ней равна .

Так как масса железа в 200 кг примесей равна 0,125  200=25 (кг), то его масса в руде после удаления примесей равна (х-25) кг. Из того, что масса оставшейся руды равна 500-200=300 кг следует, что концентрация железа в ней равна .

По условию, содержание железа в оставшейся руде повысилось на 20%=1/5. Составим уравнение (рис. 10), по которому найдём, что х=212,5 кг – масса железа в руде.

Найдём остаток железа в руде после удаления примесей:

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

В результате изученной темы было выяснено, что существует множество различных задач. Естественно, все их виды рассмотреть невозможно. Также мы научились правильно анализировать задачи и решать их разными методами (путём составления уравнений и систем уравнений, путём составления таблиц и т. д.) и разными способами: алгебраическим и арифметическим (старинным). Арифметические способы решения текстовых задач имеют больший развивающий потенциал, чем универсальный алгебраический способ решения. В наше время предпочтение отдаётся алгебраическому способу.

Читайте также: