DRAKON.SU

Текущее время: Суббота, 19 Сентябрь, 2020 06:18

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Понедельник, 20 Август, 2012 17:07 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Жили-были два итальянца, два математика Коррадо Бом (англ. Corrado Böhm) и Джузеппе Якопини (Giuseppe Jacopini).

В 1966 году они опубликовали статью
Цитата:
Bohm, Corrado; and Giuseppe Jacopini (May 1966). «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM 9 (5): 366–371.
Статья вошла в историю.

В русской Википедии есть статья "Теорема Бома-Якопини". http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B8

В английской Википедии она называется "Structured program theorem", то есть Теорема структурного программирования.
http://en.wikipedia.org/wiki/Structured_program_theorem

В чем суть теоремы?

Английская Википедия отвечает:
Цитата:
It states that a given class of algorithms can compute any computable function if those algorithms combine subprograms in only three specific ways. In other words, any algorithm can be expressed using only three control structures. They are

1.Executing one subprogram, and then another subprogram (sequence)

2.Executing one of two subprograms according to the value of a boolean expression (selection)

3.Executing a subprogram until a boolean expression is true (iteration)


Русская Википедия говорит так:
Цитата:
Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления:
— последовательной (англ. sequence),
— ветвлений (англ. selection)
— и повторов или циклов (англ. repetition, cycle).


Вкратце можно сказать:
Цитата:
Любой алгоритм можно представить с помощью трех управляющих структур:
— последовательность;
— развилка;
— повторение (цикл).


Что было дальше?
Русская Википедия отвечает:
Цитата:
Публикация теоремы была толчком к началу дебатов о структурном программировании. Спустя 2 года вышла статья Эдсгера Дейкстры «Go To Statement Considered Harmful»[2], в которой он критиковал использование оператора GOTO и высказывался в пользу улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма.

http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B8

Английская Википедия говорит (примерно) то же самое.
Цитата:
The Böhm-Jacopini proof describes how to construct a structured flow chart from an arbitrary chart, using the bits in an extra integer variable to keep track of information that the original program represents by the program location.

This construction was based on Böhm's programming language P′′.

The Böhm-Jacopini proof did not settle the question of whether to adopt structured programming for software development, partly because the construction was more likely to obscure a program than to improve it.

On the contrary, it signalled the beginning of the debate.

Edsger Dijkstra's famous letter, "Go To Statement Considered Harmful," followed in 1968.

Subsequent proofs of the theorem addressed practical shortcomings of the Böhm-Jacopini proof with constructions that maintained or improved the clarity of the original program.[3]


Что думает большинство программистов по этому вопросу?

Мне кажется, что большинство программистов думает что-нибудь в таком стиле:
Цитата:
Структурная теорема Бома-Джакопини — хорошая вещь. Но, если очень хочется, иногда можно использовать оператор передачи управления GOTO или его заменители.


Таким образом, сухой остаток дискуссии, по-видимому, можно сформулировать так:
Цитата:
Любой алгоритм можно представить с помощью трех управляющих структур:
— последовательность;
— развилка;
— повторение (цикл);
— Но! Если очень хочется, иногда можно добавлять к этому списку (или не добавлять) оператор передачи управления.

Конец первой части. Занавес опускается.

==================================

Часть вторая. Занавес поднимается.

До сих пор речь шла только о программировании.
Поэтому теорема Бома-Джакопини была мало кому известна. Точнее, она была известна узкому кругу программистов. И не более того.

В какое-то время (никто не знает, в какое именно) возник вопрос.

А нельзя ли посмотреть на эту теорему в более широком масштабе?
В масштабе всего человечества?


То есть выйти за узкие рамки программирования и проанализировать (осмысленную) деятельность всех людей на Земле.
А не только деятельность программистов.

Продолжение следует


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Понедельник, 20 Август, 2012 20:26 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
Жили-были два итальянца, два математика Коррадо Бом (англ. Corrado Böhm) и Джузеппе Якопини (Giuseppe Jacopini).

В 1966 году они опубликовали статью
Цитата:
Bohm, Corrado; and Giuseppe Jacopini (May 1966). «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM 9 (5): 366–371.
Статья вошла в историю.

В русской Википедии есть статья "Теорема Бома-Якопини". http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B8

В английской Википедии она называется "Structured program theorem", то есть Теорема структурного программирования.
http://en.wikipedia.org/wiki/Structured_program_theorem

В чем суть теоремы?

Английская Википедия отвечает:
Цитата:
It states that a given class of algorithms can compute any computable function if those algorithms combine subprograms in only three specific ways. In other words, any algorithm can be expressed using only three control structures. They are

