DRAKON.SU

Такое соответствие (требование) не связано с потенциальной осуществимостью.

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

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

А соответствие системы команд алгоритма системе команд исполнителя - это
разновидность общего требования выполнимости (осуществимости) процесса, заданного алгоритмом:
в смысле - нельзя (бесполезно) задавать невыполнимые алгоритмы (а также команд, распоряжения и т.п.)

Давайте вернемся к соответствию системы команд алгоритма системе команд исполнителя.
У Вас где-то в одном из предшествующих постов по этому поводу было замечание типа:
это означает относительность понятия алгоритма - алгоритм относительно исполнителя.
В этом смысле очень даже согласен с Вами. Я тоже давно так думаю:
-- для школьника, знающего школьную алгебру, алгоритм вычисления гипотенузы - это алгоритм
(он по нему может работать);
-- а для школьника, еще не знающего школьную алгебру - это не алгоритм, а непонятная абракадабра.

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

Это что-то вроде алгоритмической разрешимости массовых математических проблем:
- если нашли общий алгоритм, то дело в шляпе - проблема разрешима,
- а если не нашли - ничего сказать определённо нельзя.

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

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

Средневековые схоласты, которые пытались логически обосновать наличие бога,
доказали только:
во-первых, что логика и вера (в бога) несовместимы;
во-вторых, что бог (если он есть) не всемогущий.

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

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

Это я понимаю. Только ко всему перечисленному опять надо присовокупить "дискретное", не так ли?

А вот насчёт любого преобразования информации - есть сомнения. Происходящие из определения информации.

Такое впечатление, что я совсем криво пишу, подразумевая больше, чем изложено? Нет? Тогда почему так трудно даются абстракции? Почему пропускаются ключевые тезисы, которые я даже выделил жирным шрифтом:

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

Вам никак не даётся абстракция пространства состояний?

Хороший пример. Давайте переведём его на язык рассматриваемой абстракции.
Дано: алгоритм вычисления гипотенузы.
Спецификации к алгоритму: входные данные (длины катетов), выходные данные (длина гипотенузы).
Всё или что-то забыли?

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

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

Что же с потенциальной осуществимостью? Ничего. Она как была, так и осталась!
То есть потенциально возможно найти (и мы нашли, даже постулировали) такое пространство состояний, в котором алгоритм осуществим.


Недостаточен уровень абстракции для анализа!

И система команд, и вычислительные ресурсы исполнителя - варьируемые (по крайней мере, теоретически) параметры.
Другими словами, мы можем предпринять поиск подходящего исполнителя для самых странных, "невыполнимых", команд.

Как ни странно, даже алгоритм с командами для волшебной палочки можно считать потенциально осуществимым, если в принципе возможно существование такого исполнителя, как "волшебная палочка"!

Это не филология, а как раз математика.

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

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


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

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

Не понял. Что "дифференциальное уравнение"? (Что у вас вообще за нездоровая тяга к ним?)
Или вы предлагаете ими информацию кодировать?

Каша у вас в голове.

Исходный посыл звучал так:

Основной инструмент физики - это что-то нездоровое?

Тогда давайте договариваться о терминах. Что такое "информация" в вашем понимании?

Может, вы всё-таки будете разговаривать корректно (в этическом смысле)?

Какой нам прок с этого инструмента в данной теме?
А если сейчас огородник какой зайдет и начнет лопатой махать? Это ведь его основной инструмент...

Или вы думаете, что стоит сказать "лопата" и все сразу начали понимающе кивать головами?
Так что будьте добры разъяснить к чему нам тут эта "лопата".


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


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

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

Что вас смутило?

Тык да. Но мы ведем разговор об описаниях.

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

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

А мне вполне достаточный уровень - чего тут неясного?

Причем тут математика, если, например, алгоритм технический - без математики, типа:
взять деталь;
установить в патрон;
подрезать торец на длине L1 = ...;
проточить диаметр D на длину L2;
и т.д.

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

Юрий Гуревич и Алан Тьюринг

https://en.wikipedia.org/wiki/Abstract_state_machines


Что такое ASM? Abstract State Machines

Видео. Юрий Гуревич Что такое алгоритм?

Специально привел весь пост целиком - для наглядности разговора.

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

1) Первичная классическая или фундаментальная теория алгоритмов.
Или по существу - это теория вычислимости (теория вычислений), включая:

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

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

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


2) Исторически вторичная неклассическая или прикладная теория алгоритмов
(или структурная теория алгоритмов).
В частности, в нее включается теория автоматов:
конечных автоматов (самые простые), магазинных автоматов и т.д.
Она указывается в аглицкой Википедии в одноименной статье по общим наименованием
"Теория алгоритмов" (Theory of algorithms - переключается на статью: Theory of computation):
там указывается теория автоматов - в дополнение к классике типа машин Тьюринга, ... и теории сложности.
То есть - тоже Теория вычислений, но она толкуется чуть шире, чем в совецкой Википедии.

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

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

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

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

Это слегка обработанная копия (цветом и т.п.) в формате pdf.
Оригинал веб-страницы в формате htm. не пропускается на форум.

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

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


С какой целью вы интересуетесь? Я программист 1С. Этих сведений достаточно?


Конкретно откройте учебник и посмотрите.

В Гугле можно набрать ключевые слова (в кавычках):
"Прикладная теория алгоритмов".
Выдается:
Результатов: примерно 26 600, страница 1 (0,16 сек.)

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

В отношении ссылок - это надо будет подготовить. Я об этом раньше не заботился.
А пока - для предварительного прикида:

