Способ решения вычислительной задачи
Методы решения вычислительных задач зависят от многих причин: их сложности, математической подготовки учащихся, поставленных учителем целей и т. д.
В зависимости от применяемого математического аппарата различают следующие методы или способы решения вычислительных задач: арифметический, алгебраический, геометрический и графический. По характеру логических операций, используемых в процессе решения, различают аналитический, синтетический и аналитико-синтетический методы.
Арифметический метод. При этом методе над физическими величинами производят только арифметические действия. Физические задачи решают примерно так же, как задачи на уроках арифметики: по вопросам, без применения формул. Арифметический способ применяют в основном на первой ступени обучения физике, когда учащиеся еще не имеют достаточных знаний по алгебре или еще не уяснили достаточно глубоко зависимость между величинами, входящими в физические формулы.
Иногда считают, что отличительная черта арифметического метода — отсутствие буквенных выражений. Дело как раз не в буквенных выражениях, а в том, что при этом методе не составляют и не решают уравнений. Приведем пример решения задачи арифметическим способом, но с применением буквенных выражений. Возьмем задачу на закон Архимеда, когда с буквенными обозначениями соответствующих величин учащиеся уже знакомы.
20. Какой максимальный груз может выдержать в пресной воде плот, связанный из 25 сосновых бревен. Объем каждого бревна составляет в среднем 
Разобрав условие задачи, делаем сначала чертеж (рис. 5). Решение выполняем по вопросам.
1. Каков объем бревен плота? 
2. Чему равна масса плота? По таблице находим, что масса 
древесины равна 
3. Каков вес плота? 
.
4. Чему равна масса вытесненной воды при полном погружении плота в воду? По таблице находим, что масса 
воды равна 
5. Каков вес вытесненной воды? 
6. Чему равен вес груза? 
.
Алгебраический метод. При этом методе применяют имеющиеся у учащихся знания по алгебре, используют формулы, составляют и решают уравнения. Наиболее простой случай применения алгебраического метода состоит в решении задач по готовой формуле. Рассмотрим для примера следующую задачу.
21. Определить сопротивление километра медного провода сечением 
Сопротивление провода находят по формуле 
Удельное сопротивление находят по таблице 
В более сложных задачах окончательную зависимость, с помощью которой вычисляют искомую величину, определяют, используя несколько формул или системы уравнений.
Геометрический метод. При решении задач геометрическим методом искомую величину находят на основании известных учащимся геометрических соотношений. Геометрический метод широко применяют в статике, геометрической оптике, электростатике и других разделах курса физики средней школы.
Приведем пример решения задачи геометрическим методом. 22. Посредине троса длиной 
подвесили фонарь массой 
Определить силу натяжения троса, если стрела прогиба 
Сделаем чертеж (рис. 6,а). Силу тяжести 
разложим на две составляющие и 
направленные вдоль частей троса (рис. 6,б). Нетрудно доказать, что 
Из подобия треугольников следует: 
как стрела прогиба невелика, примем, что 
тогда 
Отсюда 
Искомое натяжение троса равно по величине и противоположно по направлению силе 
В случае геометрического метода решения задач можно использовать не только геометрические соотношения, но и тригонометрические формулы (№ 411, 905).
Графический метод. С геометрическим методом решения задач тесно связан метод графический, при котором для определения искомых величин используют графики. Ввиду значительной специфики этих задач рассматриваем их отдельно (см. стр. 24).
По характеру логических операций различают аналитический и синтетический способы рассуждения при решении задач. При аналитическом способе рассуждения начинают с определения искомой величины, выясняют, как связана эта величина с другими величинами и, последовательно применяя физические формулы, приходят кратчайшим путем к искомой величине (№ 12).
При синтетическом способе рассуждения сначала устанавливают промежуточные зависимости между данными физическими величинами, стараясь подготовить почву для определения искомой величины. В итоге всех операций, часть из которых может оказаться лишней, получают выражение, из которого и находят искомую величину.
Учащиеся чаще всего становятся на путь синтетического решения: они пробуют различные зависимости между величинами, пока не установят такую, которая дает возможность найти искомую величину. При этом, естественно, вначале возможны пути, не приводящие к желаемому результату. Синтетический способ решения наиболее простой, но не всегда короткий.
Аналитический способ труден, так как требует строгой логической последовательности в действиях, но он быстрее приводит к конечной цели.
При решении задач, особенно в старших классах, предпочтение нужно отдать аналитическому способу, так как этот способ имеет большое значение для развития логического мышления. Приведем пример решения задачи аналитическим и синтетическим способами.
23. В шахту равноускоренно опускается бадья массой 280 кг. За первые 10 сек она прошла 35 м. Определить натяжение каната.
При решении задач трудно выделить в чистом виде анализ или синтез, они выступают всегда во взаимосвязи. Поэтому часто говорят об аналитико-синтетическом способе рассуждения при решении задач.
Однако в первом случае, когда мы начинаем рассуждение с вопроса задачи, на первый план выступает все же анализ. Правда, в конце, когда «собирают» общую формулу для решения задачи, проводят синтез. Все же данный способ рассуждения при решении задач можно называть аналитическим.
Во втором способе вначале на первый план выступает синтез, так как синтезируются различные соотношения, которые могут быть установлены по данным и условию задачи. Хотя определенные элементы анализа есть и здесь, все же данный способ рассуждения при решении задачи можно назвать синтетическим.
Источник
Краткое руководство по сложным вычислительным задачам
Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта.
Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.
Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.
Существует множество различных классов сложности, хотя в большинстве случаев исследователи не смогли доказать, что один класс чётко отличается от других. Доказательства различия между классами – одни из самых трудных и важных задач в этой области.
Разница между классами может быть едва различимой или явной, и хорошо разбираться во всех классах довольно трудно. Поэтому мы собрали этот справочник по семи наиболее фундаментальным классам сложности. И да не будете вы больше путать между собой BPP и BQP.
Обозначает: полиномиальное время
Краткое описание: все задачи, которые легко может решить классический (не квантовый) компьютер.
Точное описание: алгоритмы класса P должны прекратить работу и выдать правильный ответ не более чем за время n c , где n – длина входных данных, c – константа.
- Является ли число простым?
- Каков кратчайший путь между двумя точками?
Что исследователи хотели бы знать: совпадает ли P с NP? Совпадение совершило бы революцию в информатике и лишило бы смысла большую часть криптографических систем (но в это почти никто не верит).
Обозначает: недетерминированное полиномиальное время
Краткое описание: все задачи, которые классический компьютер может легко проверить при наличии решения.
Точное описание: проблема попадает в класс NP, когда при наличии ответа «да» существует краткое доказательство корректности ответа. Если входные данные представляют собой строку X, а вам надо решить, совпадает ли ответ с «да», тогда кратким доказательством будет другая строка, Y, которую можно использовать для проверки корректности ответа «да» за полиномиальное время. (Y иногда называют «кратким свидетелем» – у всех задач из NP есть краткие свидетели, благодаря которым их можно проверить).
- Задача о клике. Представьте граф с рёбрами и вершинами – к примеру, вершины обозначают пользователей соцсети, а ребро – то, что они «друзья». Клика – это подмножество этого графа, в котором все люди состоят друг у друга в друзьях. О графе можно задавать следующие вопросы: есть ли в нём клика из 20 человек? 50 человек? 100? Нахождение клики – это NP-полная задача, то есть, её сложность самая высокая из всех NP-задач. Но, имея потенциальный ответ – подмножество из 50 узлов, которые могут быть или не быть кликой – проверить его легко.
- Задача коммивояжёра. Дан набор городов с расстояниями между двумя любыми парами – существует ли способ объехать все города, проехав меньше определённого расстояния? К примеру, может ли коммивояжёр объехать все столицы штатов США, проехав менее 11 000 миль?
Что исследователи хотели бы знать: P = NP? Специалисты по информатике и близко не подошли к решению этой задачи.
Обозначает: полиномиальная иерархия
Краткое описание: PH – это обобщение NP. Она содержит все задачи, которые можно получить, начав с задачи из NP, и накладывая дополнительные уровни сложности.
Точное описание: PH содержит задачи с некоторым количеством различных «кванторов», усложняющих эти задачи. Пример задачи с различными кванторами: Если нам дано X, существует ли такой Y, что для каждого Z существует W, при котором выполняется R? Чем больше в задаче кванторов, тем она сложнее, и тем выше полиномиальная иерархия.
Типичная задача: определить, действительно ли существует клика размера 50, и не существует клики размером 51.
Что исследователи хотели бы знать: никто пока не смог доказать, что PH отличается от P. Эта задача эквивалентна равенству P и NP, поскольку, если вдруг окажется, что P = NP, тогда все PH низведутся до P (P = PH).
PSPACE
Обозначает: полиномиальное ограничение пространства
Краткое описание: PSPACE содержит все задачи, которые можно решить, используя разумное количество памяти.
Точное описание: При решении задач PSPACE вы уже не переживаете за время, вы переживаете только за количество памяти, которое требуется для работы алгоритма. Специалисты по информатике доказали, что PSPACE содержит PH, которая содержит NP, которая содержит P.
Типичная задача: все задачи из P, NP и PH содержатся в PSPACE.
Что исследователи хотели бы знать: отличается ли PSPACE от P?
Обозначает: квантово-полиномиальное время с ограничением вероятности ошибок
Краткое описание: все задачи, которые легко можно решить на квантовом компьютере.
Точное описание: все задачи, которые можно решить на квантовом компьютере за полиномиальное время.
Типичная задача: найти простые множители целого числа.
Что исследователи хотели бы знать: Пока что доказано, что BQP содержится в PSPACE, и что BQP содержит P. Исследователи не знают, содержится ли BQP в NP, но они считают, что два этих класса сравнивать нельзя – есть задачи, входящие в NP, но не входящие в BQP, и наоборот.
EXPTIME
Обозначает: экспоненциальное время
Краткое описание: все задачи, которые можно решить за экспоненциальное время на классическом компьютере.
Точное описание: EXP содержит все предыдущие классы — P, NP, PH, PSPACE и BQP. Исследователи доказали, что он отличается от P – они обнаружили задачи, входящие в EXP, и не входящие в P.
Типичная задача: обобщения игр типа шахмат и шашек. Если шахматная доска может быть любого размера, то задача определения наличия преимущества у одного из игроков становится задачей из EXP.
Что исследователи хотели бы знать: они хотели бы доказать, что PSPACE не содержит EXP. Они считают, что существуют задачи, входящие в EXP, но не входящие в PSPACE, потому что иногда для решения задачи из EXP требуется очень много времени. Исследователи знают, как разделять EXP и P.
Обозначает: полиномиальное время с ограничением вероятности ошибок
Краткое описание: задачи, которые можно быстро решить при помощи алгоритмов, использующих случайность.
Точное описание: BPP совпадает с P, с той разницей, что алгоритм может включать шаги, в которых принятие решений происходит случайно. Алгоритмам в BPP необходимо давать правильные ответы с вероятностью, близкой к 1.
Типичная задача: у вас есть две различные формулы, выдающие многочлены со множеством переменных. Вычисляют ли эти формулы один и тот же многочлен? Это задача проверки полиномиальной идентичности.
Что исследователи хотели бы знать: Равны ли BPP и P. Если они равны, тогда любой алгоритм со случайностями можно было бы избавить от случайностей. Они считают, что так и есть – что для каждой задачи, для которой существует эффективный случайный алгоритм, существует и эффективный детерминистский алгоритм – но пока не смогли этого доказать.
Источник
