Сентябрь, 25, 2007 - ЗАМЕТКИ О ПРОГРАММИРОВАНИИ

Или войдите, используя свой аккаунт в:

- Facebook
- Twitter
- VK
- Google+
- Mail.ru
- OpenID

Error Имя пользователя:
Error Пароль: Забыли пароль?
Запомнить меня
Создайте аккаунт
Ваш OpenID URL:
ЗАМЕТКИ О ПРОГРАММИРОВАНИИ
Руслан Петрович Богатырёв

## Сентябрь, 25, 2007

## RB29-1. Джордж Пойа о решении задач в программировании

- 25 сент, 2007 at 3:31 PM

Изучая пару лет назад архив Эдгара Дейкстры, я нашёл тот ключ, который давно искал. Речь идёт о понимании того, что есть программирование и в чём специфика этой сферы интеллектуальной деятельности человека. Среди классиков программирования не так много можно выделить тех, кто исследовал философские аспекты. И Дейкстра, на мой взгляд, принадлежит к числу этих немногих.
В нескольких заметках Дейкстры (EWD480, EWD512, EWD881) содержится указание на книги известного математика Джорджа Пойа, посвящённые подходам к решению математических задач ("How to Solve It", "Art of Plausible Reasoning" и др.). Дейкстра уловил важную аналогию. Он видит в этих книгах ответ на вопрос, как нужно подходить к решению задач в программировании. Собственно, ценность и универсальность этих книг в отношении подхода к решению задач в сфере интеллектуальной деятельности отмечают очень многие известные специалисты, чьи интересы выходят за рамки чистой математики. В частности, их выделяет наш лауреат Нобелевской премии по физике Жорес Алфёров.
Получив этот ключ и перечитав книги Пойа уже с этой точки зрения, я пришёл к выводу о том, что многие проблемы современного программирования связаны с неадекватным пониманием его природы, его сути. Что значит неадекватным? Это значит, что нынешнее восприятие программирования через систему сложившихся стереотипов недостаточно продуктивно, недостаточно полезно для решения тех проблем, которые стали проявляться в наши дни с особой силой.
Аппетит, как известно, приходит во время еды. Вот и программирование, дав возможность обществу в той или иной степени автоматизировать свою деятельность в решении повседневных задач, привело к возникновению новых задач и к изменению взгляда на ранее известные задачи уже на новом витке эволюции, на новом витке понимания. Разрыв между задачами современного мира, производством компьютерного оборудования и собственно программированием становится весьма опасным. Сложность систем и инструментов выходит из-под контроля, при этом жизнь требует лавинообразного роста объёма программного обеспечения. Это программное обеспечение становится всё менее устойчивым во времени из-за растущей "агрессивности" окружающей информационной среды и постоянно меняющихся требований. Оно само и стимулирует эту агрессивность. Программное обеспечение стареет гораздо быстрее, чем это можно было бы ожидать в отношении "вечных" абстракций, реализованных в программах. В силу существенного отставания программирования от требований сегодняшнего дня, это неумолимо ведёт к экстенсивному развитию: масштабному росту числа разработчиков во всём мире. Такому росту, который не может быть компенсирован существующими темпами подготовки специалистов. ИТ-индустрия, всё заметнее подчиняющая себе нашу цивилизацию, становится социальной воронкой, которая начинает заглатывать в себя огромные людские ресурсы, оттягивая их из других сфер деятельности. И эта армия, в которой количество важнее качества, активно создаёт инфраструктурные системы. Другими словами, на них, как на фундаменте, начинают возводиться всё новые и новые здания программного мира. Стоит ли говорить, к чему это в итоге ведёт?
Так что же такое программирование? Это непростой вопрос, требующий погружения в сферу философии, психологии, математики, общей теории систем, кибернетики. Но прежде чем излагать своё видение и своё понимание, хотелось бы настроить читателя на соответствующий контекст восприятия.
Перемежать мысли обширными цитатами не всегда хорошо, поскольку сама мысль начинает затушёвываться. Поэтому воспользуюсь приёмом, который уже применял в своём дневнике (в отношении взглядов Д.И.Менделеева): соберу в отдельной заметке цитаты Дж.Пойа, которые привлекли моё внимание, а потом уже буду в дальнейшем ссылаться на эту заметку в качестве иллюстрации своих размышлений и выводов. Так сказать, гипертекст в действии.

Биографическая справка. Джордж Пойа (George Polya, 1887-1985) – математик с мировым именем. Родился в Будапеште. В отечественной литературе известен как Георг Полиа (немецкий вариант его имени и фамилии) и Дьёрдь Пойа (венгерский вариант). Но наибольшее распространение получил американский вариант (Джордж Пойа). В предвоенные годы работал в Швейцарии (в ETH Zurich), Англии (Oxford University, Cambridge University) и Германии. Затем, как и многие другие учёные, вынужден был покинуть Европу и переехать в США. Сферой его научных интересов были такие области математики, как теория чисел, комбинаторика, теория вероятностей. Пойа большую часть своей научной карьеры провёл в ранге профессора математики в знаменитом Стэнфордском университете в США. |

Некоторые книги проф. Пойа были переведены на русский язык:
1. Г.Г.Харди, Дж.Е.Литтльвуд, Г.Полиа "Неравенства" – ИЛ, 1948.
2. Г.Полиа, Г.Сегё "Задачи и теоремы из анализа" (в 2-х томах) — Гостехиздат, 1956.
3. Г.Полиа "Как решать задачу" – Учпедгиз, 1959.
4. Г.Полиа, Г.Сегё "Изопериметрические неравенства в математической физике" – Физматгиз, 1962.
5. Г.Полиа "Математика и правдоподобные рассуждения" – ИЛ, 1957.
6. Дж.Пойа "Математика и правдоподобные рассуждения" (1975).
7. Дж.Пойа "Математическое открытие. Решение задач: основные понятия, изучение и преподавание" (1970).

