OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 18 Ноябрь, 2017 01:54

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




Начать новую тему Ответить на тему  [ Сообщений: 15 ] 
Автор Сообщение
 Заголовок сообщения: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Февраль, 2013 20:29 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7712
Откуда: Троицк, Москва
Алгоритм -- это класс эквивалентности программ в разных символических представлениях (хоть текстовых, хоть графовых) в рамках тезиса Чёрча.

(С) Ф.В.Ткачев, 2013-02-03 (если не найдётся претендентов с более ранней претензией).

Разжевывать не хочу и сил нет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Февраль, 2013 21:11 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
Еще бы как-то определить эквивалентные программы... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 02:42 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7712
Откуда: Троицк, Москва
Валерий Лаптев писал(а):
Еще бы как-то определить эквивалентные программы... :)
Вперёд!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 05:57 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Так эквивалентность можно по-разному определять... Например:

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

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

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

Как-то так с "предметных", качественных позиций. Или как?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 07:34 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
Я начал тут определять эквивалентные программы по входу-выходу, но вопрос требует более серьезного подхода.
А вообще-то эквивалентность программ давно пытаются сделать - со схем Ляпунова... :)
Но пока - не очень получается... :)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 08:01 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 651
Откуда: Псков
Если бы было голосование, я бы не отдал голос за такую (из стартового сообщения) формулировку.
Как то по душе больше без страшных строгостей. :)
PS.
А вот протоколы взаимодействия программ- это алгоритм в таком понимании?
PPS
Алгоритм - неопределяемое понятие. Все формулировки -только поясняющие. (мысль, естественно, не моя).


Последний раз редактировалось albobin Понедельник, 04 Февраль, 2013 08:45, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 08:22 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
По Закревскому - должон быть "параллельный алгоритм"... в общем случае... :) Но будет ли?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 09:22 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Валерий Лаптев писал(а):
...
2. По структуре. Это в общем виде сводится к задаче гомоморфизма графов.
...
Включая нагрузку/разметку графа, наверное?.. Ведь неэквивалентность м.б. в текстах вершин при одинаковых структурах?.. И, кстати, в части объявлений тоже?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Понедельник, 04 Февраль, 2013 11:07 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
Владислав Жаринов писал(а):
Валерий Лаптев писал(а):
...
2. По структуре. Это в общем виде сводится к задаче гомоморфизма графов.
...
Включая нагрузку/разметку графа, наверное?.. Ведь неэквивалентность м.б. в текстах вершин при одинаковых структурах?.. И, кстати, в части объявлений тоже?..

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Среда, 27 Февраль, 2013 00:56 

Зарегистрирован: Вторник, 05 Январь, 2010 21:31
Сообщения: 1101
Откуда: Харків, Данилівка
Info21 писал(а):
тезиса Чёрча.

Гы.. :mrgreen:


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Суббота, 02 Март, 2013 21:18 

Зарегистрирован: Воскресенье, 09 Март, 2008 22:38
Сообщения: 370
Владислав Жаринов писал(а):
Так эквивалентность можно по-разному определять... Например:

1. По маршрутам

2. По результатам

3. По связыванию
Как-то так с "предметных", качественных позиций. Или как?..

Именно!

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Март, 2013 05:26 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
И чего у мощного мужика Закревского смотреть?
А то у него на Озоне достаточно много книжек...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Март, 2013 06:01 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Наверное, опять же "Параллельные алгоритмы..."?..
Кстати, его понятие вроде как сопрягаемо с понятиями мощного мужика Харела... которые используются и Карповым, и "автоматчиками" (те же Поликарпова и Шалыто)?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Март, 2013 08:10 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 2846
Откуда: Астрахань
http://urss.ru/cgi-bin/db.pl?lang=Ru&bl ... &id=123497
Закревский А.Д.
Параллельные алгоритмы логического управления. Изд.3
2012. 200 с. 257 руб.
ISBN 978-5-354-01417-0

Оно?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение алгоритма
СообщениеДобавлено: Воскресенье, 03 Март, 2013 08:20 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Ну, отвечать за Андрея Александровича не буду... :) Но вот тут оформилось, зачем это более широкое понятие м.б. нужно: viewtopic.php?p=78384#p78384 (можно сразу в резолютивную часть смотреть :))...


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

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


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

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


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

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