1.Executing one subprogram, and then another subprogram (sequence)

2.Executing one of two subprograms according to the value of a boolean expression (selection)

3.Executing a subprogram until a boolean expression is true (iteration)


Русская Википедия говорит так:
Цитата:
Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления:
— последовательной (англ. sequence),
— ветвлений (англ. selection)
— и повторов или циклов (англ. repetition, cycle).

Вот ничё себе ВП заливает... я до сих пор знал эту теорему в другой формулировке:
Цитата:
Для любой программы, выраженной блок-схемой с одним входом и одним выходом, можно построить эквивалентную программу, т.е. выполняющую те же преобразования исходных данных в результаты с помощью тех же вычислений, единственными управляющими структурами в которой являются цепочка и цикл с предусловием.
:wink: (цит. по: Свердлов С.З. ЯП и МТ. - С. 71)
Интересно, к чему придём, начав с этого?..
Владимир Паронджанов писал(а):
До сих пор речь шла только о программировании.
Поэтому теорема Бома-Джакопини была мало кому известна. Точнее, она была известна узкому кругу программистов. И не более того.
В какое-то время (никто не знает, в какое именно) возник вопрос.
А нельзя ли посмотреть на эту теорему в более широком масштабе?В масштабе всего человечества?
То есть выйти за узкие рамки программирования и проанализировать (осмысленную) деятельность всех людей на Земле.
А не только деятельность программистов.
Ну ясно - речь пойдёт о маршрутах деятельности, представляемых в информатике для произвольного исполнителя, а не только для "языковых машин". И не вкатать ли нам туда явные БП?
Да ясное дело - вкатать в частном случае из общего универсума. Только при некоторых условиях, намеченных, допустим, здесь:
Владимир Паронджанов в viewtopic.php?p=73756#p73756 писал(а):
...
Если схема "выращена из цикла", то есть выведена из аксиомы (из заготовки-примитив) с помощью правил логического вывода, то это значит, что схема строго доказана математически (так как она получена с помощью правил вывода математической логики).

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

ИТАК, В ЧЕМ ЖЕ РАЗНИЦА?

В первом случае используется доказательное программирование. Имеем гарантированно правильный результат.

Во втором случае про доказательное программирование надо забыть. Про гарантии правильности тоже.
- т.е. от структурности зависит применимость дедуктивной верификации как одного из направлений формальной.
Можно ли неструктурное тем не менее формально верифицировать? Вроде да - проверкой моделей - другим направлением. Но вот было замечание Александра Сергеевича недавно по правомерности способов построения моделей для проверки... над которым надо подумать...

А не забыть ли нам про гарантии вообще?.. дабы "вошёл сюда не знающий геометрии" (т.е. не владеющий математикой информатик продолжал ничтоже сумняшеси браться за любые задачи)?.. А тут надо напомнить вот что:
Владислав Жаринов в viewtopic.php?p=72358#p72358 писал(а):
...
Предметно можно показать на примере, который используют те же Поликарпова и Шалыто в своей книге - на программных часах-будильнике. Как создавать программу их работы?
Прежде всего заметим - создавать для конкретной парадигмы программирования и представления об исполнителе ("спецификации структуры" в терминах их работы). Т.е. ненимперативные сставляющие непренебрежимы. Далее - создавать вместе с руководством пользователя (вытекающим из нормальной постановки задачи как целого - с последующим выделением "машинной" части). Сие ни от формы записи, ни от реализующих структур ещё не зависит. Только от технологической дисциплины разработки...

    А вот дальше вопрос - "сразу правильно" или "из общих слов"? И тут надо вспомнить - для чего предназначены часы-то?

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

    Если же чтобы показывать время на пульте системы, от которой мало-мальски жизнь/здоровье/благосостояние людей/природы зависит - то тут выбор может только перед "варваром" по Зелинскому ("гоблином" по Голубицкому с поправками отсюда: viewtopic.php?p=71257#p71257) стоять... :wink: :| Для адекватного гражданина сочинителя (ну или хотя бы опасающегося последствий, указанных Голубицким :wink:) нет вопроса - "сразу правильно".
    То же и для случая, когда от пользования часами как-то косвенно будет зависеть эффективность/надёжность пользователя в "кризисных" делах. Скажем, если употреблять часы дома, но чтобы вставать на серьёзную работу... или уже в личной жизни - чтобы не опоздать на свидание... :)

