Еще бы как-то определить эквивалентные программы...
| OberonCore https://forum.oberoncore.ru/ |
|
| определение алгоритма https://forum.oberoncore.ru/viewtopic.php?f=8&t=4241 |
Страница 1 из 1 |
| Автор: | Info21 [ Воскресенье, 03 Февраль, 2013 20:29 ] |
| Заголовок сообщения: | определение алгоритма |
Алгоритм -- это класс эквивалентности программ в разных символических представлениях (хоть текстовых, хоть графовых) в рамках тезиса Чёрча. (С) Ф.В.Ткачев, 2013-02-03 (если не найдётся претендентов с более ранней претензией). Разжевывать не хочу и сил нет. |
|
| Автор: | Валерий Лаптев [ Воскресенье, 03 Февраль, 2013 21:11 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Еще бы как-то определить эквивалентные программы...
|
|
| Автор: | Info21 [ Понедельник, 04 Февраль, 2013 02:42 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Валерий Лаптев писал(а): Еще бы как-то определить эквивалентные программы... Вперёд!
|
|
| Автор: | Владислав Жаринов [ Понедельник, 04 Февраль, 2013 05:57 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Так эквивалентность можно по-разному определять... Например: 1. По маршрутам (только "абстракция операций" Кауфмана) - на одинаковых исходных данных (материалах) сравниваемые программы (техпроцессы) проходят одни "развёртки" ("варианты использования"). При этом сравнивающему по барабану, какие результатные данные (продукты) в результате получаются. Видимо, надо фиксировать смысл действий и оговаривать, что "репертуар" сравниваемых в этом смысле одинаков (как бы они не формулировались). 2. По результатам (только данные) - на одинаковых данных сравниваемые программы выдают одинаковые результаты. При этом несущественно уже, какие в них получаются "развёртки". Видимо, надо фиксировать уже смысл типов источников/результатов. 3. По связыванию - на одинаковых данных исполнитель по сравниваемым программам должен приходить в одинаковые состояния (для "трансформационных" задач). Или приводить предметную область задачи в состояния из некоего "класса эквивалентности" (например, с учётом также времени приведения, как для "реагирующих" задач). Ну, тут множество состояний фиксируется... Как-то так с "предметных", качественных позиций. Или как?.. |
|
| Автор: | Валерий Лаптев [ Понедельник, 04 Февраль, 2013 07:34 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Я начал тут определять эквивалентные программы по входу-выходу, но вопрос требует более серьезного подхода. А вообще-то эквивалентность программ давно пытаются сделать - со схем Ляпунова... Но пока - не очень получается... Для учебных целей важно два вида эквивалентности: 1. По входу-выходу. Это проверяется легко на одном и том же наборе тестов. 2. По структуре. Это в общем виде сводится к задаче гомоморфизма графов. Эта эквивалентность очень важна, так как первая не дает гарантии, что студент правильно выполнил задачу. Например, задача написать сортировку. Студень вместо реализации алгоритма пишет вызов стандартной. Его программа по первому пункту удовлетворяет. а по второму - нет. Вот и приходится преподу лазить во все тексты и смотреть, что и как. А это - куча времени (у каждого посмотреть все его программы во всех лабах - и сделать замечания по реализации). Хочется повесить эту рутинную работу на среду. |
|
| Автор: | albobin [ Понедельник, 04 Февраль, 2013 08:01 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Если бы было голосование, я бы не отдал голос за такую (из стартового сообщения) формулировку. Как то по душе больше без страшных строгостей. PS. А вот протоколы взаимодействия программ- это алгоритм в таком понимании? PPS Алгоритм - неопределяемое понятие. Все формулировки -только поясняющие. (мысль, естественно, не моя). |
|
| Автор: | Владислав Жаринов [ Понедельник, 04 Февраль, 2013 08:22 ] |
| Заголовок сообщения: | Re: определение алгоритма |
По Закревскому - должон быть "параллельный алгоритм"... в общем случае... Но будет ли?..
|
|
| Автор: | Владислав Жаринов [ Понедельник, 04 Февраль, 2013 09:22 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Валерий Лаптев писал(а): ... Включая нагрузку/разметку графа, наверное?.. Ведь неэквивалентность м.б. в текстах вершин при одинаковых структурах?.. И, кстати, в части объявлений тоже?..
2. По структуре. Это в общем виде сводится к задаче гомоморфизма графов. ... |
|
| Автор: | Валерий Лаптев [ Понедельник, 04 Февраль, 2013 11:07 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Владислав Жаринов писал(а): Валерий Лаптев писал(а): ... Включая нагрузку/разметку графа, наверное?.. Ведь неэквивалентность м.б. в текстах вершин при одинаковых структурах?.. И, кстати, в части объявлений тоже?..2. По структуре. Это в общем виде сводится к задаче гомоморфизма графов. ... Да. Потому как граф программы может иметь и вершины и ребра разных типов, да еще нагруженные. Одно радует: для специального вида графов (коим является наше семантическое дерево) можно придумать более-менее нормально работающий по времени алгоритм. |
|
| Автор: | Рыжий [ Среда, 27 Февраль, 2013 00:56 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Info21 писал(а): тезиса Чёрча. Гы.. 
|
|
| Автор: | TAU [ Суббота, 02 Март, 2013 21:18 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Владислав Жаринов писал(а): Так эквивалентность можно по-разному определять... Например: 1. По маршрутам 2. По результатам 3. По связыванию Как-то так с "предметных", качественных позиций. Или как?.. Именно! Вообще, алгоритм - гораздо более широкое понятие, нежели некие вычисления позволяющие по входным данным найти некоторые выходные, см. мощного мужика Закревского. Я даже стал задумываться над своим определением управляющего алгоритма реального времени... |
|
| Автор: | Валерий Лаптев [ Воскресенье, 03 Март, 2013 05:26 ] |
| Заголовок сообщения: | Re: определение алгоритма |
И чего у мощного мужика Закревского смотреть? А то у него на Озоне достаточно много книжек... |
|
| Автор: | Владислав Жаринов [ Воскресенье, 03 Март, 2013 06:01 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Наверное, опять же "Параллельные алгоритмы..."?.. Кстати, его понятие вроде как сопрягаемо с понятиями мощного мужика Харела... которые используются и Карповым, и "автоматчиками" (те же Поликарпова и Шалыто)?.. |
|
| Автор: | Валерий Лаптев [ Воскресенье, 03 Март, 2013 08:10 ] |
| Заголовок сообщения: | Re: определение алгоритма |
http://urss.ru/cgi-bin/db.pl?lang=Ru&bl ... &id=123497 Закревский А.Д. Параллельные алгоритмы логического управления. Изд.3 2012. 200 с. 257 руб. ISBN 978-5-354-01417-0 Оно? |
|
| Автор: | Владислав Жаринов [ Воскресенье, 03 Март, 2013 08:20 ] |
| Заголовок сообщения: | Re: определение алгоритма |
Ну, отвечать за Андрея Александровича не буду... Но вот тут оформилось, зачем это более широкое понятие м.б. нужно: viewtopic.php?p=78384#p78384 (можно сразу в резолютивную часть смотреть )...
|
|
| Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|