Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Июль 2018   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор
Калашников О.А.

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Алгоритмы и теория программирования


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

CradleA
Статус: Профессор
Рейтинг: 129
∙ повысить рейтинг » 		solowey
Статус: Студент
Рейтинг: 88
∙ повысить рейтинг » 		Роман Селиверстов
Статус: Советник
Рейтинг: 0
∙ повысить рейтинг »

∙ Алгоритмы и теория программирования

Номер выпуска:215
Дата выхода:09.07.2018, 20:45
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:24 / 10
Вопросов / ответов:3 / 7

Консультация # 96243: Здравствуйте, эксперты. Направьте в нужное русло :) Постараюсь объяснить на пальцах суть вопроса. Карта представляет из себя: множество пещер(подземных - кто не в курсе:) ), соединенных между собой проходами. Пещеры могут быть произвольной формы с препятствиями внутри. По карте разбросаны объекты различных типо...
Консультация # 58600: сдраствуйте эксперты! скажите пожалуйста где можно найти инфу по алгоритмам ато от знания языков программирования никакого толку нет. в "пособиях" обычно только стандартные "школьные" либо для ВУЗовцов если без ВУЗов никак, то можно и по вузмат-ке подсказать ссылочку :) как только уходишь от "примеров&q...
Консультация # 185967: Здравствуйте уважаемые эксперты! У меня возникли сложности с таким вопросом:
Тест Егорова на способность системы к обобщениям и поиску закономерностей.
 Постановку задачи мы сделаем максимально неформальной, чтобы был понятен больше ее смысл, чем описанные ограничения. Существует естественно-языковый текст. ...

Консультация # 96243:

Здравствуйте, эксперты.

Направьте в нужное русло :)
Постараюсь объяснить на пальцах суть вопроса.

Карта представляет из себя:
множество пещер(подземных - кто не в курсе:) ), соединенных между
собой проходами. Пещеры могут быть произвольной формы с препятствиями
внутри.
По карте разбросаны объекты различных типов, между которыми необходимо
перемещаться.

Подскажите какие алгоритмы мне могут понадобиться для реализации
объекта, который будет самостоятельно передвигаться по карте от
объекта к объекту.

Здесь вроде нужны будут такие алгоритмы, как "поиск кратчайшего пути"
(Если кто знает такой "А*", то помогите инфой по нему), "поиск на графе
и его обход", возможно "волновой алгоритм" пригодится, ну и т.д.

Короче меня интересуют даже любые мысли вслух, особенно если в тему :)
Ну а если и ссылок подкинете, то вообще красота.

Заранее всем спасибо.

Дата отправки: 24.07.2007, 20:28
Вопрос задал: Sea
Всего ответов: 1
Страница онлайн-консультации »

Консультирует _killhunter_:

Здравствуйте, Sea!
попробуйте посмотреть http://alglib.sources.ru/graphs/ там есть описание и реализации некоторых алгоритмов на графах.
Есть также неплохая книжка http://www.ftl.kherson.ua/index.php?option=com_remository&Itemid=120&func=fileinfo&id=8329
А вобщем действительно надо разбить карту сеткой достаточно малого размера и осуществлять поиск в графах

Консультировал: _killhunter_
Дата отправки: 25.07.2007, 11:31
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 58600:

сдраствуйте эксперты!
скажите пожалуйста где можно найти инфу по алгоритмам
ато от знания языков программирования никакого толку нет.
в "пособиях" обычно только стандартные "школьные" либо для ВУЗовцов
если без ВУЗов никак, то можно и по вузмат-ке подсказать ссылочку :)
как только уходишь от "примеров" сразу в тупике, а заставлять вас каждую проблему решать глупо.
(сам в вузе, 2курс, но математики вообщЕ нет "Дизайнер я... буду")
спасибо.

Дата отправки: 12.10.2006, 00:41
Вопрос задал: Astmaster
Всего ответов: 4
Страница онлайн-консультации »

Консультирует Errandir:

Здравствуйте, Astmaster!
Читайте Данальда Кнута "Искусство программирования"
Или вот эту книгу http://www.books.ru/shop/books/355110

Консультировал: Errandir
Дата отправки: 12.10.2006, 01:14
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Sergey V. Gornostaev (Специалист):