Две последних представлены в Открытой электронной библиотеке в Европейском центре программирования (EuroProg.ru).
Для представления взглядов проф. Дж.Пойа я выбрал книгу "Математическое открытие", пожалуй, наиболее ценную для нашей цели изучения природы программирования. В оригинале на английском языке она вышла в свет двумя отдельными томами (в 1962 и 1965 гг.); в 1968 г. второй том был переиздан с исправлениями и дополнением. Это очень взвешенный взгляд мудрого человека, изложенный простым и понятным языком. И здесь для нас будет важна целостность видения: посмотреть на глубинные проблемы мышления глазами проф. Пойа в рамках одной конкретной его книги.
Программирование, как и математика, связано с процессом решения задач. Этот процесс осуществляет человек. Для решения задач он мысленно ищёт различные пути, выбирает подходящие инструменты или же изготавливает их самостоятельно. Вспомним изречение известного немецкого философа Иммануила Канта: "Всякое человеческое познание начинается с созерцаний, переходит от них к понятиям и заканчивается идеями". Джордж Пойа так прокомментировал этот афоризм Канта: "Изучение начинается с действия и восприятия, переходит от них к словам и понятиям и должно заканчиваться выработкой каких-то особенностей умственного склада". Программирование – это особая форма познания мира, в которой на первый план выходит не созерцание, а поиск/формирование идей и понятий, необходимых для решения тех или иных задач. Что ограничивает сферу этих идей и понятий и есть ли здесь ограничения? Оставим этот вопрос пока без ответа. К нему мы ещё вернёмся.
"Основная часть нашего сознательного мышления,— пишет Пойа,— связана с решением задач. Когда мы не развлекаемся и не мечтаем, наши мысли направлены к какой-то конечной цели, мы ищем пути и средства к достижению этой цели, мы пытаемся выработать какой-то курс, следуя которому, можно достичь нашей конечной цели. Решение задач – специфическое достижение разума, разум же – особый дар, которым наделён человек. Способность к преодолению препятствий, к нахождению обходного манёвра там, где не видно прямого пути, возвышает умное животное над тупым, человека – над самым умным животным и талантливых людей – над другими людьми".
"Процесс решения задачи,— уточняет он,— представляет собой поиск выхода из затруднения или пути обхода препятствия, — это процесс достижения цели, которая первоначально не кажется сразу доступной. Решение задач является специфической особенностью интеллекта, а интеллект – особый дар человека; поэтому решение задач может рассматриваться как одно из самых характерных проявлений человеческой деятельности…"
Что же такое задача? Вот как поясняет свой взгляд на это понятие Дж.Пойа. "При современном укладе жизни добывание пищи обычно не представляет задачи. Если я проголодаюсь дома, то тащу что-нибудь из холодильника, в городе же – иду в какое-нибудь кафе или закусочную. Однако совсем другое дело, когда холодильник пуст или когда я оказываюсь в городе без денег; в таких случаях желание поесть приводит к задаче, иногда достаточно трудной. Вообще говоря, желание может иногда приводить к задаче, а иногда – нет. Если одновременно с желанием в моём мозгу сразу же, без какого бы то ни было усилия возникает очевидное средство, с помощью которого наверное можно осуществить это желание, то задача не возникает. Если же такого средства нет, то это – задача. Таким образом, задача предполагает необходимость сознательного поиска соответствующего средства для достижения ясно видимой, но непосредственно недоступной цели. Решение задачи означает нахождение этого средства".
Итак, задача – это вызов, внешний раздражитель, мотивация перехода мышления из пассивного состояния (созерцание) в активное (поиск и формирование абстракций). Но как мы ищем и находим решение? "Решение задачи,— поясняет Пойа,— может возникнуть перед нами совершенно неожиданно. Мы долго копались в задаче без какого бы то ни было видимого прогресса – и внезапно нас осеняет блестящая идея, вспышка вдохновения, мы вдруг видим проблеск света во тьме! Это похоже на то, как бывает, когда входишь поздней ночью в незнакомый гостиничный номер, в котором даже не знаешь, где зажигается свет. Отыскиваешь в темноте выключатель, натыкаешься на какую-то мебель, ощущаешь какие-то острые углы, какие-то бесформенные тёмные массы. Но вот выключатель нашёлся, зажёгся свет – и всё сразу стало ясным. Бесформенные массы разделились, приняли очертания знакомых предметов, причем оказалось, что эти предметы расположены там, где и им и надлежит быть, и что они хорошо приспособлены для того, чтобы выполнять своё назначение. Именно так и могут выглядеть переживания решающего, сопровождающие решение задачи: идея – это внезапное просветление, вносящее ясность, порядок, связь и целесообразность в детали, которые до этого казались смутными, разбросанными, запутанными, неуловимыми".
Пойа приводит слова великого Лейбница: "Мариотт говорит, что человеческий разум подобен шкатулке: думая, вы раскачиваете эту шкатулку, пока из неё что-нибудь не выпадет. Таким образом, нет сомнения в том, что результат размышления в какой-то степени зависит от случая. Я бы добавил, что человеческий разум ещё больше походит на сито: когда вы думаете, вы раскачиваете сито, пока сквозь него не просыплются какие-то мелкие частицы. По мере того как они проходят, ваше настороженное внимание подхватывает те из них, которые кажутся относящимися к делу". Хорошо бы знать, где находятся эти заветные шкатулка и сито, и есть ли в них что-нибудь, заслуживающее нашего внимания. А за раскачиванием у нас дело не станет.
Внезапное озарение — это нечто из области подсознания, интуиции, мира иррационального. Это то, что нельзя объяснить и разложить по полочкам. Можно попытаться искусственно подвести себя к такому состоянию, посеять зёрна и терпеливо ждать их всхода. Но будет ли урожай? Появится ли это вдохновение? Значит, наряду с озарением неплохо бы иметь и некий рациональный подход к решению. Пусть он будет ограничен в предоставляемых возможностях. Пусть это будет не парящая в небе вольная птица, а вполне приземлённый трудолюбивый муравей. Главное, как найти решение? Что на сей счёт думает Пойа?
"Найти решение задачи,— отмечает Пойа,— это значит установить связь между ранее дифференцированными объектами или идеями (объектами, которые у нас имеются, и объектами, которые нам требуется отыскать, данными и неизвестным, предпосылкой и заключением). Чем дальше друг от друга находились вначале зависимые объекты, тем больше уважения заслуживает исследователь, обнаруживший между ними связь. Иногда эту связь мы представляем себе в виде моста: значительное открытие поражает нас, как наведение моста над глубокой пропастью, разделяющей две идеи, далеко отстоящие друг от друга. Часто эта связь представляется осуществлённой как бы при помощи цепи: доказательство предстает перед нами как взаимосвязь аргументов, как цепь – возможно это будет длинная цепь – выводов. Вся цепь в целом не более прочна, чем её слабейшее звено, — и если хотя бы одного звена недостает, то нет обоснованного доказательства, нет непрерывности хода рассуждений. Ещё чаще мысленную связь ассоциируют с нитью – всем нам приходилось видеть преподавателя, который потерял нить своих рассуждений и которому приходилось подглядывать в свои записки для того, чтобы восстановить утерянную нить… Тонкую нить естественно представлять как геометрическую линию, а взаимно связанные объекты – просто как точки; так, почти с неизбежностью возникает диаграмма, графическое представление взаимосвязи математических выводов".
Итак, найти решение означает построить мост между отправным и конечным пунктами абстракций (предпосылкой и заключением). Выстроить его в виде взаимосвязи рассуждений (цепочки или более сложной схемы). Представление этой взаимосвязи напрашивается выполнять в графическом виде. Хотя… Есть естественный язык, есть язык формул, есть язык образов (и не только графических). У каждого — свои плюсы и минусы. Обязательно ли использовать только один из них? Или можно комбинировать? Математика несмотря на всю свою строгость и формальность наглядно демонстрирует, что требуются все три вида. Да и естественным языком не стоит пренебрегать, сколь бы расплывчатыми и многозначными не казались его формулировки. "Достаточно часто отмечалось, что язык, которым мы пользуемся, полон метафор (слабых, посредственных и ярких). Однако мне неизвестно,— пишет Пойа,— замечено ли также то, что многие из этих метафор взаимозависимы: они могут быть как-то связаны между собой, как-то объединены, могут образовывать более или менее независимые или, наоборот, более или менее сцепленные между собой группы". Запомним этот момент. В дальнейшем он нам пригодится.
А что есть решение, что служит результатом наших умственных усилий? Это объект или процесс? Пойа рассматривает оба значения слова "решение". Он пишет: "Решение (объект, solving object) — объект, удовлетворяющий условию задачи. Если в задаче ставится цель решить алгебраическое уравнение, то решение (объект) — это корень уравнения, т.е. величина, удовлетворяющая уравнению. Решение (объект) может существовать только у задач на нахождение. В отчётливо сформулированной задаче должна быть заранее чётко указана категория (множество), к которой принадлежит решение (объект),— мы должны знать наперёд, что мы ищем: треугольник ли, число ли, или ещё что-нибудь. Такое указание (чёткое выделение множества, к которому принадлежит неизвестное) является важной частью задачи. "Найти неизвестное" означает найти (отождествить, построить, провести, получить,…) решение (объект) [или множество всех решений (объектов)]." Пойа выделяет особенности и второго значения слова "решение". Он уточняет: "Решение (процесс, solving procedure) — процедура (построение, схема операций, система выводов), заканчивающаяся нахождением неизвестного в задаче на нахождение или ликвидацией сомнения в справедливости (или ложности) утверждения, высказанного в задаче на доказательство. Таким образом, решение (процесс) — термин, применимый к обоим видам задач. В начале работы мы обычно не знаем процедуры решения, надлежащей схемы операций, но мы неустанно ищём её в надежде, что, в конце концов, определим её полностью; эта процедура является частью наших поисков; она по смыслу, по сути дела,— наше неизвестное, она (употребим такое выражение) наше "процедурное неизвестное". Можно говорить о "работе над решением" (work of solving) или о "результате решения" (result of solving)…"
Пойа чётко выделил два рода задач: задачи на нахождение (поиск/построение объекта) и задачи на доказательство (поиск/построение процесса). Уже здесь очевидно проглядывают императивность и декларативность, столь знакомые нам в программировании. Императивная последовательность явных шагов к цели ("как") и декларативное описание задачи, подразумевающее неявный путь к цели ("что"). Механический (машинный) путь "мышления" и ментальный (человеческий) путь "мышления", яркими выразителями которого являются соответственно императивное программирование (ИП) и функциональное программирование (ФП). Объектно-ориентированное программирование (ООП) и сценарное программирование (СП) удобнее будет пока рассматривать как пограничные сферы, сочетающие в себе элементы ИП и ФП.
"Ну вот,— подумает нетерпеливый читатель,— всё это конечно хорошо, вполне понятно, но пока что идут какие-то общие рассуждения. Где же, наконец, рецепт? Как же решать задачи? Ждать у моря погоды? Подражать известным решениям?" Не будем торопиться и продолжим знакомство с подходом проф. Пойа.
Он пишет: "Решение задач – практическое искусство, подобное плаванию, катанию на лыжах или игре на фортепиано; научиться ему можно только подражая хорошим образцам и постоянно практикуясь… Конечно, подражать уже известному решению легко, если новая задача очень похожа на известную вам; однако если сходство задач невелико, то такое подражание может оказаться гораздо более трудным и даже едва осуществимым. В глубине души человек стремится к большему: ему хотелось бы обладать универсальным методом, позволяющим решать любую задачу. У большинства из нас это желание остаётся скрытым, но оно иногда проступает наружу в сказках и произведениях некоторых философов. (Возможно, вы припомните сказку о волшебном слове, открывающем все двери.) Над универсальным методом, пригодным для решения любых задач, размышлял Декарт; наиболее же чётко сформулировал идею о совершенном методе Лейбниц. Однако поиски универсального, совершенного метода дали не больший эффект, чем поиски философского камня, превращающего неблагородные металлы в золото: существуют великие мечты, которым суждено оставаться мечтами. Тем не менее такие недостижимые идеалы не остаются бесполезными — пока никто не достиг полярной звезды, но многие, глядя на неё, находили правильный путь".
Пойа упоминает о методе Декарта. О чём идёт речь? В своих "Правилах для руководства ума" французский философ и математик Рене Декарт (1596-1650) постарался сформулировать универсальный метод решения задач. Его метод выражается в трёх пунктах.

