OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 17:33

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




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 12:17 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Вчера передавал хелло Мартину Одерскому (ученик Вирта, Scala и т.п.: http://people.epfl.ch/martin.odersky). Он не знал, что такое "марковская парадигма". Хотя в Scala пытается слить ООП и функциональное, плюс еще речь шла о pattern-matching.
Вот я и задумался: где первоисточник слов "марковский язык", "марковская парадигма".

Искал-искал, и нашел только это:
http://www.inr.ac.ru/~info21/qna.htm (2005). Еще раньше в своих лекциях. Еще раньше когда-то отклассифицировал (для внутреннего понимания) систему компьютерной алгебры SCHOONSCHIP как марковскую, т.к. чтобы научиться там программировать "что угодно", пришлось когда-то (начало 80-х) мозги вывернуть.
Основания теории вычислимости (где трактуется про "нормальные алгорифмы Маркова"; например, кажется, Мальцев), конечно, читал и читал давно (причем реально читал). Программеры таких книг, конечно, не читают, а заимствуют фразы для дальнейшего комбинирования друг у друга.

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

Итак, где впервые на одном дыхании было сказано об "императивном, функциональном, марковском" программировании/парадигме/языках?

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

Мелочь, а было бы приятно :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 13:19 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
"Сентенцеальное" - это из книги Непейводы. Я читал не книгу, а курс лекций на интуите, который гораздо короче. В лекциях, насколько я помню, ясного объяснения, в чём различие между функциональными и сентенциальными языками не было.


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Если перечислять по времени появления, то получится такой ряд:

1920-е годы -- Комбинаторная логика
1930-е годы -- Лямбда-исчисление
1930-е годы -- Машина Тьюринга
1940-е годы -- Нормальные алгорифмы Маркова

Неудивительно, что советские алгорифмы Маркова почти неизвестны на западе. Даже комбинаторы, которые открыл Моисей Шейнфинкель в России, пришлось через несколько лет переоткрывать Хаскеллу Кэрри в штатах...


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Info21 писал(а):
Искал-искал, и нашел только это:http://www.inr.ac.ru/~info21/qna.htm (2005). Еще раньше в своих лекциях. Еще раньше когда-то отклассифицировал (для внутреннего понимания) систему компьютерной алгебры SCHOONSCHIP как марковскую
Свидетельствую, что услышал этот термин от Вас на Вашей лекции в Институте физических проблем году эдак в 1998 наверное. Я тогда ещё в аспирантуру собирался поступать, значит 98-ой.

Я тогда так понял, что, например, пакет Reduce марковский.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 15:22 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Сергей Губанов писал(а):
Я тогда так понял, что, например, пакет Reduce марковский.
Reduce основан на лиспе, так что это всё-таки лямбда-исчисление, а не марковские алгорифмы...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 15:43 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
G. De Leve, P. J. Weeda "DRIVING WITH MARKOV-PROGRAMMING", 1968

В списке литературы только G. De Leve, "Generalized Markovian Decision Processes", 1964


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 16:27 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Info21 писал(а):
Искал-искал, и нашел только это:
http://www.inr.ac.ru/~info21/qna.htm (2005). Еще раньше в своих лекциях. Еще раньше когда-то отклассифицировал (для внутреннего понимания) систему компьютерной алгебры SCHOONSCHIP как марковскую, т.к. чтобы научиться там программировать "что угодно", пришлось когда-то (начало 80-х) мозги вывернуть.
Основания теории вычислимости (где трактуется про "нормальные алгорифмы Маркова"; например, кажется, Мальцев), конечно, читал и читал давно (причем реально читал). Программеры таких книг, конечно, не читают, а заимствуют фразы для дальнейшего комбинирования друг у друга.

1. О "марковских" языках в программистской литературе нет ничего - это я вам как нехилый знаток программерской литературы говорю.
Хотя надо посмотреть в книжке Кауфмана
http://proklondike.com/contentview.php? ... 44&print=1
Там может быть.
В книжках по рефалу, которые в свое время издал ЦНИИПИАСС - точно не было.
2. Зачем так программеров-то обижать, Федор Васильевич?
Я Дейкстру реально читал - с разбором каждого доказательства и даже сам доказывал кое-что, что там без доказательства дается.
Введение в теоретическое программирование тоже нам не чуждо. И вообще, теория графов в изложении Касьянова и Евстигнеева - рулит.
К сожалению марковские цепи нам в универе почему-то не давали - это проехало мимо меня.
Теперь посмотрю внимательно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Марковская парадигма
СообщениеДобавлено: Четверг, 07 Май, 2009 16:31 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Валерий Лаптев писал(а):
К сожалению марковские цепи нам в универе почему-то не давали - это проехало мимо меня.
Кстати, марковские цепи и марковские алгорифмы -- разработки разных Марковых, отца и сына...


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Я сначала встретил этот термин у Фёдора Васильевича; потом познакомился с Рефалом; потом - с книгой Непейводы; и, наконец, с книгой Кауфмана, где выделяются фон-неймановская, функциональная и марковская парадигмы (последняя называется "Модифицированная модель Маркова" и "модель М").

Про Рефал у Кауфмана так изложено:

Цитата:
Тут уместно вспомнить язык нормальных алгоритмов Маркова (для единообразия
назовем этот язык моделью Маркова).
Охарактеризуем эту модель с точки зрения нашей концептуальной схемы.
Базис: единственный скалярный тип данных - литера; единственная базисная
операция - поиск-подстановка; единственная структура данных - строка (текст);
единственная структура операций - цикл по подстановкам.
Развитие: Явных средств нет. Только моделированием.
Дальнейший анализ модели можно предложить в качестве упражнения.
В модели Маркова анализ структуры встроен в исполнитель и управляется левой
частью подстановки. Синтез структуры отделен от анализа - он управляется правой
частью подстановки. Исполнитель распознает тривиальную структуру (слово),
указанную слева, и заменяет ее столь же тривиальной структурой (словом), указанной
справа.
С точки зрения нашей задачи эта модель недостаточно развита. Дело в том, что
вид распознаваемых структур слишком тривиален. Хотелсь бы приблизить средства
описания вида структур, скажем, к БНФ. Шаги в нужном направлении сделаны в языке,
созданном в ИПМ АН СССР в 1966-68 г.г. и получившем название "рефал" (рекурсивных
функций алгоритмический язык). В его основу положены следующие три модификации
модели Маркова.

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Geniepro писал(а):
Сергей Губанов писал(а):
Я тогда так понял, что, например, пакет Reduce марковский.
Reduce основан на лиспе, так что это всё-таки лямбда-исчисление, а не марковские алгорифмы...
Лисп точно так же "основан" на ассемблере, ну и что.

В пакете Reduce-2 есть средство подстановки (SUB), но оно добавлено уже под влиянием SCHOONSCHIP'а (и без ссылки (за что автор второго на автора первого имеет тенденцию ворчать).
Но основная "схема" Reduce'а более всего императивная, даже не функциональная.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Валерий Лаптев писал(а):
2. Зачем так программеров-то обижать, Федор Васильевич?
Виноват. Это было статистическое утверждение, без квантора общности.

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

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Geniepro писал(а):
Валерий Лаптев писал(а):
К сожалению марковские цепи нам в универе почему-то не давали - это проехало мимо меня.
Кстати, марковские цепи и марковские алгорифмы -- разработки разных Марковых, отца и сына...
А главное, это совершенно разные вещи.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Валерий Лаптев писал(а):
Введение в теоретическое программирование тоже нам не чуждо. И вообще, теория графов в изложении Касьянова и Евстигнеева - рулит.

Оффтоп: Да, книга основательная! От людей, которые создавали части этой теории, а не просто переизлагают.
У меня была в электронном виде тоненькая книжка "Графы в программировании" Евстигнеева, 198х г.
Заказал вот эту новую (2003 г., 1000 стр..) - так заказ отменили, не нашли на складе :)
Мне её таки нашли в электронном виде в Торрентах. Кому нужно - обращайтесь :)


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Илья Ермаков писал(а):
... с книгой Кауфмана, где выделяются фон-неймановская, функциональная и марковская парадигмы (последняя называется "Модифицированная модель Маркова" и "модель М").
Значит, Кауфман.