Короче - не нужен переход. Нужно сразу работать либо в неатомарном представлении структур управления (применительно к графической форме - допускающем многоадресный силуэт и пересадки, дающие goto), либо в атомарном. Второе однозначно требуется для "кризисных задач".
...
- и в кризисных задачах нам нужен аналитик:
Владислав Жаринов в viewtopic.php?p=73876#p73876 писал(а):
...
И вот тут снова вспоминаем, что у нас роолевая триада формализации. Что тогда? Аналитик должен сформулировать цель доказательства - опираясь на требования, предъявляемые к решению задачи предметником. Требования к программе оказываются частью задачных - и связаны с тем, что возлагается при решении на человека. Многое зависит от того, качественно ли предметник задал требования. И вот тут, если тип мышления предметника образный - то переход к графовой записи дествительно может помочь. А это, видимо, часто так. Тогда как аналитику - по сути, логику и математику - по своей роли важно, чтобы предметник максимально чётко объяснил, что требуется от решения заадачи - и если предметнику нужно для этого перевести структурную часть в граф, то это, конечно, д.б. обеспечено.
    Притом аналитик может иметь тип мышления текстовый, "символьный". И ему или всё равно, граф или нет - или даже сложнее, если он тяготеет к тексту. Так что уже здесь м.б. не лишним изоморфная текстовая запись...
Если аналитика не выделяем - то уже придётся для эффективной работы требовать от предметника и программиста примерно равных логико-математической культуры и типа мышления. Что, разумеется, практически далеко не всегда достижимо. Потому и Усов опять же говорил:
alexus в viewtopic.php?p=52774#p52774 писал(а):
Драконограф писал(а):
alexus: Талантливый инженер не обязан быть хорошим токарем. И не факт, что талантливый токарь станет хорошим инженером. А создание систем - это инженерная прерогатива...
Т.е. Вы подразумеваете, что аналитика выбрасывать из связки с заказчиком и программистом нельзя?
Как минимум, не надо этого делать...
...
Так что ещё раз - эргономическая поддержка формального мышления это одно, а методы формального мышления - другое... И введение новых форм записи, когда они адекватны типам мышления, не отменяет необходимости формально мыслить в тех ролях, где это нужно...
...
- а формальное мышление по поводу неструктурных программ реалистично, как уже говорил, именно в направлении проверки моделей. Т.е. имитомоделированием исполнения при заданных логических требованиях. Формулировка которых тоже требует логико-математической культуры...

Если же команда разработчиков ничего, кроме "от-лажи-вания" ((С) Усов) не умеет - сомнительно избежать "кризисных" ошибок...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 09 Сентябрь, 2012 12:24 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Владислав Жаринов писал(а):
Вот ничё себе ВП заливает... я до сих пор знал эту теорему в другой формулировке:
Цитата:
Для любой программы, выраженной блок-схемой с одним входом и одним выходом, можно построить эквивалентную программу, т.е. выполняющую те же преобразования исходных данных в результаты с помощью тех же вычислений, единственными управляющими структурами в которой являются цепочка и цикл с предусловием.
:wink: (цит. по: Свердлов С.З. ЯП и МТ. - С. 71)


Уважаемый Владислав!

Ваше сообщение неполное и не совсем точное. Оно не позволяет выявить историческую значимость теоремы Бома-Якопини.
И роль этой теоремы в становлении структурного программирования.


Чтобы это понять, надо ответить на на следующие вопросы:

1. Почему в русской Википедии теорема подается как «Теорема Бома-Якопини», http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B8
а в английской как «Structured program theorem» (Теорема структурного программирования) http://en.wikipedia.org/wiki/Structured_program_theorem

2. Может ли Теорема структурного программирования говорить только о цепочке и цикле с предусловием, как говорит Свердлов?

А где же ветвление? Или структурное программирование должно обходиться без ветвления? И т.д.

        Мое предположение состоит в том, что Теорема структурного программирования (как она описана в английской и русской Википедии) является Следствием оригинальной теоремы Бома-Якопини.

        Поскольку Следствие является прагматически более важным, чем оригинальная теорема, почетное звание «Structured program theorem» (Теорема структурного программирования) незаметно перекочевало от оригинальной теоремы к Следствию.

Мое предположение подтверждается тем, что в Википедии в статье «Структурное программирование» есть текст:

Цитата:
Теорема о структурном программировании:

Основная статья: Теорема Бома-Якопини

Любую схему алгоритма можно представить в виде композиции вложенных блоков begin и end, условных операторов if, then, else, циклов с предусловием (while) и может быть дополнительных логических переменных (флагов).

Эта теорема была сформулирована итальянскими математиками К. Бомом и Дж. Якопини в 1966 году и говорит нам о том, как можно избежать использования оператора перехода goto.

http://ru.wikipedia.org/wiki/%D0%A1%D1% ... 0%B8%D0%B5

Цитата:
Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops – in contrast to using simple tests and jumps such as the goto statement which could lead to "spaghetti code" which is both difficult to follow and to maintain.

It emerged in the 1960s, particularly from work by Böhm and Jacopini,[1] and a famous letter, Go To Statement Considered Harmful, from Edsger Dijkstra in 1968[2]—and was bolstered theoretically by the structured program theorem, and practically by the emergence of languages such as ALGOL with suitably rich control structures.

Theoretical foundation

The structured program theorem provides the theoretical basis of structured programming. It states that three ways of combining programs—sequencing, selection, and iteration—are sufficient to express any computable function.

This observation did not originate with the structured programming movement; these structures are sufficient to describe the instruction cycle of a central processing unit, as well as the operation of a Turing machine.

Therefore a processor is always executing a "structured program" in this sense, even if the instructions it reads from memory are not part of a structured program.

However, authors usually credit the result to a 1966 paper by Böhm and Jacopini, possibly because Dijkstra cited this paper himself.
[/quote]
http://en.wikipedia.org/wiki/Structured_programming

В литературе по этому вопросу имеется разброс мнений.
Например:
http://nigma.ru/index.php?startpos=10&s ... 0%B2%D0%B5

Уважаемые коллеги!

Если кто-либо может прояснить проблему, связанную с оригинальной теоремой Бома-Якопини и постепенным (или не постепенным) превращением ее в Теорему структурного программирования, просьба поделиться знаниями.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 09 Сентябрь, 2012 13:24 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
По источникам в Сети прежде всего видно, что и сейчас теорему Б-Я дают в двух разных формулировках. Причём в Свердлове (и ещё где-то) при изложении (видимо, более полном) указывают, что в доказательстве употребляются три базовых формы, а в формулировке теоремы - указывается на достаточность двух. Т.о. история, видимо, примерно такова. А следствие следует из доказательства... :)
Что достаточно двух - нетрудно вывести из смысла цикла Дейкстры как "паттерна универсальной программы" - все линейные участки переписываемой "из трёх" программы подставляем как тела ЦД-ветвей, выводим такие охраны, чтобы получались все "варианты использования" переписываемой... и порядок (только выводить м.б. сложно). А сам ЦД может получаться как гнездование циклов строго определённым образом - что в Драконографике показано.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Вторник, 11 Сентябрь, 2012 15:04 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Расследуя "дело" Бома-Якопини, я нашел интересную работу Харлана Миллса.

Конечно, все знают, кто такой Harlan D. Mills (1919-1996).

А если кто забыл, вот статья в Википедии
http://en.wikipedia.org/wiki/Harlan_Mills

А вот список его работ
http://www.informatik.uni-trier.de/~ley ... an_D=.html
_______________________________________________

Вот обещанная работа Миллса.
http://trace.tennessee.edu/cgi/viewcont ... 0harlan%22

Цитата:
MATHEMATICAL FOUNDATIONS FOR STRUCTURED PROGRAMMING
by Harlan D. Mills
February 1972


В этой работе дается ответ на два вопроса:

1. Что такое теорема Бома-Якопини?
2. Что такое структурная теорема?

ТЕОРЕМА БОМА-ЯКОПИНИ

На стр. 4 Харлан Миллс пишет:
Цитата:
a ''Structure Theorem'', due in original form to Bohm and Jacopini,
guarantees that any flowchartable program logic can be represented by
expansions of as few as three types of structures, e.g., (1) f THEN g,
(2) IF p THEN f ELSE g, (3) WHILE p DO f, where f, g, are flowcharts ,
with one input and one output, p is a test, THEN, IF, ELSE, WHILE, DO,
are logical connectives.


Перевод:
Цитата:
Структурная теорема, сформулированная Бомом и Якопини,
гласит: любая программа, заданная в виде блок-схемы, может быть представлена с помощью трех типов структур:

(1) f THEN g,
(2) IF p THEN f ELSE g,
(3) WHILE p DO f,

где f, g это блок-схемы с одним входом и одним выходом,
р это проверка,
THEN, IF, ELSE, WHILE, DO это логические связки.


СТРУКТУРНАЯ ТЕОРЕМА ХАРЛАНА МИЛЛСА

На стр. 31 Харлан Миллс формулирует и доказывает свою собственную структурную теорему:
Цитата:
STRUCTURE THEOREM

Any proper program is equivalent to a program whose formula contains at
most the graph labels BLOCK, IFTHENELSE, and DOUNTIL, and additional
functions TRUE, FALSE, POP and predicate function TOP.

где BLOCK — это последовательность, или цепочка.
Остальные обозначения Харлан Миллс дает на стр. 28.

ВЫВОДЫ

1. Харлан Миллс использует термин (вводит понятие) "Структурная теорема" (STRUCTURE THEOREM).

2. Он применяет это понятие как для теоремы Бома-Якопини, так и для своей собственной теоремы.

3. Обе теоремы близки по смыслу, хотя и не совпадают.

4. Харлан Миллс опубликовал свою работу в качестве отчета фирмы IBM в 1972 году, то есть на 4 года позже, чем Бом и Якопини.

5. Миллс в явной форме ссылается на Бома-Якопини как на оригинал. Он, в частности, пишет:
Цитата:
a ''Structure Theorem'', due in original form to Bohm and Jacopini


6. Структурную теорему Миллса можно рассматривать как развитие и обобщение теоремы Бома-Якопини.

7. Роль Харлана Миллса в Википедии в статье Structured Programming оценена высоко
Цитата:
Structured programming theorists gained a major ally in the 1970s after IBM researcher Harlan Mills applied his interpretation of structured programming theory to the development of an indexing system for the New York Times research file.

The project was a great engineering success, and managers at other companies cited it in support of adopting structured programming, although Dijkstra criticized the ways that Mills's interpretation differed from the published work.
http://en.wikipedia.org/wiki/Structured_programming

8. Можно предположить, что термин "Structured program theorem" произошел от термина Миллса "Structure theorem"
http://en.wikipedia.org/wiki/Structured_program_theorem

===================================

Уважаемые коллеги!

Если Вы обнаружите ошибку или неточность в моем сообщении, просьба меня поправить.
Спасибо


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Четверг, 13 Сентябрь, 2012 14:36 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Вернемся к началу темы и кое-что повторим.

Жили-были два итальянца, два математика: Коррадо Бом (англ. Corrado Böhm) и Джузеппе Якопини (Giuseppe Jacopini).

В 1966 году они опубликовали статью
Цитата:
Bohm, Corrado; and Giuseppe Jacopini (May 1966). «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM 9 (5): 366–371.
Статья вошла в историю.

В русской Википедии есть статья "Теорема Бома-Якопини". http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B8

В английской Википедии она называется "Structured program theorem", то есть Теорема структурного программирования.
http://en.wikipedia.org/wiki/Structured_program_theorem

В чем суть теоремы?

Английская Википедия отвечает:
Цитата:
... any algorithm can be expressed using only three control structures. They are

1.Executing one subprogram, and then another subprogram (sequence)

2.Executing one of two subprograms according to the value of a boolean expression (selection)

3.Executing a subprogram until a boolean expression is true (iteration)


Русская Википедия говорит так:
Цитата:
... любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления:
— последовательной (англ. sequence),
— ветвлений (англ. selection)
— и повторов или циклов (англ. repetition, cycle).


Вкратце можно сказать:
Цитата:
Любой алгоритм можно представить с помощью трех управляющих структур:
— последовательность;
— разветвление (выбор);
— повторение (цикл).


Конец первой части. Занавес опускается.

==================================

Часть вторая. Занавес поднимается.

До сих пор речь шла только о программировании.
Поэтому теорема Бома-Якопини была мало кому известна. Точнее, она была известна узкому кругу программистов.

Со временем возник вопрос.

А нельзя ли посмотреть на эту теорему в более широком масштабе?
В масштабе всего человечества?


То есть выйти за узкие рамки программирования и проанализировать (осмысленную) деятельность всех людей на Земле.
А не только деятельность программистов.

Оказывается, можно.
Цитата:
Любую целенаправленную человеческую деятельность можно описать с помощью трех управляющих структур:
— последовательность действий;
— разветвление действий;
— повторение действий (цикл).


Данная формулировка представляет собой обобщенную теорему Бома-Якопини.

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

Примечание.Речь разумеется, идет только о процедурном знании и не затрагивает декларативное знание.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 16 Сентябрь, 2012 09:15 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Продолжим рассуждения.

Добавим к списку еще две позиции:
— параллельные действия;
— вставка действий (которая обеспечивает декомпозицию).

В результате получим Следствие из обобщенной теоремы Бома-Якопини:

Цитата:
Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):

          — последовательность действий;
          — параллельные действия;
          — разветвление действий;
          — повторение действий (цикл);
          — вставка действий.
.
Формулировка Следствие из обобщенной теоремы Бома-Якопини является правильной. Но для простоты ее можно сократить. И ограничиться краткой формулировкой Теорема Бома-Якопини.

Эта краткая формулировка подчеркивает самое главное — тот факт, что приоритетом в исследовании данной проблемы обладают итальянские ученые Коррадо Бом (Corrado Böhm) и Джузеппе Якопини (Giuseppe Jacopini).