1. Задача любого вида сводится к математической задаче.
2. Математическая задача любого вида сводится к алгебраической задаче.
3. Любая алгебраическая задача сводится к решению одного-единственного уравнения.

Как отмечает Пойа, "чем больше объём ваших знаний, тем больше пробелов вы сможете усмотреть в этой программе". И далее он продолжает: "В намерении, положенном в основу схемы Декарта, можно усмотреть нечто глубоко правильное. Однако претворить это намерение в жизнь оказалось очень трудно: здесь возникло гораздо больше препятствий и осложнений, чем это первоначально представлял себе полный энтуазиазма Декарт. Проект Декарта потерпел неудачу, однако это был великий проект, и, даже оставшись нереализованным, он оказал большее влияние на науку, чем тысяча малых проектов, в том числе таких, которые удалось реализовать".
Дерзкая идея. Наивная? В какой-то мере — да. Но в ней в самом деле видна некая правильность, чувствуется глубина. Хорошо. Пусть надо свести задачу реальной жизни к математической. Но как это сделать? Пытаться её разбить на несколько задач, декомпозировать? В "Рассуждении о методе" Декарт подтверждает наши ожидания. Он пишет: "Расчлените каждую изучаемую вами задачу на столько частей, на сколько сможете, и насколько это потребуется вам, чтобы их было легко решить". Расчленить – это здорово. Но как? Вот в чём загвоздка. И Лейбниц обоснованно возразил Декарту: "Это правило Декарта малоэффективно, поскольку искусство разделения… остаётся неподдающимся истолкованию. Разделяя задачу на неподходящие части, неопытный решающий может увеличить свои затруднения".