Кауфман -- это же ВМК МГУ? Если так, то б.-м. понятно: это, так сказать, сокровенное знание "советского" домена.
Книгу Мальцева Кауфман наверняка тоже знал, дальше логика в одно касание.

Но на SCHOONSCHIP Кауфман не ссылается. Плохо знают теоретики прикладные области. А вещь сильная, существует с 1967 г. Сейчас, правда, больше квази-коммерческий клон FORM-*.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Илья Ермаков писал(а):
Мне её таки нашли в электронном виде в Торрентах. Кому нужно - обращайтесь :)
Разве по теории графов мало книг? Вроде, море. Чем эта лучше?


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

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

У новосибирцев теория преломлена через свои работы - теория схем программ, оптимизация программ, САПР и т.п. В последней книге разобраны методы построения чертежей разных классов графов и прочая практически нигде больше не разбиравшаяся интересная конкретика.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Info21 писал(а):
Кауфман -- это же ВМК МГУ? Если так, то б.-м. понятно: это, так сказать, сокровенное знание "советского" домена.

Ага, Кауфман с ВМК. С 90-х в Хельсинках (по-моему).


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Geniepro писал(а):
G. De Leve, P. J. Weeda "DRIVING WITH MARKOV-PROGRAMMING", 1968

В списке литературы только G. De Leve, "Generalized Markovian Decision Processes", 1964


Это как раз про другое марковское - вероятностное :) Марковские процессы.
Приведённая статья вроде по стат. анализу, типа того...
А слово "programming" употреблено в смысле "оптимизация". Так же, как "математическое... линейное... динамическое... программирование". (Так повелось, кажется, с 30-х гг., когда комп. пр-я и в помине не было; а слово употреблялось как что-то типа "планирование").


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Geniepro писал(а):
Валерий Лаптев писал(а):
К сожалению марковские цепи нам в универе почему-то не давали - это проехало мимо меня.
Кстати, марковские цепи и марковские алгорифмы -- разработки разных Марковых, отца и сына...

Тем более...
Видите, насколько я дремуч... :)


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Илья Ермаков писал(а):
Я сначала встретил этот термин у Фёдора Васильевича; потом познакомился с Рефалом; потом - с книгой Непейводы; и, наконец, с книгой Кауфмана, где выделяются фон-неймановская, функциональная и марковская парадигмы (последняя называется "Модифицированная модель Маркова" и "модель М").

Вот!!!! Я ж говорил, что у Кауфмана может быть.. :)


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

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


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

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


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

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