Личный кабинет

Хабаровская школа программистов

Как учить программированию
Виталий Потопахин ( Пользователь )
Добрый день всем.

Прошу прощения за громкое название "Школа программистов". Наверное для 20-30 учеников и одного учителя это громко сказано, но мы действительно считаем себя школой. Разрешите предложить вашему вниманию наш ресурс www.lotos-khv.narod.ru. По крайней мере три пункта этого сайта могут быть полезны многим.
1) Коллекция решений логически сложных задач. Это задачи которые приняты называть олимпиадными. Это не просто решения. Мы за много лет выработали определенную форму описания в которую сейчас входит детальное словесное описание (идея, алгоритм, технические детали и т.д.) и тексты программ на одном или двух языках. Это С и Паскаль, а сейчас мы переходим на набор С и Компонентный Паскаль.

2) Коллекция алгоритмов. Алгоритмы описаны на естественном русском языке с минимумом математики. Текстов программ пока нет, я полагал, что это не нужно, но быть может мы снабдим их и программами.

3) Коллекция исследовательских проблем. Это не чисто программисткие проблемы, но связанные с необходимостью разрабатывать алгоритмы. А главная их особенность это то, что это серьезные проблемы большой математики. Мы стараемся таковые представлять в наиболее популярном виде, но это не делает оные проще.

Наши коллекции невелики, по той простой причине, что мы заполняем наш сайт не торопясь, тщательно отбирая материал.
Михаил Густокашин ( Пользователь )
Ваш алгоритм Йена будет неправильно работать на поиске двух путей для вот такого графа:
[attachment=1810:attachment]
Он найдет только один, а их тут два. Причем второй будет полностью содержать первый.
Алгоритм Йена предназначен для поиска k кратчайших простых цепей (т.е. без повторения вершин).
Татьяна Дедюлькина ( Пользователь )
(Потопахин Виталий @ 23.03.2007, 15:40) <{POST_SNAPBACK}>
Наши коллекции невелики, по той простой причине, что мы заполняем наш сайт не торопясь, тщательно отбирая материал.

Виталий Валерьевич ! Вы большие молодцы bravo.gif И идея , и сайт отличные!
Работать, работать и работать.
С Вашего позволения, ссылку на Ваш сайт я помещу на ветке "Нить Ариадны в информационном мире" http://pedsovet.org/forum/topic1663.html
Виталий Потопахин ( Пользователь )
(Михаил Густокашин @ 23.03.2007, 19:25) <{POST_SNAPBACK}>
Ваш алгоритм Йена будет неправильно работать на поиске двух путей для вот такого графа:
[attachment=1810:attachment]
Он найдет только один, а их тут два. Причем второй будет полностью содержать первый.
Алгоритм Йена предназначен для поиска k кратчайших простых цепей (т.е. без повторения вершин).


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

Теперь, что касается формулировки алгоритма. Я все же утверждаю, что он ищет пути имеющие отличия, а не полностью отличные. Требование не повторять вершины делает алгоритм банальным. Тогда все слишком просто. Находим первый, далее выбрасываем все вершины в нём находящиеся и в том что осталось продолжаем поиск. Наш вариант интереснее. Кстати, если положить, что алгоритм Йена должен искать пути с неповторяющимися вершинами, то ваш пример будет просчитан так же. То есть будет найден только один путь.

Конечно, сказанное не аргумент в споре о том, что назвать алгоритмом Йена. Йен не обязан был следовать моей логике. Это конечно вопрос о первоисточнике определения. Я если честно не помню точно книги из которой я взял наше понимание, помню только, что книга была серьезная. Может быть я и не прав. Но главным образом я утверждаю, что наша формулировка более содержательна и если вы докажете, что изначально его определение звучит иначе, то мы свое понимание оставим, только изменив название алгоритма.
Михаил Густокашин ( Пользователь )
да я не против, просто человек сторонний может прочитать и использовать такой алгоритм, например, при решении задачи, где нужно найти k кратчайших путей в графе и не учтет, что Йен сделает это правильно только в случае если граф ациклический.
я когда говорил про повторение вершин, то имел в виду, что в одном и том же пути может повторяться одна и та же вершина.
вообще, вам надо форум приделать к сайту, чтобы там общаться можно было smile.gif . а так - весьма доходчиво все написано.
Виталий Потопахин ( Пользователь )
(Михаил Густокашин @ 24.03.2007, 09:45) <{POST_SNAPBACK}>
да я не против, просто человек сторонний может прочитать и использовать такой алгоритм, например, при решении задачи, где нужно найти k кратчайших путей в графе и не учтет, что Йен сделает это правильно только в случае если граф ациклический.
я когда говорил про повторение вершин, то имел в виду, что в одном и том же пути может повторяться одна и та же вершина.
вообще, вам надо форум приделать к сайту, чтобы там общаться можно было smile.gif . а так - весьма доходчиво все написано.