Но ведь с чего-то надо начинать. Чтобы подвести читателя к своему подходу, Пойа приводит ряд примеров. Остановимся на одном из них (с.185). Разбирая решение задачи о нахождении объёма правильной четырёхугольной усечённой пирамиды, Пойа отмечает разные аспекты (он их называет уровнями), которые задействованы при этом: "На рисунке каждый этап решения (каждый мысленный образ, возникающий у решающего задачу) представлен в четырёх формах. Части рисунка, относящиеся к одному и тому же мысленному образу, расположены одна под другой по вертикали, так что за ходом решения можно следить по четырем горизонтальным путям, расположенным на четырёх различных уровнях. На самом важном из них, на уровне геометрических образов, мы видим эволюцию изучаемой фигуры в мыслях решающего. На каждом этапе решения у него возникает мысленное изображение исследуемой геометрической фигуры, и это изображение меняется при переходе к следующему этапу; при этом некоторые детали отступают на задний план, внимание начинают привлекать другие детали, а некоторые детали появляются вновь. Спускаясь на одну ступень, мы попадаем на уровень связей. При графическом представлении решения элементы задачи (неизвестное, данные, вспомогательные неизвестные) символически обозначаются точками, а соотношения, связывающие эти элементы,— линиями, соединяющими эти точки. Непосредственно над уровнем связей расположен уровень вычислений, представленный формулами; в некотором смысле его можно противопоставить уровню связей. Мы имеем здесь в виду следующее: на уровне связей мы фиксируем совокупность всех соотношений, найденных к рассматриваемому моменту; последнее из этих соотношений выделено (цветом или толщиной линий; оно находится в фокусе нашего внимания), но показано не с большими подробностями, чем предыдущее. На вычислительном же уровне на каждом этапе решения полностью выписана только последняя формула, предыдущие же не отражены никак. Опускаясь еще ниже, мы попадаем на эвристический уровень, который для нас важнее всего. На каждом его этапе ставится простой, естественный, вопрос (который можно поставить и в любой другой задаче) или даётся некоторая рекомендация, способствующая достижению данного этапа".

Итак, Пойа формулирует четыре уровня, четыре аспекта:
1. Геометрические образы (приближение к образным формам в мышлении).
2. Связи (взаимосвязь форм, соответствия, отображения, отношения).
3. Вычисления (язык формул, вбирающий в себя образы и связи).
4. Эвристика ("суфлёры", рецепты решений).

