Решение задач на компьютере

Лекция 1.
д.ф.-м.н. Москвитин А.А.

Москвитин А.А. Задачный подход в информатике. – Новосибирск, НГУ, 2003.
Москвитин А.А. Решение задач на компьютерах в 4-х частях. – Новосибирск, СибГУТИ, 2009.
Пойа Как решать задачи

Программист

В пп. «А,В,С» задача может измениться

Самый общий ответ таков:
человек понимает беспокоящую его задачу, а не просто обеспокоен (томиться) ею, если и только если он в состоянии распознать ситуации, когда задача решена от всех прочих ситуаций.
Что же необходимо сделать для того, чтобы удовлетворить это чувство беспокойства, да еще и в том случае, когда для этого мы привлекаем компьютерную технику?
Какие при этом возникают проблемы и непредвиденные ситуации в практике решения задач на компьютерах, и чем они «грозят» как пользователям, так и разработчикам программных средств?

Задача - это неудовлетворенное чувство беспокойства.

Замечание: не следует путать решение/нерешение задачи с ответом/неответом на вопрос. В некотором смысле решение/нерешение – это алгоритм, а ответ/неответ – чаще всего некоторое конкретное значение, выраженное текстом или числом.

Река

Условия

Заключение

Критерий

Задача = условие + заключение
Осмысленная задача = условие + заключение + критерий осмысленности

Задача – основа разработки информационной системы
Этапы решения задачи:
Прагматический.
Методологический.
Теоретический.
Технологический.

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

Предметные области:
Физика:

Математика:
Теорема Ф. Виета (1540-1603)





ax2 + bx + c = 0

Закон Ш.О. Кулона (1736-1806)

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

H = Lim (d1+d2+ … + dn)
n

d1

d2

a

b

H

H = Lim (d1+d2+ … + dn)
n

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

Дано:
ax2 + bx + c + 0,
Найти:
Заряды капель x1 и x2?
Критерий осмысленности:
Решение ищем во множестве действительных чисел, т.к. заряды могут быть только действительными (отрицательными и/или положительными).
D = b2 – 4ac ≥ 0.
Алгоритм представлен на псевдокоде.

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

Общая схема решения задач на компьютере

Решение задачи
(разработка ПС)

П-документация
С-документация

Принятие пользователем ответственного решения на всех этапах постановки и решения задачи
Понятность задачи для пользователя
Корректность постановки и решения задачи
Конструктивность постановки и решения задачи
Удобство работы для пользователя в языках спецификаций задач

Процесс решения задачи на компьютере начинается с ее точной постановки.
Точная постановка задачи возможна лишь при ее правильной спецификации.
Спецификация же задачи предполагает использование точного и достаточно выразительного языка.
Точность языка обеспечивается его формальностью;
Выразительность – достаточно богатым набором синтаксических средств и точной семантикой такого языка.

Для решения задач на компьютере, наиболее адекватным языком, отвечающим сформулированным требованиям, может служить, например, язык математической логики.
Под математической логикой (математической системой M) обычно понимают совокупность, включающую по меньшей мере следующие объекты:
алфавит K;
множество A слов в K, называемых аксиомами;
конечное множество R1, …, Rm отношений в K, называемых правилами вывода.
Следовательно, для точной постановки и эффективного решения задачи на компьютере нам необходимо выбрать точный и достаточно выразительный язык спецификаций задач, а также удобный и эффективный язык реализаций задачи.
Тогда результатом действий по решению задачи на компьютере будет разработка программного средства и проведение расчетов на компьютере.

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

Спецификация задачи:

анализ и исследование задачи
построение модели,
постановка задачи
выбор или разработка алгоритма.

Решение задачи:

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