Здравствуйте, Astmaster! Рекомендую посмотреть здесь:

http://edu.mikhis.org/informatika_2/Part2.php
http://csi.ucoz.ru/Pakety.htm

а так-же смотрите почитать книги:
Кнут Д. Искусство программирования для ЭВМ
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ

Консультировал: Sergey V. Gornostaev (Специалист)
Дата отправки: 12.10.2006, 01:17
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует NextStep / www2:

Здравствуйте, Astmaster!

Вот довольно крупный ресурс посвящённый алгоритмам http://algolist.manual.ru/

Консультировал: NextStep / www2
Дата отправки: 12.10.2006, 07:03
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует _GReeN_:

Здравствуйте, Astmaster!
Загляни сюда тут море различной литературы! http://lib.kruzzz.com/
найдеш все что душе угодно!

Консультировал: _GReeN_
Дата отправки: 12.10.2006, 20:10
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 185967:

Здравствуйте уважаемые эксперты! У меня возникли сложности с таким вопросом:

Тест Егорова на способность системы к обобщениям и поиску закономерностей.

Постановку задачи мы сделаем максимально неформальной, чтобы был понятен больше ее смысл, чем описанные ограничения.
Существует естественно-языковый текст. (Например, первые семь страниц романа Толстого "Анна Каренина".)
Существует система, на вход которой мы подаем этот текст как последовательность символов. При этом у нас нет каких-то заранее выделенных символов, система не имеет представление о том, что "пробел" и "запятая" - это служебные символы, один разделяет слова, другой предназначен для пунктуации. Будем считать, что символ - это просто некоторый идентификатор, например, байт.
Система может иметь представление о том, что символ (байт) на входе - это экземпляр такого понятия как "символ", т.е. система может иметь "базу знаний", в которой будет существовать такой экземпляр как "символ", который как-то специфицирован, например, по своему байтовому значению. (Тогда "пробел" будет иметь ID = 32.)
Задача: Найти такие архитектуру системы, механизмы, методы обработки этого массива, чтобы система самостоятельно, без дополнительного обучения сгенерировало понятие "слово", специфицировало его и выделила все слова в исходном тексте.
Разрешается: Вводить в систему любые правила обработки, предположения об устройстве мира и эволюции, собирать статистическую и прочую информацию с исходного текста и заниматься прочей работой.
Запрещается: В явном или неявном виде задавать понятие "слово" (например, предполагать до обработки, что слово - это последовательность символов между пробелами или идти на другие "ухищрения"), иметь в "базе знаний" какие-то частные правила выделения объектов, получать информацию в систему, кроме исходного тек ста (например, диалог с оператором, толковый словарь и т.п.).
Заранее спасибо за помощь!

Дата отправки: 05.05.2012, 13:15
Вопрос задал: Куценко Андрей Валерьевич
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Vest:

Здравствуйте, Андрей Валерьевич!

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

Всё что разрешено делать со входящим текстом - это собрать статистику по символам. Статистика будет полезна в том случае, когда невозможно явно определить к какой группе принадлежит символ.

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

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

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

Другие правила, которые предлож ил Алексей на форуме позволят помочь вам узнать цифры или специальные символы. Но опять же, надо смотреть на живом примере и экспериментировать.

Консультировал: Vest
Дата отправки: 05.05.2012, 18:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Алексей Бурин:

Здравствуйте, Куценко Андрей Валерьевич!

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