1) Известный нам на этой теме "новый учебник" по алгоритмизации:
хорошее и практически полезное введение
в основы визуальной технологии (последовательной и даже параллельной !!!) алгоритмизации
для простых смертных - потенциальных практических разработчиков и пользователей алгоритмов
не-математического назначения, хотя и математика там отражается
(а не для математиков - фундаменталистов в области оснований математики).

2) Давайте посмотрим тему на этом сайте:
Здесь будут такие замечания:

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

Во-во вторых.Категорически протестую.
Все эти дела давно вышли из только математических приложений в технические приложения.
В частности:
Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов.
В третьем издании книги (1989 г.) излагаются:
-- традиционные последовательные логические схемы алгоритмов (ЛСА);
-- параллельные логические схемы алгоритмов (ПЛСА).

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

3) Можно привести другие направления прикладной теории алгоритмов:
автоматные, сетевые, параллельные алгоритмы логического управления (Закревский А.Д.) и т.д.

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

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

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

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

Вы несколько ошиблись. Результатов не 26 000, а всего 35.

Это легко проверить. Посмотрите внизу страницы. И перейдите на последнюю страницу.
Вы получите: https://www.google.ru/webhp?sourceid=na ... 1&start=60

Это типичная ошибка. От нее легко избавиться. С помощью именно такой перепроверки.

При еще одном повторении я получил чуть иной результат (не 35, а 43) https://www.google.ru/webhp?sourceid=na ... 1&start=40

=====

Заодно случайно заглянул в один (не бог весть какой) источник:

В нем нашел статью Ваграменко:
Из этой статьи я узнал, что:

Из другого источника можно узнать, что: http://group230105.nord001.ru/download/ ... 8F%204.pdf

Надо бы посмотреть эту литературу (которую дает Гугл) и конечно, английскую (в первую очередь).

Но вот беда — на английском я ничего не смог найти. Может, плохо искал?

Провожу эксперимент:
1) Без кавычек получилось примерно 240 000.
2) С кавычками получилось:
Результатов: примерно 118 000 (0,28 сек.) - в два раза меньше.
А в прошлый раз я выходил в Гугл через Яндекс (там было очень мало - но может быть это было более точное):
Тогда в Гугле было:
Результатов: примерно 26 600 (0,16 сек.)

Продолжаю эксперимент.
Кликаю внизу на последнюю 7-ю страницу:
Результатов: 35, страница 4 (0,28 сек.)
Это какой-то остаток? - после 6-ти страниц,
или общий тонко отфильтрованный результат?,
или некорректная работа?
Всего 35 источников - подозрительно маловато.

Продолжаю эксперимент.
Кликаю на первую страницу (из последних 4-х). Получается:
Результатов: примерно 99 000(0,23 сек.)
Что бы это значило?
Надо будет еще поиграться.

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


Это презентация лекции на штук 20-и листах (альбомного формата).
Не ясно для кого читается лекция.
Но не поленимся разобраться по существу.

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

Начинается с классического определения алгоритма:
Определение 4.0. Алгоритм – это точное предписание,
определяющее процесс переработки исходных данных в требуемый результат.
И далее перечисляются его классические свойства.

Затем вдруг появляется вставка одного листа с указанием:
и две фразы:
-- Для наглядного представления структуры алгоритмов применяются графические средства:
графы, блок-схемы, сети.
-- Формальное и полное описание алгоритмов осуществляется на языках программирования
высокого уровня (C++, PASCAL, FORTRAN и др.).
И пока все по прикладной теории.

А далее очень кратко представлены типичные аспекты классической теории:
Примеры алгоритмически неразрешимых задач.
Машина Тьюринга.
Элементы теории рекурсивных функций,
примеры примитивно-рекурсивных и обще-рекурсивных функций.
Эквивалентность всех представительных вычислительных моделей:
“тезиса Чёрча” о том, что все уточнения понятия алгоритма эквивалентны.

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

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

Вы уверены, что это именно всеобщая неясность? Может наоборот?

Без кавычек искать бессмысленно.

У меня столько же. Но. Цифра 26 600 — это ложь. Этой цифре нельзя верить ни в коем случае. Потому что она противоречит цифре 7 страниц (внизу). Цифра 7 гораздо ближе к истине, (но тоже не совсем точная, а предварительная, приблизительная).

Вот это правильно!
Почему правильно. Потому что 7-я страница — это ложь. Если бы было 7 страниц, мы бы получили число от 61 до 70. Но Гугл имеет меньше результатов, чем 61.

Когда Вы кликаете на цифре 7, Вы делаете великое дело — Вы разоблачаете Гугл. И вынуждаете его не лгать, а сказать правду.

Ни то, ни другое, ни третье. Вы неправильно интерпретируете результат.

Это означает, что Гугл нашел не 7 страниц (как он ошибочно, точнее, предположительно заявил вначале). На самом деле Гугл имеет за душой всего 4 страницы. На четырех страницах Гугл показывает 35 результатов. И среди них далеко не все принесут пользу. Увы.

Почему подозрительно? 35 — это и есть правда.

Это значит, что Вы некорректно понимаете алгоритм работы Гугла.

=====
Я заинтересован в том, чтобы Вы нашли полезный материал по "Прикладной теории алгоритмов". Но (повторяю) меня настораживает, что я не смог ничего похожего найти на английском.

Я не могу придти в себя от вострга.
Не подозревал, что Гугл мне так морочил голову - по своему ехидному алгоритму.
Запросил на Яндексе "алгоритм работы Гугла".
Нашел более или менее вразумительный ответ:

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


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


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

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

andr, почему-то я не смог скачать. Если можно, пришлите мне эту книгу по электронной почте на мой адрес vdp2007@bk.ru

Спасибо