OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 16 Октябрь, 2019 13:58

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




Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Четверг, 14 Май, 2009 02:15 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
На Королевстве Дельфи возникла тема о доказательном построении алгоритма вычисления исправленной дисперсии выборки.

Это послужило толчком к написанию следующей статейки:

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

Вложение:
I21-a-058-disperse-example-2009-eie.pdf [94.91 КБ]
Скачиваний: 844


Исходник в odc (Юникод):

Вложение:
I21-a-058-disperse-example-2009-eie.odc [143.8 КБ]
Скачиваний: 686


Замечания, конечно, приветствуются.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Май, 2009 08:23 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
1. У Гриса [3] нет "базовой схемы "полный проход"".
2. Это не "полный проход", а Ваш любимый линейный поиск (линейный просмотр, в терминах Дейкстры, [2], с. 146). Ищется первое НЕ real.
3. Тема не очень удачная. Внутренность цикла имеет вид x:=F(x). Такие примеры обычно решаются при изучении индуктивных функций (Кушниренко, [7]). А здесь индуктивные функции даже не упоминаются.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
По поводу [3] - ошибка в ссылке, конечно.

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

Можно строить более "глубоко", но вопрос в целесообразности. Доказать правильность = представить в такой форме, чтобы правильность была очевидна.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Peter Almazov писал(а):
3. Внутренность цикла имеет вид x:=F(x).


Вообще-то такой вид - x := F(x, ...) - имеет внутренность любого цикла, манипулирующего переменными (x - вектор). В частном случае F не зависит от x, либо зависит только от x.

Конечно, при объяснении темы "Расчёт рекуррентных последовательностей" всё проговаривается подробнее, чем я сделал тут. Здесь принято, что человек умеет отображать рекуррентное выражение функции в тело цикла. Тем более, что функция, считаемая циклом, тривиальна - сумма.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Вообще, Пётр, Ваша "война" против базовых схем и подобных частных (но общих по статистике) случаев, мне совершенно непонятна. Они как раз и появились вследствие практического применения дисциплины программирования.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Май, 2009 14:02 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Peter Almazov писал(а):
3. Внутренность цикла имеет вид x:=F(x).


Вообще-то такой вид - x := F(x, ...) - имеет внутренность любого цикла, манипулирующего переменными (x - вектор). В частном случае F не зависит от x, либо зависит только от x.

Конечно, при объяснении темы "Расчёт рекуррентных последовательностей" всё проговаривается подробнее, чем я сделал тут. Здесь принято, что человек умеет отображать рекуррентное выражение функции в тело цикла. Тем более, что функция, считаемая циклом, тривиальна - сумма.
Не надо добавлять точки внутрь скобок, частный случай без точек - это и есть линейный просмотр. Прочтите внимательно Дейкстру. Там, правда, охрана зависит от x, но это несущественно.
Ещё раз повторяю, что этот пример больше подходит для объяснения индуктивных функций. Книги Кушниренко у меня под рукой нет, но можно посмотреть здесь http://www.intuit.ru/department/se/pbmsu/4/4.html и здесь http://www.intuit.ru/department/se/oip/tasks/6.html Задача 11.36


Вложения:
dd.png
dd.png [ 212.91 КБ | Просмотров: 16696 ]
Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Май, 2009 14:12 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Вообще, Пётр, Ваша "война" против базовых схем и подобных частных (но общих по статистике) случаев, мне совершенно непонятна. Они как раз и появились вследствие практического применения дисциплины программирования.

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8184
Откуда: Троицк, Москва
Peter Almazov писал(а):
Часто вредный.
На каком опыте это основано.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Май, 2009 17:46 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Info21 писал(а):
Peter Almazov писал(а):
Часто вредный.
На каком опыте это основано.
Что шаг лишний, видимо, нет возражений.
Основано на моём личном опыте.
Одно дело - распознать характер цикла и классифицировать его, это не вредно, а весьма полезно. Но это всё очень просто сделать, не надо переоценивать важность тривиальных вещей. В случае с полным проходом мозги после этого можно отключить. А в случае линейного поиска надо смотреть на условия задачи, а не на то, что это линейный поиск. Ибо шаблон один, а условия бывают весьма разные. В обсуждениях на форуме я часто наблюдаю обратный путь, что и считаю вредным. Но вести "войну", как выразился Илья, не собираюсь.
Вот если есть конкретные примеры, то их было бы интересно обсудить.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8184
Откуда: Троицк, Москва
Peter Almazov писал(а):
Info21 писал(а):
Peter Almazov писал(а):
Часто вредный.
На каком опыте это основано.
Что шаг лишний, видимо, нет возражений.
Есть, причем даже вступать в полемику, честно говоря, лень.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Май, 2009 19:46 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Info21 писал(а):
Есть, причем даже вступать в полемику, честно говоря, лень.
Аналогично


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Линейный просмотр у Дейкстры - как раз и есть полный проход. Выраженный в общем виде.
Проход по последовательности неизвестной длинны от её начала до конца. Последовательность состоит из {x:~B(x)}.

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

