OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2024 05:23

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




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: две базовые формы цикла - бред?
СообщениеДобавлено: Понедельник, 19 Апрель, 2010 20:39 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Выделено: viewtopic.php?p=46150#p46150
Валерий Лаптев писал(а):
Запостил в РСДН тему: Как учить технике программирования. Народ - не врубается... То есть даже не понимает проблему - обучение технике...
Тяжело разговаривать.
О двух базовых формах цикла - понятия не имеют. Ощущаю себя миссионером-просветителем...
Среди профессиональных программистов. :(
Вы не слишком там усердствуйте. Потому что две базовые формы цикла - это бред здешнего форума.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 19 Апрель, 2010 20:56 

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Понедельник, 19 Апрель, 2010 22:00 
Модератор
Аватара пользователя

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


Может быть, пан Алмазов большой специалист в области клинической психиатрии? :)
Нам про него известно только то, что Дейкстру с Грисом штудировал и в инвариантах зело преуспел, что уважению способствует, но для подписи под диагнозами как-то недостаточно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 19 Апрель, 2010 22:03 
Модератор
Аватара пользователя

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


Таких соотношений, как между общей теорией Дейкстры и схемами, пруд пруди и в прикладной математике, и в инженерии.
Есть конкретные методы, есть более общие теории, которые работают там, где кончается область применимости у методов.
Что-то строится из общих соображений, что-то - из практической техники. Конфликтов обычно нет, если аккуратно построено, а не наобум.


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Дело в том, что я практически самоучка-программист... Не учился я на инженера. Поступал на матфак, а заканчивал ПММ - первый выпуск в ташкентском универе. Поэтому математику мне вроде неплохо преподали, а вот программирование, как я потом понял - очень плохо. И естественно, на матфаке и на ПММ ни о каких инженерных дисциплинах речи не было.
Препод я тоже самоучка, и стал преподавать только после 40. Года этак с 95-го, стал задумываться, а как, собственно, учить программированию... И практически ничего, кроме словесов, найти не мог. Пока вот на этот оберонский форум не наткнулся...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 07:51 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Валерий Лаптев писал(а):
Интересный вопрос выплыл в моей дискуссии по технике программирования на РСДН. Как всегда, большинство гнут пальцы, но попадаются вопросы.
Цикл event dispatcher'а (например, в X-Windows или AWT/SWT) — это перебор или поиск?
Цикл, возникающий при чтении из сокета тела HTTP-запроса/ответа - это перебор или поиск?
Это подтверждения диагноза, данного в этой теме :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 07:54 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Валерий Лаптев писал(а):
Препод я тоже самоучка, и стал преподавать только после 40. Года этак с 95-го, стал задумываться, а как, собственно, учить программированию... И практически ничего, кроме словесов, найти не мог. Пока вот на этот оберонский форум не наткнулся...
Ну вот вам пример с двоичным поиском.
Как решать эту задачу? Первым делом здесь, как и в 100% других случаев, нужно попытаться сформулировать инвариант цикла. Здесь как раз потребуется и опыт, и догадка, и интуиция. Например, Бентли ([1] c. 51) приводит такой инвариант: "если элемент T вообще есть в массиве X[1..N], то он должен быть в некоторой области, принадлежащей X". Первоначально эта область – весь массив. Уже по слову "если" в этой формулировке видно, насколько она корявая. Думаю, причина этого в том, что у Бентли мало опыта – он, как и многие, использует всю это теорию только для обучения, а не для реальной жизни.
Вот нормальный инвариант цикла: определим область, где НЕ содержится искомый элемент. Первоначально эта область состоит из двух несмежных кусков нулевой длины (толщины, если угодно) в начале и в конце массива. Она не содержит искомый элемент, т. к. пуста и вообще ничего не содержит. Если в процессе работы эта область покроет весь массив, то искомого элемента в массиве нет.
Формально (буквы и размерность массива 1..N как в [1]):
Aj: 1 <=j < L или U < j <= N: X[j] != T
Первоначально L=1, U=N, область пуста.
Когда область покроет весь массив? Когда L > U, достаточно L=U+1.

Предположим, средний элемент (обозначим его индекс как M) массива X не равен искомому элементу T. Как мы можем изменить L и U так, чтобы инвариант остался истинным? В такой постановке задача оказывается настолько простой, что здесь негде ошибиться. Если T больше среднего элемента, то во всем куске от 1 до среднего элемента нет T. Аналогично, если T меньше среднего элемента, то во всем куске от среднего элемента до N нет T. Область расширяется, в первом случае L:=M+1, во втором U:=M-1. Для полной наглядности можно нарисовать массив на бумаге в клеточку.
Вот и вся идея алгоритма, причем у нас есть уверенность, что мы нигде не ошиблись на плюс/минус 1.
При чем здесь "шаблон линейного поиска"? Правильно, ни при чем.

1. Бентли. Жемчужины творчества программистов. М:Радио и связь 1990.


Последний раз редактировалось Peter Almazov Вторник, 20 Апрель, 2010 08:28, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 07:59 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
У Ткачёва речь о структурном подобии первого варианта, которое является полезным для уверенности; а не о том, чтобы придумывать, исходя из ЛП.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 08:23 
Аватара пользователя

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

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

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

Среди более сложных циклов (а они все -- как мин. двухветочные Дейкстры) тоже можно выделить один-два полезных частных случая. И упражнять их отдельно, в зависимости от времени в курсе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 08:29 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 08:43 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 08:58 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
1. Я там написал:
Цитата:
Для снижения градуса возбуждения, добавлю, что такое утверждение — только две схемы цикла — как раз для новичков, для постановки БАЗОВОЙ техники...
Это же два квантора: для любого и существует.
Сначала новичков следует научить этим самым общим схемам, а потом, естественно, можно углубляться...
По мере увеличения уровня обученности, чел научится и "конь на краю доски" применять грамотно и безболезненно...

Только там исправить нельзя - приходится новое сообщение писать...
2. Кто, как не автор концепции, лучше знает, как поправлять :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: две базовые формы цикла - бред?
СообщениеДобавлено: Вторник, 20 Апрель, 2010 09:32 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Info21 писал(а):
Валерий Лаптев писал(а):
Тогда скажите, как поправить.
Ну вот... меня же и грузить...
Впредь наука (в том числе и мне!). Лучше давать только опубликованные цитаты, и ссылочку на них. Чтобы был доступен контекст.


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

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


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

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


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

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