(1) подсчёт символов
(1.2) выбор 3-х групп символов
1 - вероятные разделители
2 - вероятные буквы
3 - вероятные специальные символы
* группы должны иметь довольно существенную разницу, например
вес разделителя 100 -90 %
вес буквы 70 - 30 %
вес знака 10-1 % (знак в данном случае - знак препинания или служебный символ)
тут считаешь сколько раз встречается каждый символ и самый большой результат берёшь за 100%
** естественно, может получится несколько символов в группе 1.
в таком случае, если например, в первой группе оказалось 3 символа - каждый из них является разделителем с вероятностью в 33%
***статистику и распределение по группам не выбрасывай - сделай табличку со всеми найденными с имволами и занеси туда статистику для каждого
(2) уточнить разделитель
в случае, если в группе 1 оказалось несколько символов, нужно отсеять "лишние" (например ' ', о, а)
тут нужно применять правила.. можно придумать кучу правил.
правило 1 - длина слов. смысл в том, что знаки препинания делят цепочки символов на более мелкие слова, чем буквы
нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя.
причём, мы ищем "статистически" - то есть лучше выбрать не одно а 10 самых длинных "слов" и взять их среднюю длину.
например текст "нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя."
даст результат "пробел" - самое длинное слово - 13 символов, 'о' - 46 символов, 'а' - 24 символа.
то есть "о" - 100%, "а" - 52% и пробел - 28%.
разница очевидна.
правило 2 - знаки всегда идут до или после пробела.
тоже хорошее правило... но пока что невозможно быть уверенным на счёт знаков, то есть пробел никогда не будет стоять рядом с "ъ"
с другой стороны, ни "а" ни "о" тоже не стоят рядом с "ъ", что делает это правило оправданным.
нужно считать пары "знак"+"пробел" или "пробел"+"знак" для всех возможных пробелов со всеми возможными знаками
например, тот же текст " нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя. "
для пробела даст 5 совпадений ( ","+" "), ( "ь"+" " ), ("." + " ")
для "о" даст 1 совпадение ("о" + ",")
для "а" даст 0 совпадений
я в этом случае указал и "ь" потому что скорее всего буквы "ь", "ъ" ока жутся в группе знаков..
в любом случае - правило однозначно работает
...можно составить сколько угодно правил..
в итоге, используя набор правил можно выбрать наиболее вероятный разделитель
*я рекомендую ВСЕ результаты сохранять в табличке, в которой записана статистика по символам
в разных столбцах, конечно ))

(3) уточнить знаки (знаки препинания и специальные символы)
нужно применить другой набор правил к тексту
например
правило 1 знаки - это символы, которые всегда идут до или после "разделителя"
берёшь список всех символов, которые встретились в тексте и начинаешь просматривать текст
если встречается сочетание "символ"+"пробел" или "пробел"+"символ" - подтверждаешь этот символ
если встречается сочетание "не пробел"+"символ"+"не пробел" - вычёркиваешь этот символ из списка.
получается список из "вычеркнутых", "подтверждённых" ; и "не подтверждённых" знаков - заносим в ту же табличку со статистикой
"подтверждённые знаки", которые входят в группу 3 - можно считать доказанными
"вычеркнутые знаки" - это буквы типа "ъ"
"не подтверждённых" теоретически быть не должно... если появятся - стоит поискать ошибки

(4) Правила - "заглавные буквы"
можно применить правило поиска "заглавных букв" по шаблону типа
"пробел"+"возможная заглавная буква"+"буква"
бывают одиночные заглавные буквы ( "А", "И"), но их невозможно подтвердить..
подтверждение "заглавных букв" - считать "слово" после "заглавной буквы" и найти совпадение в тексте
если найдётся совпадение, но вместо заглавной буквы будет стоять другая буква - можно считать "заглавную букву" доказанной
и даже занести её в ту же табличку на против соответствующей &qu ot;строчной буквы"
если одной "заглавной букве" будет соответствовать несколько "строчных букв" то нужно считать, что это исключение
- вычеркнуть символ из списка "заглавных букв" и не применять к нему это правило.
если есть несколько исключений, то можно считать, что это правило не работает на данном тексте.


(5) Дополнительные правила - "цифры" это сложный разбор текста...
"цифры" могут входить во все 3 группы, но практически всегда идут вместе друг с другом
это работа для небольшой базу данных...
нужно прочитать текст и сделать табличку из всех сочетаний всех символов, которые встречаются в тексте,
подсчитав количество таких сочетаний.
при разборе нужно принять во внимание, что, например, "б" скорее всего никогда не встретится с "щ" но оба символа встретятся с "о"
тут можно использовать порог, например "цифра с 80% вероятность ю"
но, нужно помнить, что требуется проанализировать БОЛЬШОЙ объём текста
и всё равно - не факт, что удастся корректно выделить "цифры"

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

smile

Консультировал: Алексей Бурин
Дата отправки: 08.05.2012, 07:50
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное