DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 14:13

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




Начать новую тему Ответить на тему  [ Сообщений: 328 ]  На страницу 1, 2, 3, 4, 5 ... 17  След.
Автор Сообщение
 Заголовок сообщения: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 11:20 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Решил начать новую тему, чтобы обсудить интересный (я бы даже сказал, концептуальный) вопрос о формализации алгоритмических знаний. Почему в разделе про Дракон – да потому что Дракон рассматривается на этом форуме как наиболее подходящий кандидат для представления алгоритмических знаний.

Возможно, я многого не знаю в теории по этому вопросу, и надеюсь на просвещение с Вашей помощью...

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

Начнём, как обычно, с неформальной картинки:
Вложение:
Комментарий к файлу: Задача копирования
move_problem.PNG
move_problem.PNG [ 3.34 КБ | Просмотров: 28225 ]

И ещё необходимое уточнение: размер ячейки памяти - пусть будет 2-байтовое слово для определённости (возможно, кто-то сразу захочет услышать извинения из-за «ассемблерной» постановки задачи… ну, что ж делать, задача такая… реальная задача).

Как ни парадоксально это звучит, но на этом обобщённые алгоритмические знания о сути данной задачи… заканчиваются!
Далее начинается слой алгоритмических знаний, привязанный к конкретному исполнителю.

Вариант 1 (Borland Pascal, Delphi):
Код:
var p1,p2:pointer; i:integer;
p1:=откуда; p2:=куда;
for i:=1 to N do begin
  Smallint(p2^):=Smallint(p1^);
  inc(Longword(p1),2); inc(Longword(p2),2);
end;
М-м… да-а… Что-то некрасиво, ненадёжно (указатели нетипизированные; а хоть бы и типизированными сделать – изменится не сильно!) и вообще какая-то странная эмуляция ассемблерного решения на Паскале… однако, вроде бы полностью соответствует сути задачи. Ну хорошо, сформулируем более чисто (алгоритмически).

Вариант 2 (Borland Pascal, Delphi):
Код:
var a1,a2:array[1..N] of Smallint; i:integer;
for i:=1 to N do a2[i]:=a1[i];
Ой… Алгоритм вроде виден, но как его использовать для конкретной задачи? Как описать нужную область памяти (например, видеопамяти) в виде Паскальского массива? Ну, допустим, как-то можно извернуться (оставив за кадром, хотя это не есть хорошо) – но тогда необходимо усложнить алгоритм с учётом начальных смещений, суммируя их с индексами… Ну и т.п.
Хорошо. Каждой задаче - адекватный инструмент. Ассемблер так ассемблер. Вопрос – какой?

Вариант 3 (Asm, DEC PDP-11):
Код:
        mov   откуда,   r1
        mov   куда,   r2
        mov   N,   r0
1$:     mov   (r1)+,   (r2)+
        sob   r0,   1$   ;Subtract One and Branch if not zero
Решение элегантное, эффективное… За счёт особенностей конкретного исполнителя, который разрешает автоинкрементную адресацию и имеет специальную команду для организации цикла.
А не взять ли другой процессор?

Вариант 4 (Asm, Infineon C167):
Код:
        mov   r1,   откуда
        mov   r2,   куда
        mov   r0,   N
L_1:    mov   [r2+],   [r1]
        add   r1,   #2
        sub   r0,   #1
        jmp   cc_NZ,   L_1
Вот незадача… Оба регистра-указателя процессор не позволяет инкрементировать в одной команде. Так… Ещё один процессор (догадайтесь сами, какой ;) ):

Вариант 5 (Asm, Intel 8086):
Код:
        lds   si,   откуда
        les   di,   куда
        mov   cx,   N   ;сколько
        cld         ;в каком направлении
        rep   movsw      ;поехали!
Цикл реализуется микропрограммно, я рад безмерно… Вот только куда подевался алгоритм копирования как таковой? ;)

Ну и, наконец, ближе к кандидату на «универсальный описатель алгоритмов» - Дракону. Что же в нём описывать? Алгоритм? И каков, на самом деле, алгоритм решения данной задачи? Вариант 2? Или 1? Ну хорошо, пусть вариант 1 – вернулись к тому, с чего начали:
Вложение:
Комментарий к файлу: алгоритм копирования на Драконе
move.PNG
move.PNG [ 3.07 КБ | Просмотров: 28223 ]

Ну а, что, если воспользоваться неязыковыми средствами? Например, процедурой Move(Src,Dst,Count) в Delphi? Хорошо, это правильное решение, Delphi7 содержит код этой процедуры по типу варианта 5 (ну, с учётом 32-разрядности, конечно). Причём, если позволяет количество копируемых данных, использует не movsw, а movsd, что, естественно, ещё эффективнее… затрачивая только пару команд на проверку и ветвление перед началом цикла…
А вот сейчас взял да и посмотрел, какой код делает более свежая версия - Turbo Delphi… Ой! Я ничего не понимаю… После кучи проверок на более эффективные случаи (когда можно обойтись парой простых команд копирования вместо цикла) – реализуется обычный цикл (!), причём данные в цикле копируются не напрямую, и не через регистр общего назначения, а… через стек FPU ! Может, я чего-то не понял с ходу… но комментировать больше неохота…

Кроме того, очевидно, что на все случаи жизни системных процедур не напасёшься.

Собственно, для чего меня всё это интересует? Как ни странно, для вполне практической цели – хочу к Дракон-редактору прикрутить кодогенератор… На самом деле почти без разницы, к чему прикручивать кодогенератор – к Дракону или какому текстовому ЯВУ… А вот что именно компилировать? Смотрим – даже в такой простой задаче ну никак не отделяется чистый алгоритм от того слоя, в котором можно было бы отдельно учесть особенности исполнителя (естественно, ставится задача получения не просто работающего кода, но кода оптимального. Причём оптимального кода для разных целевых платформ).

Применить шаблоны? Дык, на все случаи шаблонов не напасёшься… да и как их распознавать в общем случае? Как придумать шаблон даже для такой несложной задачи? Особенно, если учесть, что от размера ячейки памяти в этой задаче реализация кода может существенно меняться, как и его эффективность…

Использовать оптимизирующий компилятор ЯВУ? Но какой компилятор сможет оптимизировать даже «приближённый к ассемблеру» вариант 1?

Вот такие вопросы. Если они останутся риторическими, я не удивлюсь… Но должна же что-то говорить теория… Про то, что такое алгоритм и с чем его едят…


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 12:16 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 82
Откуда: Москва
Алексей!
Вы выбрали неудачную задачу. Копирование из одной области памяти в другую не есть предмет алгоритма (т.к. с точки зрения любой прикладной задачи само по себе копирование из одной области памяти в другую бессмысленно), а есть предмет машиннозависимой реализации алгоритма.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 12:35 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 112
Откуда: Беларусь, Минск
У Кнута в первой книге алгоритмом называется метод вычислений с пятью ограничениями. Там же написано, что до 50-х годов алгоритмом называлось только вычисление НОД по Евклиду. Поэтому, поиск можно начинать оттуда.

На мой взгляд - алгоритм близок к математике или, что правильнее, завязан на формализации. А процессора, скорее всего, не имеют формальных моделей. Грубо говоря, наборы команд берутся от потолка. Соответственно, формулу "алгоритм + процессор = максимальная эффективность" вывести не получается.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 12:58 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Сергею Прохоренко - Ну тогда ещё раз про задачу. Формулировка на самом деле классическая - платформная независимость. Мне нужно, чтобы системная часть наших контроллеров была написана один раз и компилировалась под нужные целевые платформы, а не переписывалась десять раз заново. Обычно это решается программрованием на Си, где машинно-зависимые части максимально изолируются от содержательного кода. Например, осциллограф со всеми его буферами данных должен оставаться без изменения, а вот механизмы хранения этих буферов (RAM, FRAM, Flash) существенно различаются... Но это, в принципе, другая часть вопроса.