Пойа терпеливо ведёт нас к своей модели, той заветной модели, которая поясняет, как же мы думаем. Но не будем торопить события, нам ведь важно это понять, не так ли?
В задаче очень важно ухватить главную идею решения, стержень, на который будёт нанизываться всё остальное. Это остальное будет второстепенным, рутинным, вспомогательным. Там, конечно, могут быть свои главные идеи рангом пониже, но стержень определяет многое. Пойа рекомендует начинать с уровня чертежей, образов, графического уровня (аспекта). Затем начинать понемногу насыщать его деталями наших мысленных построений. Он поясняет: "Самый бросающийся в глаза признак прогресса в решении задачи — это появление всё новых и новых подробностей на графической иллюстрации решения. По мере того, как решающий успешно продвигается вперёд, на геометрических фигурах и на диаграмме связей возникают всё новые и новые линии. За всё увеличивающейся сложностью чертежа мы должны ощущать развитие мысленных построений решающего. С каждым новым шагом он включает в работу новые относящиеся к делу сведения; он узнаёт на изучаемом рисунке какую-то знакомую конфигурацию, применяет некоторую известную ему теорему. Таким образом, умственная работа решающего предстаёт перед нами как воскрешение относящихся к делу элементов его опыта, как связь этого опыта с решаемой задачей, как мобилизационная и организационная работа".
Пойа подводит нас к тому, что он называет дисциплиной ума – "некоторому ядру принципов и правил, известной системе направляющих линий на пути к универсальному методу, который пытались открыть Декарт и Лейбниц". Пойа выделяет два ключевых понятия – план и программа. Не правда ли, знакомые до боли слова?
Пойа приводит слова Т.Гоббса из его "Левиафана": "От желания возникает мысль о некоторых средствах, при помощи которых мы видим осуществлённым нечто подобное тому, к чему мы стремимся, и от этой мысли — мысль о средствах для достижения этих средств, и так далее, пока мы не доходим до некоторого начала, находящегося в нашей собственной власти". В этих словах, как пишет Пойа, "с замечательной краткостью и точностью изложен фундаментально важный метод, определяющий процесс решения задачи". Он продолжает: "Итак, перед нами стоит задача. Иными словами, у нас есть цель A, к которой мы не можем прийти сразу, и мы стремимся найти подходящий образ действий для её достижения. Эта цель может принадлежать к области практики или к области теории, возможно, она относится к математике… "От желания возникает мысль о некоторых средствах" — это хорошо подмеченное свойство ума. Цель подсказывает средство: обычно вскоре вслед за желанием нам приходит мысль об определённых действиях, необходимых для осуществления этого желания… Но вернёмся к словам Гоббса: "От желания возникает мысль о некоторых средствах" B, с помощью которых можно получить A… Мы думаем, что могли бы получить A, если бы имели B. А из мысли о B возникает мысль о средствах, например, о C, с помощью которых можно получить это B… "И так далее, последовательно"… "пока мы не доходим до некоторого начала, находящегося в нашей собственной власти"… Мы могли бы получить D, если бы имели E, но ведь у нас есть E! На этом E заканчивается ход наших мыслей; мы обладаем E, оно "в нашей собственной власти", дано, известно…"
Далее Пойа продолжает: "То, о чём мы только что говорили, можно назвать составлением плана. За ним должна следовать, конечно, реализация плана… Заметим, что составление плана и его реализация идут в противоположных направлениях. Мы начинаем составление плана с A (цель, неизвестное, заключение); мы его заканчиваем, достигнув E (заданные нам объекты, данные, условие). Реализуя же наш план, мы напротив, продвигаемся от E к A; таким образом, об A, т.е. о нашей цели начинаем думать в самом начале, достигаем же её в самом конце. Если движение в направлении цели рассматривать как движение в прямом направлении, то можно сказать, что при составлении плана мы продвигались в обратном направлении. Таким образом, описанным Гоббсом важный метод решения задач можно было бы назвать составлением плана в обратном направлении, или продвижением от конца к началу; греческие геометры называли этот метод анализом, что по смыслу означает "решение от конца к началу". Если же мы продвигаемся в противоположном направлении, т.е. от объектов, которые находятся в нашем распоряжении, по направлению к цели (в нашем случае от E к A), то такой метод решения (в противоположность первому методу) называют составлением плана в прямом направлении, или продвижением от начала к концу, или синтезом (что по-гречески означает "соединение")".
Думаю, пытливый читатель уже смекнул, что к чему. Прямой и обратный путь решения, восходящий и нисходящий принцип разработки, синтез и анализ, императив и декларатив. Что есть план – понятно. А что есть программа (в понимании Пойа)? Это реализация плана. Т.е. конкретизация контура, подхода, идей решения. Она может проступать постепенно, но наполняет конкретикой (тут императив и декларатив выступают на равных основаниях).
Может ли быть несколько разных планов? Конечно. А у каждого плана несколько реализаций? Разумеется. Вот что пишет Пойа: "Очень часто мы не получаем сразу окончательного плана, в нашем плане имеются разрывы, всё ещё не хватает некоторых нужных идей. Но это нас не останавливает, мы приступаем к его реализации в надежде, что появится какая-нибудь яркая или же просто новая идея и что с её помощью нам удастся ликвидировать пробелы. Хороший план отличается от плохого прежде всего тем, что надежда на появление нужной идеи здесь больше. Если же мы вообще не нуждаемся в новых идеях, а, наоборот, уверены, что заранее обдуманные и предусмотренные шаги обеспечивают достижение цели, то наш план можно считать достаточно чётким и определённым, чтобы называть его (полной) программой действий. Иногда приходится затрачивать очень много времени на разработку различных несовершенных планов прежде, чем какой-то один из них удастся превратить в программу".
В примечаниях Пойа указывает ещё одну, комбинированную схему построения плана (и программы). Т.е. двигаться сразу с нескольких сторон, как бы заглядывая вперёд (оборачиваясь назад). Практика программирования (добавлю от себя) показывает, что это один из самых продуктивных подходов. Пойа пишет: "Окончательный план, полная система взаимных связей… не указывает направления, в котором он составлялся. Один решающий мог бы начать его построение с данных и продвигаться в направлении, указанном стрелками… В то же время другой решающий (перед которым стоит иная, возможно, более сложная задача) мог бы составлять план, не придерживаясь при этом однажды выбранного направления. Избрав в качестве отправного пункта либо начало, либо конец, он мог бы продвигаться то от неизвестного к данным, то от данных к неизвестному; он мог бы продвигаться также попеременно в обоих направлениях; при этом он мог бы устанавливать некоторые перспективные связи между объектами, которые пока ещё не связаны ни с началом, ни с концом намеченной схемы решения, прокладывать мостики между изолированными точками, скучающими в одиночестве, где-то между данными и неизвестным". Он продолжает: "Хорошей схемой будет чередование размышлений в обоих направлениях. Когда надежда на достижение результата по одному направлению угасает или работа в этом направлении начинает нас утомлять, мы обращаемся к другому направлению, будучи готовыми, если этого потребуют обстоятельства, снова вернуться к первоначальному направлению; таким образом, накапливая сведения в процессе работы по обоим направлениям, мы можем в конечном счёте добиться успеха".
Один из важных моментов — постановка и решение вспомогательных задач. Они не просто служат недостающим звеном в цепи решения. Они помогают пролить свет на подходы к решению. Пойа пишет: "Некоторые виды вспомогательных задач, даже будучи решены, не гарантируют полного решения первоначальной задачи; однако они могут оказать частичную помощь в её решении. Часть решения вспомогательной задачи (или даже всё решение целиком) может стать частью решения исходной задачи, обеспечив для последнего какой-нибудь вывод, построение (или же просто отдельный факт, который послужит основой такого вывода, построения и т.д.). Даже если такой частичной помощи ждать неоткуда, вспомогательная задача может принести методологическую помощь: она может подсказать метод решения или направление, в котором следует начинать работу…"
В программировании наиболее очевидным аналогом реализации вспомогательных задач служат процедуры (подпрограммы, функции, методы). Однако не стоит понимать всё столь буквально. Отображать можно разными способами, не говоря уже о том, чтобы формировать специальные программные конструкции большого и малого масштаба, носящие временный, вспомогательный характер с целью прояснения деталей программного проекта и обоснования принятия тех или иных проектных решений. Речь идёт о макетировании (прототипировании). Но вернёмся к книге Пойа: "Вспомогательные задачи могут оказать помощь ещё одним довольно тонким образом. Занимаясь задачей, мы принимаем известные решения. Допустим, что работу можно продолжать по двум направлениям, что нам открыты два пути: один – направо, другой – налево. Какой из них выбрать? Который из двух ведёт к решению с большей вероятностью? Важно уметь разумно оценивать шансы – и в этом отношении вспомогательные задачи могут служить желательным руководством. Весьма вероятно, что внимание и труд, затраченные на решение вспомогательной задачи, и приобретённый при этом опыт весьма благоприятно скажутся на решении исходной задачи".
Пойа раскрывает важный принцип: Respice finem. Он пишет: "Стремление достичь цели следует рассматривать как стимул, оно подсказывает нам действия, которые, возможно, приведут к достижению цели. Желанный конец диктует средства. Поэтому смотрите в конец, не спускайте глаз с вашей цели; она направляет ваши мысли. Respice finem означает "Смотри в конец"; эта фраза была обиходной во времена, когда латынь была общеупотребительной. Она взята из средневекового гекзаметра: Quidquid agis prudenter agas et respice finem (что бы ни делал, благоразумнее делай и смотри в конец). Гоббс поясняет это: "… во всех ваших действиях часто имейте перед глазами то, чего вы хотите достигнуть, как ту вещь, которая направляет все ваши мысли на пути к её достижению". Раздумывая над концом задачи, мы надеемся, что возникнет мысль о подходящих средствах для её решения. Чтобы сократить время, необходимое для прихода этой мысли, нужно стараться представить себе конец с максимальной отчётливостью: Что требуется? Какого рода объект вы хотите найти? Что представляет собой неизвестное? В чём состоит заключение? Мы должны применять самые настойчивые усилия, чтобы вызвать в своём воображении подходящие средства: Как можно получить такой объект? Где можно отыскать подобный объект? В каком магазине можно приобрести подобную вещь? Как можно вывести такое заключение?"
Немного о мотивации. Это то самое топливо, без которого практически нереально решить любую задачу. Мотивация бывает различной. Но, пожалуй, сама сильная – это чувство собственности в отношении задачи. Пойа пишет: "Существенным ингредиентом процесса решения всякой задачи является желание, стремление, решимость её решить. Задача, которой вы предполагаете заняться, которую вы достаточно хорошо поняли,— это ещё не совсем ваша задача. Она становится по-настоящему вашей, действительно овладевает вами, когда вы твёрдо решили заняться ею как следует и стремитесь решить её. Задача может увлечь вас больше или меньше, ваше желание решить её может быть более или менее сильным, но я утверждаю, что пока оно не станет очень сильным, ваши шансы решить по-настоящему трудную задачу будут ничтожны".
Окончание заметки см. RB29-2.