В итоге получим:
Цитата:
Теорема Бома-Якопини

Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):

          — последовательность действий;
          — параллельные действия;
          — разветвление действий;
          — повторение действий (цикл);
          — вставка действий.
.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 16 Сентябрь, 2012 13:53 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
Продолжим рассуждения.

Добавим к списку еще две позиции:
— параллельные действия;
— вставка действий (которая обеспечивает декомпозицию).

В результате получим Следствие из обобщенной теоремы Бома-Якопини:
...
Формулировка Следствие из обобщенной теоремы Бома-Якопини является правильной. Но для простоты ее можно сократить. И ограничиться краткой формулировкой Теорема Бома-Якопини.

Эта краткая формулировка подчеркивает самое главное — ...
... что Бом и Якопини рассматривали также параллельные действия и процедуры?.. А это из каких источников следует?.. я в таком виде встречал только в стандарте 8631-94 (Разд. 3)... но там контекст не точно такой, и научные обоснования в силу жанра документа отсутствуют...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 16 Сентябрь, 2012 14:41 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
Владислав Жаринов писал(а):
... что Бом и Якопини рассматривали также параллельные действия и процедуры?.. А это из каких источников следует?..

Уважаемый Владисав!

Вы правы, Бом и Якопини НЕ рассматривали параллельные действия и процедуры.
Ни в каких источниках этого нет.

Эти рассуждения провел я.
Я сделал следующее:

Шаг 1. Распространил идею Бома и Якопини на любую целенаправленную человеческую деятельность.

Шаг 2. Добавил к списку признаков параллельные действия и вставку действий.

Мне кажется, что эти два шага являются очевидными. Они непосредственно вытекают из теоремы Бома-Якопини и являются ее следствиями.

Поэтому приписывать эти два шага Паронджанову, по моему мнению, неправильно.

Я считаю, что приоритет как самой Теоремы, так и ее обобщения и следствия должен принадлежать Бому и Якопини.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Воскресенье, 23 Сентябрь, 2012 22:09 

Зарегистрирован: Воскресенье, 09 Март, 2008 22:38
Сообщения: 341
Уважаемый Владимир Даниелович!

Владимир Паронджанов писал(а):
В результате получим Следствие из обобщенной теоремы Бома-Якопини:
Цитата:

Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):
          — последовательность действий;
          — параллельные действия;
          — разветвление действий;
          — повторение действий (цикл);
          — вставка действий.
.


Мне кажется, это (выше) - весьма важная вещь! И она, несомненно, должна быть опубликована!

Более того, из нее может быть масса важных следствий в самых различных предметных областях!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Понедельник, 24 Сентябрь, 2012 10:56 

Зарегистрирован: Понедельник, 09 Август, 2010 22:28
Сообщения: 128
Владимир Паронджанов писал(а):
В результате получим Следствие из обобщенной теоремы Бома-Якопини:
Цитата:

Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):
— последовательность действий;
— параллельные действия;
— разветвление действий;
— повторение действий (цикл);
— вставка действий.


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

http://lamp.tu-graz.ac.at/~hadley/uncom ... mbers.html


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Понедельник, 24 Сентябрь, 2012 12:00 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Ну, тут как раз водораздел между математикой и информатикой всё тот же проявляется... (и соответствующими стадиями моделирования/формализации)... :)

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

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


Последний раз редактировалось Владислав Жаринов Понедельник, 24 Сентябрь, 2012 12:16, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Понедельник, 24 Сентябрь, 2012 12:13 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Со сказанным, что интересно, сопрягается и это:
TAU в viewtopic.php?p=74986#p74986 писал(а):
Мне кажется, это (выше) - весьма важная вещь! И она, несомненно, должна быть опубликована!

Более того, из нее может быть масса важных следствий в самых различных предметных областях!
- в том смысле, что это уже осознано. И опубликовано. Если говорить только об Оберонкоре - то, например, здесь: viewtopic.php?p=66609#p66609 - в отношении параллелизма и его обобщения за пределы работы с данными.
Но то же самое мы видим и в упомянутом стандарте - правда, ещё применительно к программам. В то же время можно предположить, что разработчики задали такие структуры программных конструктивов и их понимание не случайно... :wink:

