OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Ноябрь, 2019 00:06

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




Начать новую тему Ответить на тему  [ Сообщений: 48 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 21:51 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:02 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9157
Откуда: Россия, Орёл
Это Вы за деревьями леса не хотите видеть. К частностям целпяетесь. Математика - это не просто формалистика, суть надо видеть.

Цикл по определению работает над последовательностью состояний. Ничего кроме последовательности у цикла быть не может (в отличие от рекурсии). А цель цикла либо проста (один класс состояний), либо сложна (дизъюнктивная форма). ЛП - навязывание дисциплины с выделением этих классов и оперированием с дизъюнктивной формой постусловия. Фактически, только два случая и могут быть: ЛП не нужен (нет дизъюнкции вообще), ЛП нужен (несколько классов конечных состояний).

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


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

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Peter Almazov писал(а):
Илья Ермаков писал(а):
Бинарный поиск в тот же шаблон цикла вписывается (если потом не оптимизировать): поиск на последовательности сходящихся интервалов.
Я уже не удивляюсь таким заявлениям. Но, должен констатировать, что маразм с линейным поиском превышает все мыслимые пределы.

Вы знаете, маразм, как и склероз - серьезные неврологические заболевания, у них нет ни мыслемых, ни немыслемых пределов. Это либо высыхание (истощение) мозга (маразм), либо загнивание мозга (склероз).

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:13 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Закройте все книги, синтезируйте программу двоичного поиска и докажите, хотя бы себе, ее правильность. Время не ограничено, но разумное время на эту задачу 3-5 минут. Но с непривычки может быть значительно больше, время - не главное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:19 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Peter Almazov писал(а):
Закройте все книги, синтезируйте программу двоичного поиска и докажите, хотя бы себе, ее правильность. Время не ограничено, но разумное время на эту задачу 3-5 минут. Но с непривычки может быть значительно больше, время - не главное.

Не понял...
Предлагается по памяти записать бинарный поиск? Запишу, поскольку у меня это еще с олимпиад в печенках сидит. Да, сейчас далеко за полночь и я могу не сразу все вспомнить, но у меня действительно уйдет 3-5 мин на то, чтобы руки с головой нарисовали этот самый поиск.
Или что-то другое имеется ввиду?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:25 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:34 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Peter Almazov писал(а):
Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него?

Ээ-э-э... Тут я порченный пациент (это тоже термин из медицины). Синтезировать не смогу, я его просто знаю :)

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 22:56 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
У вас есть инструмент - шаблон линейны поиск. Точнее, скажем так: лекция № 8 Ткачева. Я предлагаю с его помощью решить задачу, которую дает Бентли в книге "Жемчужины творчества программистов".


Вложения:
bin.png
bin.png [ 168.03 КБ | Просмотров: 6032 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 23:11 
Модератор
Аватара пользователя

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


Приведено как начальный вариант в новой редакции АСД:

Код:
L := 0; R := N -1;
m := любое значение между L и R;
WHILE (L <= R) & (a[m] # x) DO
  IF a[m] < x THEN
    L := m + 1
  ELSE
    R := m - 1
  END;
  m := любое значение между L и R
END


Цитата:
Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R. Чтобы не потерять это подобие и тем самым надёжнее гарантировать корректность цикла, мы воздержались от соблазна мелкой оптимизации программы с целью устранения дублирование инструкции присваивания переменной m.

<Дальше инвариант (A k: 0 <= k < L: a_k < x) & (A k: R < k < N: a_k > x)
и обоснование корректности>

Как уже упоминалось, можно заняться устранением дублирования инструкции присваивания m. Однако такая оптимизация на уровне кода является преждевременной в том смысле, что сначала лучше попытаться оптимизировать алгоритм на уровне логики задачи. Здесь это действительно возможно: ввиду сходства алгоритма с алгоритмом линейного поиска естественно искать решение с более простым условием окончания, то есть без второго операнда конъюнкции в охране цикла (И.Е.: аналогия с барьером в случае ЛП). Для этого нужно отказаться от наивного желания закончить поиск сразу после нахождения искомого значения. На первый взгляд это неразумно, но при ближайшем рассмотрении оказывается, что выигрыш в эффективности на каждом шаге больше, чем...

Более быстрое решение основано на следующем инварианте:
(A k: 0 <= k < L : a_k < x) & (A k: R <= k < N : a_k >= x), а поиск продолжается, пока два отрезка не будут покрывать весь массив.


Код:
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + l ELSE R := m END
END


Цитата:
Можно сказать, что теперь ищется не элемент a[m] = x, а граница, отделяющая все элементы, меньшие x, от всех прочих.
... В отличие от первого решения, данный алгоритм - как и линейный поиск - находит искомое значение в позиции с наименьшим индексом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 23:18 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3109
Откуда: Астрахань
Илья Ермаков писал(а):
Код:
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + l ELSE R := m END
END


не кажется ли вам, что корректнее писакть
Код:
m:= (L + (R-L)) DIV 2;

Не может ли возникнуть в вашем случае переполнения суммы L+R ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Среда, 17 Февраль, 2010 23:22 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9157
Откуда: Россия, Орёл
Да ну, нереальная ситуация.

Даже если Вы возьмёте массив размером со всё адресное пространство, то поделите это на размер элемента - получитё ёмкость индексов, в неск. раз меньшую MAX(INTEGER).

А случай не мой; а полностью из книги процитированный.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 07:36 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 08:17 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Приведено как начальный вариант в новой редакции АСД: ...
Смиялсо.
Вы читать-то умеете?
Peter Almazov писал(а):
Закройте все книги ...
--------
Цитата:
Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R....
Пример характернейший. В приведенной цитате вся галиматья про линейный поиск - целиком на совести info21, тут даже оригинал можно не перечитывать. Но я все же проверил. У Вирта, к его чести, ничего этого нет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 08:28 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3109
Откуда: Астрахань
Peter Almazov писал(а):
Илья Ермаков писал(а):
Приведено как начальный вариант в новой редакции АСД: ...
Смиялсо.
Вы читать-то умеете?
Peter Almazov писал(а):
Закройте все книги ...
--------
Цитата:
Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R....
Пример характернейший. В приведенной цитате вся галиматья про линейный поиск - целиком на совести info21, тут даже оригинал можно не перечитывать. Но я все же проверил. У Вирта, к его чести, ничего этого нет.

Это вы, батенька, ахинею несете! Затем именно и нужны справочники, о которых Димыч говорил в первом посте. Грамотный инженер из башки не будет придумывать, он в справочник полезет. А в справочнике как раз паттерны-то и прописаны! И в каких условиях их применять лучше!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 09:05 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 11:33 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3109
Откуда: Астрахань
Peter Almazov писал(а):
Валерий Лаптев писал(а):
А в справочнике как раз паттерны-то и прописаны!
Я говорю об инструменте для "прописывателей паттернов".

Прошу прощения - не понял.
Если вы о том, что в справочнике прописывать, а что считать творческим алгоритмом, то я тоже такой вопрос задавал. ИМХО паттерн двоичного поиска должен быть прописан. Как и паттерны линейного поиска, поиска максимума или минимума... И т.п.
Или вы о том, что не получится прописать ПРАВИЛЬНЫЙ паттерн?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 11:38 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Peter Almazov писал(а):
Валерий Лаптев писал(а):
А в справочнике как раз паттерны-то и прописаны!
Я говорю об инструменте для "прописывателей паттернов".

Честно говоря, так и не понял вашу позицию. Ну да ладно...

Утро вечера мудренее: вынужден с вами согласиться.
Из головы у большинства программеров поиск выйдет с ошибкой.
Но ведь тем важнее создание справочника, в котором будет прописано что да как делать - бери и списывай.

Понятно, что на такие вещи надо натаскиваться во время обучения, что такие вещи должны просто от зубов отскакивать.
Но мы имеем то, что имеем - разночтения даже в основных алгоритмах, не говоря уже о том, как реализовывать "хаки" и "трюки".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 11:42 
Аватара пользователя

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

Библиотечная программа обычно нашпигована всякими проверками по самое не могу.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 11:49 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Наблюдаю за обсуждением (в этой и соседней ветках) и понимаю, что справочник нужен.

Понимаю также, что это работа не на один год, если подходить к этому серьезно.
Что считаю обязательным:
  • примеры на нескольких языках: Oberon-2, CP, Object Pascal, C. Вероятнее всего С++ и Java.
  • наличие ссылок на литературу с обсуждениями достоинств/недостатков/истории вопроса.
  • классификация. Понимаю, что это необходимо, но, не с этого начинать :)

Ну вот как-то так...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Программирование. Начала
СообщениеДобавлено: Четверг, 18 Февраль, 2010 12:05 
Аватара пользователя

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

Данная версия алгоритма была написана упростить объясняющую логику в тексте и упростить верификацию -- как и в случае всех других исправлений в новой версии книги (см. предисловие переводчика http://www.inr.ac.ru/~info21/wirth/ADru ... versii.htm).
Все исправления -- начиная с их цели -- были одобрены Виртом.
Он просил внести их в английский текст, но мне трудно найти связный блок времени, потому что нужно будет делать и изменения по тексту.
Если у кого-то есть время -- займитесь, я просмотрю изменения на предмет английского, и новый вариант будет выложен на страничке Вирта в ETH с указанием имени героя.

У вас по существу есть возражения?


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

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


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

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


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

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