- Поделиться
- Ссылка

## RB29-2. Джордж Пойа о решении задач в программировании

- 25 сент, 2007 at 3:42 PM

Начало заметки см. RB29-1.

Изучая пару лет назад архив Эдгара Дейкстры, я нашёл тот ключ, который давно искал. Речь идёт о понимании того, что есть программирование и в чём специфика этой сферы интеллектуальной деятельности человека. Среди классиков программирования не так много можно выделить тех, кто исследовал философские аспекты. И Дейкстра, на мой взгляд, принадлежит к числу этих немногих. В нескольких заметках Дейкстры (EWD480, EWD512, EWD881) содержится указание на книги известного математика Джорджа Пойа, посвящённые подходам к решению математических задач ("How to Solve It", "Art of Plausible Reasoning" и др.). Дейкстра уловил важную аналогию. Он видит в этих книгах ответ на вопрос, как нужно подходить к решению задач в программировании.
Для представления взглядов проф. Дж.Пойа я выбрал книгу "Математическое открытие", пожалуй, наиболее ценную для нашей цели изучения природы программирования.
------

О контурном подходе к решению задач (читай – "контурное проектирование"). Пойа пишет: "Как только мы начинаем серьёзно заниматься какой-нибудь задачей, нас что-то побуждает заглядывать вперёд, мы пытаемся предвидеть, что будет дальше: мы ждём чего-то, мы стремимся угадать контур решения. Этот контур может быть более или менее расплывчатым, он может быть даже в какой-то степени неправльным, хотя на самом деле не так уж часто он бывает очень неправильным". Как формируется контур? Пойа поясняет: "Я редко расстаюсь со своими наручными часами, но когда это случается, у меня всегда появляется забота о том, как их найти. Потеряв свои часы, я по привычке начинаю их искать в некотором совершенно определённом месте: на своём письменном столе, или на какой-нибудь полке, где я обычно кладу свои мелкие вещи, или ещё в каком-нибудь третьем месте, если мне удалось вспомнить, что я снял часы именно там. Такое поведение типично. Как только мы серьёзно заинтересовались своей задачей, мы стараемся наметить контур, внутри которого следует искать решение. Этот контур может быть неопределённым, он может быть почти неосязаемым, но именно он определяет наши будущие действия. Конечно, попытки решения могут быть различными, но по существу же все они похожи друг на друга, все они лежат внутри этого заранее намеченного (возможно, не вполне сознательно) контура. Если ни одна из испробованных попыток не даёт результата, мы чувствуем себя обескураженными, ничто другое не приходит на ум; мы не в состоянии выйти за пределы намеченного контура. Ведь мы ищем не вообще какое-то решение, а вполне определённое решение, решение, которое должно находиться внутри нашего ограниченного контура. Мы не ищем решения где-то по всему свету, а внутри ограниченной области поисков".
Самый выносливый и терпеливый читатель, сумевший дойти до этого места, надеюсь, сможет по достоинству оценить простоту и глубину подхода Пойа. И всё же перед штурмом вершины (изложением схемы мышления, предложенной Пойа) давайте сделаем последний привал.
О решении задач как о процессе строительства. Пойа пишет: "Попробуем сравнить взгляды решающего математическую задачу в начале и в конце его работы. Когда задача только ещё возникла, картина проста: решающий видит её обособленной, либо без всяких подробностей, либо с очень малыми подробностями; возможно, что он различает только главные её части – неизвестные, данные и условие, или предпосылку и заключение. Картина же, которую он видит в конце, совсем другая: она сложна, снабжена такими дополнительными подробностями и деталями, о связи которых с рассматриваемой задачей решающий вначале и не подозревал… Откуда же берутся все эти материалы, вспомогательные элементы, теоремы и т.д.? Их накопил решающий в своей памяти, и теперь ему предстоит извлечь их оттуда и целенаправленно приспособить к решению своей задачи. Такое привлечение сведений мы будем называть мобилизацией, а их приспособление к решаемой задаче – организацией. Процесс решения задачи подобен строительству дома. Сначала нужно собрать необходимый материал, чего само по себе недостаточно: куча камней – это ещё не дом. Чтобы построить дом или решение, надо сложить части вместе и организовать их в целое, к которому мы стремимся. Практически мобилизацию невозможно отделить от организации; они дополняют друг друга как аспекты единого сложного процесса – процесса умственной работы, конечной целью которой является решение. Работа эта, если она проводится интенсивно, вводит в дело все наши материальные ресурсы, требует применения всей гаммы наших умственных способностей и содержит в себе неисчерпаемое множество аспектов. Возможно, нам следует здесь поддаться искушению и выделить некоторые операции из всего многообразия умственных операций, являющихся элементами умственной работы, и описать их в таких терминах, как изоляция и комбинация, распознавание и вспоминание, перегрупировка и пополнение".
Распознавание и вспоминание. Пойа так раскрывает эти понятия: "Решая задачу, мы бываем очень рады, если нам удаётся распознать какой-нибудь знакомый элемент. Так, например, при изучении геометрической фигуры мы можем обнаружить не замеченный ранее треугольник… Обнаружив, распознав этот треугольник, мы устанавливаем тем самым связь с обширной областью ранее приобретённых знаний, один из участков которой может оказаться в настоящий момент полезным. Таким образом, распознавание может, вообще говоря, побуждать нас к вспоминанию чего-то полезного для решения задачи, к мобилизации относящихся к рассматриваемому вопросу сведений".
Пополнение и перегруппировка. Пойа поясняет: "Мобилизованные нами потенциально полезные элементы, будучи присоединены к нашей концепции задачи, могут, вообще говоря, обогатить её, придать ей более законченный вид, ликвидировать пробелы, устранить её недостатки, одним словом, пополнить её. Иногда, однако, удаётся добиться значительного успеха в организации решения и без добавления нового материала за счёт одного лишь изменения расположения уже имеющихся элементов, путём изучения соотношения между ними в новой диспозиции, путём перестановки или перегруппировки их. Перегруппировав элементы, мы меняем "структуру" нашего понимания задачи. Итак, перегруппировка означает изменение структуры".
Изолирование и комбинирование. Пойа пишет: "При изучении сложного целого наше внимание может привлекать то одна, то другая деталь. Мы сосредоточиваемся на какой-то определённой детали, мы фокусируем на ней своё внимание, делаем на неё упор, выделяем её из её окружения – одним словом, изолируем её… После того как изучен ряд деталей и произведена соответствующая их переоценка, может снова возникнуть потребность представить себе всю ситуацию в целом… Комбинированный эффект переоценки роли некоторых деталей может вылиться в новую мысленную картину общей ситуации, новую, более гармоничную комбинацию всех деталей. Изолирование и комбинирование, дополняя друг друга, могут продвинуть процесс решения. Изолирование деталей приводит к распаду целого на части, а последующее комбинирование их снова объединяет части в целое, более или менее отличающее от исходного. Разлагая целое на составные части, а затем воссоединяя их по-иному, снова разлагая и снова воссоединяя по-иному, мы заставляем эволюционировать наше понимание задачи, переходя к более перспективной ситуации".
Ну вот мы и подошли к вершине нашего повествования. К той схеме, которую Джордж Пойа озаглавил "Как мы думаем" (с.253).

Вот его пояснения к диаграмме: "Мобилизация и организация представлены как противоположные концы одной и той же (горизонтальной) диагонали квадрата, так как практически эти операции дополняют друг друга. Мобилизация извлекает из нашей памяти относящиеся к делу элементы, а организация целенаправленно увязывает их друг с другом. Изолирование и комбинирование представлены как противоположные концы другой (вертикальной) диагонали, так как практически эти операции дополняют друг друга. Изолирование выделяет конкретную деталь из окружающего ее целого, комбинирование воссоединяет детали в осмысленное целое. Стороны, исходящие из вершины, отведенной мобилизации, помечены словами "распознайте" и "вспомните", так как практически мобилизация элементов, имеющих отношение к задаче, часто начинается с распознавания некоторого элемента, содержащегося в задаче, и заключается во вспоминании связанных с ним и уже знакомых нам других элементов. Стороны, исходящие из вершины, отведенной организации, помечены словами "пополните" и "перегруппируйте", так как практическая организация означает пополнение нашего понимания задачи, придание ему определенной законченности путем добавления новых деталей и ликвидации пробелов; она означает также перегруппировку, перестройку во всей нашей концепции задачи. Точно так же деталь, которую нам удалось вспомнить и которая оказалась полезной при комбинировании, обогащает наше понимание задачи и пополняет целое. В процессе решения задачи прозрение (или предвидение) является центром нашей деятельности; поэтому соответствующая точка помещена в центре нашего символического квадрата. Мы движемся, мобилизуя и организуя, изолируя и комбинируя, распознавая и вспоминая элементы различного вида, перегруппировывая и пополняя нашу концепцию задачи, стараясь предвидеть решение или какую-нибудь его характерную черту, или участок ведущего к нему пути. Если предвидение, прозрение приходит внезапно, подобно вспышке, то мы называем его вдохновением или блестящей идеей; обладание такой идеей — наше самое сокровенное желание".
Как нетрудно догадаться, эта схема подходит не только для решения математических задач. Она весьма универсальна, и всё предшествующее изложение задавало необходимый контекст, базис обоснования этой схемы. Анализируя его, можно прийти к выводу, что схема Пойа может быть полезна в самых разных областях интеллектуальной деятельности. В первую очередь, нас, разумеется, интересует сфера программирования. Однако, те, кто знаком с близкими областями (программирование человеческой деятельности — менеджментом), легко заметят, что схема Пойа весьма компактно представляет универсальный подход к решению задач и здесь. И её можно использовать в том числе для организации процесса создания сложных программных систем (включая и подход Open Research Programming).
В заключение моего пересказа с обширным цитированием приведу ещё одни важные слова Пойа. Он пишет: "Мы радуемся, когда наше понимание задачи оказывается хорошо сбалансированным и гармоничным, когда оно содержит все необходимые детали, и притом только хорошо знакомые детали… Наша концепция задачи кажется хорошо уравновешенной, если не ощущается необходимости в перегруппировке её элементов, она кажется внутренне согласованной, если не нужно вспоминать детали, если одна из них легко вызывает в памяти другие. Если нет необходимости в пополнении концепции задачи, она представляется нам законченной; если все детали распознаны, она кажется нам знакомой и близкой. Отчётливость в восприятии деталей обеспечивается их предварительной изоляцией и сосредоточением внимания на каждой из них в отдельности, а гармоничность концепции в целом является следствием удачной комбинации деталей. Мы говорим, что идея близка, когда чувствуем уверенное продвижение к тому, что можно назвать прозрением".
Пойа в своей книге в виде сносок-комментариев приводит ряд интересных цитат, которые привлекли его внимание. Некоторые, даже не сообщив об этом читателю, я самовольно под собственным углом зрения встроил в свой субъективный пересказ его книги с прицелом на последующее раскрытие своего видения природы программирования. Но две хотел бы выделить особо. Они прокладывают мостик к следующей моей заметке, которая, как и эта, будет носить вспомогательный характер, и потребуется в качестве важного приложения к моим мыслям о природе программирования.
Цитата из книги "The Age of Reason" (Baltimore, 1956) выдающегося американского просветителя, политического деятеля и публициста Томаса Пэна (Thomas Paine, 1739-1809), именем которого назван штат Пенсильвания: "Каждый исследователь, изучавший деятельность и развитие человеческого ума, основываясь на наблюдениях над собственным умом, не мог не заметить, что существуют две различные категории того, что называют мыслями: к первой относятся те, которые мы порождаем активно, посредством акта мышления, обдумывания, ко второй – те, которые вспыхивают в нашем сознании самопроизвольно. Я всегда почитал за правило общаться с этими добровольными пришельцами со всевозможной вежливостью и старался изучить, насколько мне позволяли мои способности, заслуживают ли они внимательного приёма; именно благодаря им я и приобрёл почти все знания, которые имею".
Косвенная ссылка на книгу "Афоризмы" немецкого физика и писателя Георга Кристофа Лихтенберга (1742-1799). Пойа пишет: "Лихтенберг как-то заметил, что не следует говорить "я думаю", но – "думается", подобно тому как говорят: "светает", "морозит". Лихтенберг утверждает, что существуют спонтанные акты мышления, которыми мы не можем управлять, подобно тому как мы не можем управлять великими силами природы. Мы могли бы сюда ещё добавить, что разум наш иногда ведёт себя подобно упрямой лошади или мулу – странному животному, к которому мы должны приноровиться и которого должны время от времени понукать, чтобы заставить его служить нам, ибо, вообще-то говоря, он довольно часто отказывает нам в своих услугах".
На мой взгляд, изложенный здесь материал (помимо чисто практической пользы в решении различных задач) в достаточно компактной форме позволяет осознать возможные подходы к программированию (включая и всевозможные методологии). Если отталкиваться от взглядов Пойа и проецировать их на сферу программирования, приходишь к мысли о том, что программирование стоит рассматривать гораздо шире, чем это обычно принято. Иными словами, обобщить программирование (не просто компьютерное) до уровня интеллектуальной деятельности, направленной на построение любых систем (не только компьютерных). О том, что под этим понимается и к какой пользе это может привести, мы поговорим несколько позже.

- Поделиться
- Ссылка

Яндекс.Директ

Фотошкола в Харькове! Жми! bk2s.com
Фотошкола Back2School! Максимум практики! Стоимость от 500грн! Заходи! Жми! Адрес и телефон
Скрыть объявление

Спасибо. Объявление скрыто.

Акция! Все книги от 10 грн. 0+ bookclub.ua
Уникальное предложение для новых клиентов. Кто еще не зарегистрировался? Адрес и телефон
Скрыть объявление

Спасибо. Объявление скрыто.

Пенсионная реформа в Украине ask.masterprav.com Помощь юриста. Консультация по телефону онлайн - доступно и бесплатно! Харьков
Скрыть объявление

Спасибо. Объявление скрыто.

Надоела реклама? Улучшите аккаунт всего за $1.66 месяц!
На день назад | На день вперёд

### Profile

  rbogatyrev
  rbogatyrev
  EuroProg

### Latest Month

Март 2009
Вс | Пн | Вт | Ср | Чт | Пт | Сб
--- | --- | --- | --- | --- | --- | ---
1 | 2 | 3 | 4 | 5 | 6 | 7
8 | 9 | 10 | 11 | 12 | 13 | 14
15 | 16 | 17 | 18 | 19 | 20 | 21
22 | 23 | 24 | 25 | 26 | 27 | 28
29 | 30 | 31 |  |  |  |

### Links

- * ОГЛАВЛЕНИЕ
- * Европейский центр
- * История Кронос
- * Оберон-технологии
- * Информатика-21
- * Мои публикации

Разработано LiveJournal.com
Designed by Paulina Bozek

# Журнал ЖЖ

- ### sestratk

  КОТИКИ ПЕНСИОННОГО ВОЗРАСТА. Как распознать первые признаки старения своего питомца

- ### Журнал ЖЖ

  ПУСТЬ ЗА НАС ПОВОЮЮТ МИГРАНТЫ. 36000 иностранцев погибли за мечту о французском гражданстве

- ### Журнал ЖЖ

  БОЧ ВОРОНИН И ДЕВОЧКА ПУТИН. Самые дикие имена современных детей

- ### Журнал ЖЖ

  БЕЗВИЗОВЫЙ КУСОЧЕК АМЕРИКИ. Здесь живут граждане США, лишённые права выбирать президента

- ### Журнал ЖЖ

  ОЧИСТИТЕЛЬНЫЙ ОТРЯД. Разъездная бригада старьевщиков освобождает горожан от хлама

- ### Журнал ЖЖ

  СБОИ В МАТРИЦЕ. Страны, где братья-сёстры Вачовски затерялись бы в толпе себе подобных

- ### Журнал ЖЖ

  ЗАТО КАК ВИСИТ! К 115-летию самого необычного в мире метро

- ### Журнал ЖЖ

  КУПОЛЬНАЯ КОНСТРУКЦИЯ. Как устроена противовоздушная оборона Москвы

- ### Журнал ЖЖ

  ПОГРЯЗНУТЬ В БОГАТСТВЕ. Парк, где посетители роются в земле в поисках алмазов

- ### Журнал ЖЖ

  ЗАДАЧА: ВЫЖИТЬ. Справляемся с «офисными» недугами и приятно повышаем работоспособность

Рекомендовать пост Порекомендовано Случайный блог

Вы уверены, что хотите удалить этот репост?

### Добавить в избранное

Выберите уровень приватности Изменить уровень приватности

- Публичный
- Только друзьям
- Личный

Все настройки