P.S. При описании этих схем в терминах x := F(x) следует не забывать о случае управляющих алгоритмов, когда явно доступного алгоритму состояния может не быть вообще (т.е. идёт только выдача/получение сигналов/инструкций), а постусловие формулируется относительно цепи событий в системе. Не спорю, что и тут можно говорить о F(x), если трактовать x в нужном смысле (говорить о состоянии в смысле, специфичном для программируемой системы). Но всё же, отметим.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Очень интересное развитие темы вышло, в плане анализа погрешностей:
отсюда и далее -
http://delphikingdom.ru/asp/talktopic.a ... 95#msg4899

В итоге получился как раз успех доказательного подхода.

Надо статью дополнить, займусь завтра.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 05:50 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Линейный просмотр у Дейкстры - как раз и есть полный проход. Выраженный в общем виде.
Проход по последовательности неизвестной длинны от её начала до конца. Последовательность состоит из {x:~B(x)}.

Линейный поиск же подразумевает много причин окончания процесса - и классифицирует, так скажем, эти исходы.
А, ну всё ясно, в терминах лекции 08 Вы совершенно правы. Я под этими терминами понимал другое, и пропустил эти рассуждения в лекции как очевидные. Как говориться, "...ну, это я знаю..."
Смотрел в книгу, а видел фигу.
Это возникло из-за того, что толкователи использовали те же термины, что и отцы-основатели, но абсолютно в другом смысле. Такой подлянки не ожидал просто. Определение Дейкстры я уже приводил, вот Гриса.
После таких фокусов какие бы то ни было обсуждения полностью теряют смысл.


Вложения:
gris.png
gris.png [ 52.33 КБ | Просмотров: 16700 ]
Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 08:50 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8184
Откуда: Троицк, Москва
Peter Almazov писал(а):
Такой подлянки не ожидал просто.
А надо уточнять термины всегда, и вообще о смысле слов заботиться 8)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 09:44 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Info21 писал(а):
А надо уточнять термины всегда, и вообще о смысле слов заботиться 8)
Совет разумный. Можете применить его в лекции 08: "Если кто-нибудь знаком с работами Дейкстры и Гриса, забудьте про то, что они называют линейным поиском, и слушайте, что я так называю".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 11:47 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8184
Откуда: Троицк, Москва
Peter Almazov писал(а):
Info21 писал(а):
А надо уточнять термины всегда, и вообще о смысле слов заботиться 8)
Совет разумный. Можете применить его в лекции 08: "Если кто-нибудь знаком с работами Дейкстры и Гриса, забудьте про то, что они называют линейным поиском, и слушайте, что я так называю".
У меня непоняток не возникает.

А линейный поиск -- устоявшийся термин. (А Вы опять невнимательны.)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 12:55 

Зарегистрирован: Среда, 04 Июль, 2007 16:43
Сообщения: 233
Кстати, по-поводу
Илья Ермаков писал(а):
Текст набран в среде BlackBox.

формулы просто скопированные картинки или в среде BlackBox есть возможность генерить графическое представление формул изTeX-овского представления?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 13:24 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
По виду формулы больше походят на MathType'овские (не TeX)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Май, 2009 14:13 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4509
Откуда: Россия, Орёл
QWERTYProgrammer писал(а):
...есть возможность генерить графическое представление формул изTeX-овского представления?
http://www.zinnamturm.eu/downloadsAC.htm#Casket.


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

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


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

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


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

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