А вообще то я задумался. Мы не даем не оценок времени выполнения, ни условий применимости. Это из соображений упрощения, а правильно ли это!? Наверное условия применимости и быть может примеры все-же нужны.
Роман Еннер ( Пользователь )
Где же вы были так долго? Знаем Вас еще по ДООИ smile.gif

Заинтересовало на вашем сайте вот это:
Модель БОЛЬШОЙ ИГРЫ
...
На сегодня в качестве промежуточного варианта мы умеем довольно хорошо программировать интеллектуальные игры. У нас есть две сильно играющие программы: это игра Реверси и Го-Бан и несколько довольно прилично играющих программ: Шашки - Фокус, Халма, Реверси


Я со своими ребятами решал другие задачи, одна из них игра в крестики-нолики (не смеяться!) в КУБЕ 4х4х4. (В перспективе хотелось бы в гиперкубе 4х4х4х4)
Задача стояла написать программу анализирующее текущее состояние "поля" и делающую один ход. После этого писалась программа по очереди запускающая две разные программы написанные разными учащимися. Таким образом получался "турнир программ". Это, кстати, идея одного из наших учеников.
Большего интереса у учащихся я еще не видел.
Кстати, у Микрософт есть такая программа под Win3.1, там такие режимы: 3х3, 3х3х3, 4х4х4 (см. вложение)
3х3 - есть простой алгоритм и этот вариант не интересен
3х3х3 - всегда выигрывает первый, тоже не интересен
4х4х4 - наши программы обыгрывали программу от MS, так что программисты от MS, видимо не очень утруждали себя smile.gif
Виталий Потопахин ( Пользователь )
Доброе время суток Роман Александрович

Был я где и всегда, в своем родном городе Хабаровске. Действительно несколько лет ни с кем не общался, занимался созерцанием бытия и строительством своей школы. Знаете иногда бывает полезно ни с кем не общаться. Что касается ваших игровых разработок, то должен сказать, что это довольно серьезно. Ваши ребята как минимум (ваш максимум мне не известен) умеют решать задачи перебора, а это означает, что они смогут построить и дерево перебора в более сложных играх. Я бы посоветовал вам попытаться создать программу играющую в сложную игру. Программирование игр не имеющих жеского алгоритма это ведь в сущности задачи искусственного интеллекта, но несмотря на страшное слово у них есть одно хорошее качество. Зделать игру играющую сильно, действительно не просто, но сделать игру играющую против человека достаточно прилично достаточно легко. Стандартная технология "дерево перебора + оценочная функция + простейший метод отсечения ветвей" дают удивительно много.
А если вы позволяете мне продолжать советы, то я посоветовал бы реализовать игру Рэндзю. Рэндзю это Го-моку с правилами фола, а Го-моку это крестики - нолики на большой доске. Так что переход от ваших разработок к Рэндзю будет очень естественным. А мы в ближайшие месяц - два выложим наш вариант. Программа не гросмейстерская, но играет очень прилично. Жалко только сделана на С. Сделана она уже год назад, но мы с автором (кстати девушка) не можем пока разобраться с описанием. Она увлеклась разработкой визуального варианта.
Виталий Потопахин ( Пользователь )
Разместили на www.lotos-khv.narod.ru формулировку новой исследовательской проблемы. Что - то вот об этом - "Как конструировать модель реальных процессов из конечных автоматов". Проблема сформулирована в терминах растений и животных. От этого формулировка сильно потеряла в четкости и содержательности, но зато стала более менее понятна.
Виталий Потопахин ( Пользователь )
На нашем сайте lotos-khv.narod.ru в коллекции алгоритмов появился новый раздел - алгоритмы сортировки. Начинаем с трех алгоритмов: два простейших это алгоритм пузырька и алгоритм вставки и один уже не такой банальный - быстрая сортировка.

footer logo © Образ–Центр, 2017. 12+