И вот представляется интересным найти по источникам - когда, в какой сфере деятельности сформулировано такое следствие? На что при этом опирались авторы?

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Пятница, 28 Сентябрь, 2012 14:40 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Да, действительно распространено представление граф-схемами на произвольную деятельность было в инженерной психологии. Кое-что можно найти в "Хрестоматии по ИП", которую уже упоминал - на с. 123-137.
Там, кстати, тоже в первую очередь из нелинейных структур именно циклы рассматриваются...
Есть и связка с моделями производственных мощностей (предметно-функциональными).
Понятие именно программного конструктива в стандарте тоже можно объяснить - семантика параллельного исполнения для последовательного исполнителя есть квазиалгоритм. Который ещё надо сериализовать... чем и занимается, скажем, "многозадачная" ОС на машине, число процессоров (ядер) которой меньше, чем максимальное число рабочих точек в составляемых для неё программах...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Суббота, 29 Сентябрь, 2012 10:40 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
В сообщении viewtopic.php?p=74986#p74986 Андрей Александрович TAU писал(а):
.
Владимир Паронджанов писал(а):
В результате получим Следствие из обобщенной теоремы Бома-Якопини:
Цитата:

Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):
          — последовательность действий;
          — параллельные действия;
          — разветвление действий;
          — повторение действий (цикл);
          — вставка действий.
.


Мне кажется, это (выше) - весьма важная вещь! И она, несомненно, должна быть опубликована!

Более того, из нее может быть масса важных следствий в самых различных предметных областях!


Уважаемый Андрей Александрович!

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

На втором этапе теоретического осмысления речь идет о распространении первоначального результата и получении, как Вы совершенно справедливо указываете,
Цитата:
массы важных следствий в самых различных предметных областях!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Суббота, 29 Сентябрь, 2012 12:14 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4831
Откуда: Москва
usr345 писал(а):
Владимир Паронджанов писал(а):
В результате получим Следствие из обобщенной теоремы Бома-Якопини:
Цитата:

Любую целенаправленную человеческую деятельность можно описать с помощью пяти приемов (управляющих структур):
— последовательность действий;
— параллельные действия;
— разветвление действий;
— повторение действий (цикл);
— вставка действий.


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

http://lamp.tu-graz.ac.at/~hadley/uncom ... mbers.html


Уважаемый usr345!

Я согласен с Вами во всем, кроме одного пункта.
Я полностью согласен с утверждениями в статье по Вашей ссылке, в частности, с этим:
Цитата:
The equations that describe the weather are known to do this. This means that predicting the weather arbitrarily far into the future is impossible without knowing the current conditions (temperature, air pressure, humidity, wind speed, etc.) to arbitrary precision. Since the quantities that describe the weather are real numbers, they are uncomputable. No finite computer program can calculate the weather arbitrarily far into the future.

If the universe is a machine where the future is uniquely determined by its present state, it would not be possible to calculate what the future will be.


А с чем я не согласен? С Вашим утверждением
Цитата:
Вообще говоря, это утверждение не верно.
Почему я не согласен? Объясню на примере прогноза погоды.

1. Прогноз погоды есть целенаправленная человеческая деятельность.

2. Люди не дураки. И делают только то, что возможно.

3. Что невозможно, то люди не делают.

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

5. Человеческую деятельность, направленную на достижение НЕосуществимых (то есть НЕвозможных целей) нельзя назвать ЦЕЛЕНАПРАВЛЕННОЙ. Такая деятельность бессмысленна.
Она бессмысленна потому, что цель НЕДОСТИЖИМА.

6. С учетом этих разъяснений можно утверждать, что Следствие из обобщенной теоремы Бома-Якопини является верным.

Вы согласны?
Или у Вас есть возражения?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Суббота, 29 Сентябрь, 2012 12:29 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 189
Откуда: Россия, Санкт-Петербург
Владимир Паронджанов писал(а):
2. Люди не дураки. И делают только то, что возможно.

3. Что невозможно, то люди не делают.

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

5. Человеческую деятельность, направленную на достижение НЕосуществимых (то есть НЕвозможных целей) нельзя назвать ЦЕЛЕНАПРАВЛЕННОЙ. Такая деятельность бессмысленна.
Она бессмысленна потому, что цель НЕДОСТИЖИМА.
Как философ по образованию, не могу согласиться ни с одним из этих пунктов.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Среда, 03 Октябрь, 2012 10:44 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1082
Откуда: Россия, Чебоксары
Александр Ильин писал(а):
Как философ по образованию, не могу согласиться ни с одним из этих пунктов.
Поддерживаю.
Хотя бы просто потому, что "невозможность" априори неизвестна, да и строго недоказуема в общем случае :)

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

Кроме того, есть замечания опять же по строгости формулировок.
Все эти вставки и разветвления - понятия чисто алгоритмические. Никакого отношения к человеческой деятельности не имеющие.
Фактически здесь утверждается: "Любую человеческую деятельность можно описать алгоритмически".
Всё остальное - несущественные технические подробности!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Среда, 03 Октябрь, 2012 13:04 