Здесь меня интересует конкретно использование Драконоподобного редактора для повышения наглядности, самодокументированности и переносимости кода. Сама по себе задача построения компилятора несложная.

Однако первое возражение от программистов по существу заключается в том, что идти таким путём нельзя - код получается никак не оптимальным. Если в десктопных приложениях на это зачастую можно закрыть глаза, то в жёстком реал-тайме ну никак. Вот и спрашивается, можно ли Дракон сделать адекватным инструментом. Здесь.

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

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

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

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

Valery Solovey - так что же, сдаваться и переквалифицироваться в управдомы? ;)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 14:40 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 82
Откуда: Москва
Мне кажется, нужны промежуточные языки, позволяющие сложному алгоритму и примитивному микроконтроллеру "найти общий язык":

Графический язык системы программирования (Вы выбрали Дракон) >>> XML-подобное текстовое представление графического языка (ТПГЯ) с элементами разметки >>> паскалеподобный разноуровневый промежуточный язык (РПЯ) >>> Ассемблер

РПЯ должен быть единым и независимым от целевой платформы. Но для каждой конструкции ТПГЯ должно быть несколько альтернативных средств разного уровня в РПЯ. На этапе компиляции ТПГЯ >>> РПЯ компилятор должен использовать те средства РПЯ, которые соответствуют целевой платформе. Если платформа позволяет использовать высокоуровневые средства, то используются высокоуровневые средства. Если платформа примитивная, то используются низкоуровневые средства.

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

Кстати, в Драконе я нигде не видел копирования одной области памяти в другую. То есть, это задача не алгоритмическая а более низкоуровневая.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 15:46 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Сергей Прохоренко писал(а):
Графический язык системы программирования (Вы выбрали Дракон) >>> XML-подобное текстовое представление графического языка (ТПГЯ) с элементами разметки >>> паскалеподобный разноуровневый промежуточный язык (РПЯ) >>> Ассемблер

Если не вдаваться в детали, то примерно так и выглядят многоплатформенные системы программирования логических контроллеров (тот же CoDeSys). TMX здесь уже подробно и убедительно отвечал мне, почему они не выбрали такую систему для работы.

Сергей Прохоренко писал(а):
Кстати, в Драконе я нигде не видел копирования одной области памяти в другую. То есть, это задача не алгоритмическая а более низкоуровневая.

А вот мне нужен инструмент, который позволит упростить создание системного ПО. То есть задача вроде копирования памяти - это как раз и есть мой хлеб в данном случае, она же предметная область. И как же она, по-Вашему, решается - неалгоритмически, что-ли? org100h про это тоже говорил, его ругали... а зря ;)

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

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

Вам задача копирвания памяти кажется надуманной. Ну тогда вот ещё пример. Выше я упоминал осциллограф, который должен с высокой скоростью записывать большие объёмы данных в энергонезависимую память. Так вот, работа с этой памятью встречается постоянно (как бы равномерно размазана по всемй программе). А от вида этой памяти зависит не только набор команд доступа к ней (по всей программе), но и сам общий алгоритм работы программы. Так, при работе с FRAM можно прямо копировать данные на место, но с обеспечением определённых задержек между двумя соседними обращениями; в то время как при работе с Flash необходим буфер в ОЗУ, и отдельная процедура стирания и записи флешки в подходящий, относительно свободный момент...

Так что, если Вы сможете отделить здесь алгоритмический слой от слоя реализации, то премия Тьюринга Ваша ;)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 05 Май, 2008 17:10 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 82
Откуда: Москва
Alexey_Donskoy писал(а):
Вам задача копирвания памяти кажется надуманной. Ну тогда вот ещё пример. ... при работе с FRAM можно прямо копировать данные на место, но с обеспечением определённых задержек между двумя соседними обращениями; в то время как при работе с Flash необходим буфер в ОЗУ, и отдельная процедура стирания и записи флешки в подходящий, относительно свободный момент...


Это как раз тот случай, о котором я писал. В паскалеподобном разноуровневом промежуточном языкя (РПЯ) должно быть несколько альтернативных средств: копирование с задержкой между сообщениями, копирование через буфер в ОЗУ и т.п. Компилятор ТПГЯ >>> РПЯ компилятор должен использовать те альтернативные средства РПЯ, которые соответствуют целевой платформе. Алгоритмической является задача сохранения данных, а способ сохранения - это машиннозависимые детали реализации алгоритма. Грубо говоря, переменная - это из области алгоритмов, а ячейка памяти - из области реализации алгоритма.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 03:34 

Зарегистрирован: Вторник, 29 Ноябрь, 2005 21:41
Сообщения: 53
Valery Solovey писал(а):
На мой взгляд - алгоритм близок к математике или, что правильнее, завязан на формализации. А процессора, скорее всего, не имеют формальных моделей. Грубо говоря, наборы команд берутся от потолка. Соответственно, формулу "алгоритм + процессор = максимальная эффективность" вывести не получается.
Что-то здесь не так. Вся процессорная логика описывается в руководствах. Если Вы считаете - что это не формальная модель - то что же тогда? Формулу относительно максимальной эффективности не выводят поскольку её достижение есть процесс.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 08:06 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Сергей Прохоренко писал(а):
Алгоритмической является задача сохранения данных, а способ сохранения - это машиннозависимые детали реализации алгоритма. Грубо говоря, переменная - это из области алгоритмов, а ячейка памяти - из области реализации алгоритма.

Звучит очень хорошо и заманчиво, только немного утопически. Да, в определённой мере такой подход работает. Так, в упомянутом CoDeSys есть "сохраняемые переменные", работа с которыми из программы ничем не отличается от работы с "несохраняемыми". Это хорошо для отдельных переменных, меняющих своё состояние изредка. А для жёстких задач с большими объёмами данных (тот же осциллограф) такой подход не прокатывает. Здесь уже организация сохранения данных составляет существенную и даже принципиальную составляющую алгоритма.

То есть, обратите внимание - я прошу совета про инструмент для системных работ, а все Ваши советы относятся к прикладному уровню! А кто системными работами-то должен заниматься и дрова писать - Пушкин? Или Пушкину по штату не положены эргономичные инструменты, и удел его - ассемблер?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 09:21 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 82
Откуда: Москва
Добавьте в паскалеподобный разноуровневый промежуточный язык (РПЯ) еще более низкоуровневые инструменты: прямую адресацию памяти различных типов, регистры.
Второй вариант: наиболее низкоуровневые вещи делать на ассемблерных вставках в код на РПЯ. Такие вставки можно оформить как процедуры - для повторного использования кода. Это облегчит РПЯ.
Других вариантов я не вижу.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 09:35 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Ну вот и я про то же ;) В смысле решений... Но, прежде чем реализовывать такие полумеры, неплохо было бы сначала понять, что делать надо... с точки зрения теории...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 15:14 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 140
Откуда: Троицк, Москва
Методическое замечание №1: всегда трудно назвать, что *есть*, даже когда оно прямо перед глазами. Люди обычно сами себя своими же словами запутывают.

В частности, алгоритм это всегда некий текст. Исполнитель -- интерпретатор текста. Чтобы строить теорию, его надо тоже сделать формальной моделью -- тоже текстом :-)

Кстати, в машине Тьюринга вроде лента памяти фигурирует явным образом.

А вот ссылочка неплохая: В.А.Успенский, А.Л.Семенов. Теория алгоритмов: основные открытия и приложения. (Библиотека программиста). Москва, Наука, 1987 (сдано в набор в мае 86, значит, написана до начала реального развала, народ еще спокойно работал).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Вторник, 06 Май, 2008 17:18 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Ну да, никакого разделения на "чистый алгоритм" и "специфику" нет...
Алгоритм и исполнитель всегда связаны. То, что Вы пишете на ассемблере для Вашего процессора - тоже алгоритм. Он тоже формален и тоже в некотором роде может быть исследован (воспринят, понят, проверен, верифицирован, промоделирован и т.п.)... Но поскольку исполнитель хреновый (т.е. не со специально спроектированным языком, а развитый хаотично, как многие процессоры), то с его алгоритмами мало чего эффективно можно делать. В том и проблема. Единственный путь, про что Вы и говорили - работать в терминах другого исполнителя (абстрактной машины - некоторого ЯВУ, например) и поручить машине трансляцию.... Но исполнитель такой хреновый, что без полного использования своей низкоуровневой семантики эффективно работать не хочет :-) А использовать её может только человек, т.к. для автоматики слишком сложная задача...
Кто ж Вам выход посоветует?

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

По поводу Успенского - да, книжка хорошая... Могу дать в электронном виде. А, я Вам, Алексей, её даже уже давал - в архиве case должна быть!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Среда, 07 Май, 2008 18:10 

Зарегистрирован: Воскресенье, 09 Март, 2008 22:38
Сообщения: 341
1. Что такое алгоритм. Ну, раз уж тут упомянули достопочтимого Тьюринга, давайте вспомним, что существует несколько строгих формализаций понятия алгоритма:
Машина Тьюринга
Нормальные алгорифмы Маркова
Рекурсивные функции
...
Более того, известно, что они эквивалентны между собой. Существует также так называемый тезис Чёрча, который гласит, что если для решения какой-то задачи может быть сформулирован алгоритм, то он может быть представлен в одной из приведенных формализаций.

Разные формализации понятия алгоритма, вообще говоря, приводят к различным моделям вычислений. Машина Тьюринга - к традиционной "фон-неймановской" модели, или модели, в которой присутствуют состояния (автоматы). Рекурсивные функции - к модели функциональных языков программирования (Лисп, ML, Huskell и др.). Алгорифмы Маркова - вроде бы к модели языка Рефал. И для не ориентированных на состояния моделей язык типа Дракона вообще, видимо, не подходит.

2. Как тут уже правильно заметили, понятие алгоритма неотделимо от понятия исполнителя. И именно набор понимаемых (исполнимых) исполнителем команд определяет "уровень" алгоритма. Мне кажется, во многом к этому сводится поставленная в этой ветке изначально проблема.

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


Последний раз редактировалось TAU Четверг, 08 Май, 2008 11:09, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Среда, 07 Май, 2008 18:59 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Ну да, это ж две категории алгоритмов - информационные и управляющие.
Для первого важен в первую очередь результат (заключённый в конечном состоянии). И, в принципе, безразлично, каким путём (через какие состояния) пришли.
Для второго смысл именно в последовательности управляющих состояний...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Четверг, 08 Май, 2008 11:00 
Аватара пользователя

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

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

TAU писал(а):
Возникает вопрос с формализацией понятия такого рода алгоритмов. У меня имеются некоторые предложения и наработки на этот счет.

Излагайте - подумаем вместе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Четверг, 08 Май, 2008 11:35 

Зарегистрирован: Воскресенье, 09 Март, 2008 22:38
Сообщения: 341
Илья Ермаков писал(а):
Ну да, это ж две категории алгоритмов - информационные и управляющие.
Для первого важен в первую очередь результат (заключённый в конечном состоянии). И, в принципе, безразлично, каким путём (через какие состояния) пришли.
Для второго смысл именно в последовательности управляющих состояний...
С точки зрения вычислений то, что там машина как-то переключается между состояниями - побочный эффект. Для функциональщиков, например, очень досадный :-)
С точки зрения управления как раз вычисления побочны...

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

Alexey Donskoy писал(а):
TAU писал(а):
Возникает вопрос с формализацией понятия такого рода алгоритмов. У меня имеются некоторые предложения и наработки на этот счет.

Излагайте - подумаем вместе

Можно посмотреть здесь
http://www.old.ssau.ru/struct/kafedry/c ... s0006.html
и здесь, со с.124:
http://www.ssau.ru/files/editions/vestn ... 2004_1.pdf


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Четверг, 08 Май, 2008 14:29 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Вопрос: Вы не знакомились с "реактивным функциональным программированием"? Функциональщики возлагают на него большие надежды для продвижения в область систем РВ...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 12 Май, 2008 10:29 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 112
Откуда: Беларусь, Минск
GUEST писал(а):
Что-то здесь не так. Вся процессорная логика описывается в руководствах. Если Вы считаете - что это не формальная модель - то что же тогда? Формулу относительно максимальной эффективности не выводят поскольку её достижение есть процесс.

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

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

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

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

Что же касается той формулы, которую я приводил, то я её использовал на правах метафоры.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Что же такое алгоритм?
СообщениеДобавлено: Понедельник, 12 Май, 2008 11:59 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1098
Откуда: Россия, Чебоксары
Valery Solovey писал(а):
Соответственно, процессорная логика - это не совсем то, что нужно. Это описание команд. Возможно, что оно даже формальное, но всё-таки, это не модель.

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

Естественно, исполнители предназначены для решения разных задач - потому имеют и разные наборы команд. Например, черепашке Лого можно скомандовать "поверни направо", а процессору - "mov -(pc),-(pc)".

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

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

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

Давайте сначала я приведу конкретные примеры.

Пример 1:
(0) Школьная задача по информатике ->
(1) мат.модель ->
(2) алгоритм решения согласно мат.модели ->
(3) запись алгоритма на языке высокого уровня (ЯВУ) ->
(4) компиляция в целевой код исполнителя

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

Скажу сразу, что такая классическая модель разработки, хотя и совершенно справедлива, меня не очень интересует... разве что как учебный пример ;) Тем не менее, есть тут очень важный момент, который Вы, вероятно, упускаете или, как минимум, недооцениваете - это сложность перехода от (2) к (3). Именно здесь возникает конкретный исполнитель с его архитектурой и системой команд. Например, поддерживает ли выбранный ЯВУ работу с массивами? А, может, у него есть более высокоуровневые абстракции (например, стеки и очереди)? Да, в конце концов, есть ли у него пресловутый GOTO? И Вы вдруг обнаруживаете, что "чистый алгоритм" этапа (2) весело испаряется...

А, может, у Вас его и не было? Может, Вы сразу решаете задачу на конкретном ЯВУ? Ну, так мы далеко пойдём ;)

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

Наконец, существенное замечание для серьёзных программистов (а не школьных ламеров). Обратим внимание на ресурсы. Допустим, мы пишем текстовый редактор и выбрали представление текста в виде одной длинной строки (массив одномерный то бишь). Вроде всё нормально, всё успешно работает... пока массив помещается в память... А вот представьте себе элементартную задачу линейного поиска в этом массиве, если его размер многократно превышает имеющийся объем ОЗУ!
Если Вы мне ответите, что программы, сделанные на нормальных системах программирования должны работать и в таком случае, Вы будете правы... и будете минутами ждать завершения свопинга в ответ на каждое движение мыши...

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

Теперь ближе к Вашему предложению о модели процессора... Этапы решения задачи, по существу, остаются теми же самыми... разве что на этапе (3) исполнителем будет не ЯВУ, а ассемблер. Да и то не обязательно. Особенности конкретного процессора возникают при переходе от (2) к (3), как только что и было рассмотрено.
В чём может заключаться предлагаемая Вами модель? в наборе процедур типа "копирование памяти", "восход солнца вручную" и т.п.? Так на каждый алгоритмический чих нипочём не напасёшься!

Аналогично не помогут и шаблоны. Шаблонами хорошо ассемблер в код транслировать. Но, когда возникает действительная потребность, НЕЛЬЗЯ БУДЕТ ВЫБРАТЬ НАИБОЛЕЕ ПОДХОДЯЩУЮ КОМАНДУ!

ПОТРЕБУЕТСЯ ВЕСЬ АЛГОРИТМ ПЕРЕДЕЛЫВАТЬ!

Точнее, проектировать его сразу с учётом конкретного исполнителя. Или проектировать его для "универсального" исполнителя, неизбежно проигрывая в эффективности кода. Ваши предложения?


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

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


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

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


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

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