Зарегистрирован: Понедельник, 09 Август, 2010 22:28
Сообщения: 128
Владимир Паронджанов писал(а):
Продолжим рассуждения.

Добавим к списку еще две позиции:
— параллельные действия;
— вставка действий (которая обеспечивает декомпозицию).



Я думаю, что эти 2 позиции вставлять не надо. Я придерживаюсь позиции математиков, что аксиом должно быть минимум.

1. Если вы посмотрите оригинальную формулировку теоремы, то там написано: "1.Executing one subprogram, and then another subprogram (sequence)". Subprogram - это не обязательно атомарное действие и соответствует вашей вставке. Поэтому этот пункт предлагаю убрать как дублирующий 1-й пункт теоремы.

2. Насчет параллелизма у меня тоже сомнения. Ведь любой параллельный алгоритм при наличии одного исполнителя сводится к последовательному. И если принять мой постулат о минимальном наборе букв в алфавите описания алгоритмов, то достаточно 3-х. А распараллелить алгоритм мы можем, взяв некоторую процедуру, разбив внутри неё множество входных данных на подмножества и передав их соответствующим исполнителям. Результаты работы исполнителей собираются и возвращаются из процедуры. Но процедура все равно выглядит как единое целое.

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

Alexey_Donskoy писал(а):
Фактически здесь утверждается: "Любую человеческую деятельность можно описать алгоритмически".
Всё остальное - несущественные технические подробности!


Я тоже вначале прочитал утверждение Владимира Даниловича именно так. И думаю, что это утверждение ложно. Для этого даю цитату из книги Роджера Пенроуза: "Тени разума". Здесь Пенроуз размышляет о следствиях из теоремы Геделя о неполноте:

Цитата:
Среди положений, которые со всей неоспоримостью доказал Гёдель, имеется следующее: нельзя создать такую формальную систему лоrически обоснованных математических доказательств, которой было бы достаточно, хотя бы в принципе, для доказательства всех истинных теорем элементарной арифметики. Уже и это само по себе в высшей степени удивительно, однако это еще не все. Mнoroe rоворит за то, что результаты Гёделя демонстрируют нечто большее, а именно, доказывают,что способность человека к пониманию и постижению сути вещей невозможно свести к какому бы то ни было набору правил. Иными словами, нельзя создать такую систему правил, которая оказалась бы достаточной для доказательства даже тех арифметических положений, истинность которых, в принципе доступна для человека с ero интуицией и способностью к пониманию, а это означает, что человеческие интуицию и понимание невозможно свести к какому бы то ни было набору правил...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: От Бома-Якопини до ДРАКОНа
СообщениеДобавлено: Среда, 03 Октябрь, 2012 13:28 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1082
Откуда: Россия, Чебоксары
usr345 писал(а):
Я тоже вначале прочитал утверждение Владимира Даниловича именно так. И думаю, что это утверждение ложно. Для этого даю цитату из книги Роджера Пенроуза: "Тени разума". Здесь Пенроуз размышляет о следствиях из теоремы Геделя о неполноте:
Цитата:
именно на теореме Гёделя основывается мое доказательство неизбежности наличия в человеческом мышлении составляющей, которую никоrда не удастся воспроизвести с помощью компьютера
Давайте не будем заниматься демагогией. Разберёмся по существу:
1) Перечисление "управляющих структур" по сути относились не к человеческой деятельности, а к формализации алгоритмов.
2) До сих пор тут идут рассуждения о том, достаточно ли перечисленных структур для формализации любого алгоритма.
3) Утверждение о том, что указанное подмножество структур достаточно для описания любой человеческой деятельности, со всей очевидностью не лезет ни в какие ворота (потому что неизвестно, сводится ли деятельность человеческая к алгоритмической? Или она настолько проще алгоритмической, что хватит и подмножества структур?)
4) Утверждение о неформализуемости человеческого мышления также слабо относится к вышесказанному. Но, как минимум, оно говорит о том, что никакого набора "управляющих структур" для описания человеческой деятельности НЕ ХВАТИТ.

В результате я вообще не понимаю, о чём Вы говорите - одни противоречия :)

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

А управляющих алгоритмических структур (базовых, и причём для одного исполнителя!) на самом деле всего 4:
- старт (событие);
- последовательность;
- разветвление (выбор варианта);
- свёртка (механизм вызова подпрограммы).

Всё остальное - от лукавого. То есть не надо здесь изобретать ничего лишнего - всё остальное моделируется указанными четырьмя. И эти четыре - необходимы и достаточны.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2020, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB