Алгоритмы. Часть 1.1. Динамические соединения.

04.04.14

Разработка - Работа с интерфейсом

+206 –
Конспект первой лекции из свежего курса Принстонского университета США за 2014 год. Вольный перевод с английского с реализацией примеров на 1С. Курс в целом достаточно интересный и полезный для общего развития. Перевел и адаптировал только первую лекцию (в 1 части 11 лекций, 2 часть - еще не завершена преподавателями). Первоисточник на английском - https://www.coursera.org/course/algs4partI. Если сообщество посчитает материал полезным - займусь переводом следующих лекций (но это довольно трудоемко). Enjoy! :)

Файлы

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование Скачано Купить файл
Выгрузка информационной базы с примерами
.dt 279,44Kb
26 2 500 руб. Купить

Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний

Оформите подписку на компанию для решения рабочих задач

Оформить подписку и скачать решение со скидкой

Вы можете заказать платную доработку или адаптацию этой разработки под вашу конфигурацию на «Бирже заказов».

  • 0% комиссии — оплата напрямую исполнителю;
  • Исполнители любого масштаба — от отдельных специалистов до команд под проект;
  • Прямой обмен контактами между заказчиком и исполнителем;
  • Безопасная сделка — при необходимости;
  • Рейтинги, кейсы и прозрачная система откликов.

Алгоритмы – это методы решения проблем. Алгоритмы применяются практически в любой области человеческой деятельности. Умение составлять правильные и эффективные алгоритмы является важным качеством любого специалиста практически из любой области.

«Я считаю, что разница между плохим и хорошим программистом в том – считает ли он свой код или структуры данных более важными. Плохой программист заботится о коде. Хороший программист – о структуре данных и их взаимосвязях».
Линус Торвальдс

«Алгоритмы + структуры данных = программы».
Никлаус Вирт

 

Зачем изучать алгоритмы?

  1. Они имеют очень широкое распространение и влияние.
  2. Имеют глубокие корни и предоставляют широкие возможности.
  3. Помогают решить проблемы, которые не могут быть решены иным путем.
  4. Помогают стать хорошим программистом.
  5. Они могут раскрыть секреты жизни и вселенной.
  6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.

Лекция 1. Соединение-поиск.

Порядок преподнесения материала в лекциях:

  1. Сформулировать проблему/задачу.
  2. Найти алгоритм решения
  3. Достаточно ли он быстр? Достаточно ли памяти?
  4. Если нет – понять почему.
  5. Найти пути оптимизации.
  6. Повторить пока не будем удовлетворены результатом.

Так называемый Научный метод

Динамические соединения.

Допустим мы имеем массив из N объектов, а также 2 команды:
1. Процедура Объединить – создает соединение между двумя объектами.
2. Функция ОбъектыСоединены – проверяет наличие пути, который объединяет 2 объекта.

 

Вступайте в нашу телеграмм-группу Инфостарт

+206 –

См. также

Infostart Dashboard: Монитор показателей, виджеты и дашборды в 1С 8.3

Работа с интерфейсом Анализ учета Мониторинг 1С:Предприятие 8 1С 8.3 1C:Бухгалтерия 1С:Бухгалтерия 3.0 1С:ERP Управление предприятием 2 1С:Управление холдингом 1С:Зарплата и Управление Персоналом 3.x 1С:Комплексная автоматизация 2.х 1С:Управление нашей фирмой 3.0 1С:Управление торговлей 11 Платные (руб)

Создайте свой функциональный интерфейс в любой конфигурации 1С с помощью расширения Infostart Dashboard. Настраивайте панели виджетов с метриками, индикаторами и показателями на начальном экране. Узнайте возможность внедрения подсистемы у себя в конфигурации с помощью бесплатной обработки "Анализ внедрения подсистемы 1С Infostart Dashboard"!

31720 руб.

27.03.2025    89476    67    44    

75
Удобные фильтры: динамические кнопки-закладки для списков в 1С

Консолидация данных Работа с интерфейсом Программист Пользователь 1С:Предприятие 8 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Управление нашей фирмой 3.0 1С:Розница 3.0 1C:ERP Узбекистан Беларусь Кыргызстан Россия Казахстан Платные (руб)

Знакомая ситуация? Пользователи, особенно менеджеры, уверены: отборов много не бывает. Идут пожелания добавить в форму списка еще один быстрый фильтр, еще два, еще пять... В итоге интерфейс превращается в нагромождение полей отбора, а потребность в «самом главном» отборе, который «вот прямо сейчас нужен», все равно не закрыта. Универсальное расширение, которое решает эту проблему элегантно и технологично. С его помощью в любую форму списка можно легко добавить панель настраиваемых кнопок-закладок, каждая из которых применяет сложный фильтр-запрос, а так же показывает актуальное количество элементов в реальном времени.

6088 руб.

17.10.2025    2910    3    0    

2
Дизайнер форм 1С

Разработка Инструментарий разработчика Работа с интерфейсом Адаптация типовых решений Нейросети 1C:Бухгалтерия 1C:ERP 1С:ЗУП 1С:КА 1С:УНФ 1С:УТ 1С:Розница 1С:ДО 1С:ERP Управление предприятием 2 Платные (руб)

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

36600 руб.

28.08.2025    9375    2    2    

6
Дизайн Гайд для создания форм на 1С. Когда и как использовать различные элементы, примеры и антипримеры по использованию

Работа с интерфейсом Программист Стажер 1С:Предприятие 8 Бесплатно (free)

Это инструкция по дизайну форм в среде 1С. Гайд охватывает рекомендации и стандарты для оптимизации пользовательского интерфейса. В гайде содержатся указания по использованию элементов интерфейса, включая как основные, так и продвинутые аспекты. Предоставляются также примеры и антипримеры для наглядного понимания принципов дизайна

20.08.2024    54481    mrXoxot    44    

139
Прогресс-бар в поле динамического списка

Работа с интерфейсом Программист 1С:Предприятие 8 Бесплатно (free)

Пример простого и симпатичного прогресс-бара в динамическом списке, без картинок, используя редактирование запроса.

27.05.2024    28823    smielka    39    

119
Конструктор HTML, CSS и javascript

Инструментарий разработчика Работа с интерфейсом Программист 1С 8.3 Абонемент ($m)

Подходит для создания web-страниц для замены управляемых форм 1С, красивых отчетов, интерфейса мобильного приложения на платформе 1С и для простых страниц веб-сайтов.

1 стартмани

10.04.2023    18383    186    acces969    31    

132
{UI/UX} Свой всплывающий информер у элемента формы

Работа с интерфейсом Программист 1С:Предприятие 8 1C:Бухгалтерия Бесплатно (free)

Питничная фантазия на возможности в разработке интерфейсов формы с помощью Платформы 1С - делаем свою подсказку. Публикация содержит готовую библиотеку программного формирования данной подсказки.

12.08.2022    15670    top_1c    39    

98
Модель состояния для MVC

Работа с интерфейсом Программист 1С:Предприятие 8 1C:Бухгалтерия Абонемент ($m)

"MVC плохо применима в 1С" - познакомьтесь с моделью состояния и, возможно, ваше мнение поменяется! Представленное решение является эволюционным развитием идеи реализации MVC для 1С. В новой версии добавлены DSL для описания модели состояния, а также параметризация свойств параметров и элементов формы.

1 стартмани

05.07.2022    16300    kalyaka    8    

36
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. botokash 403 04.04.14 11:55 Сейчас в теме
Очень полезно! Спасибо автору за перевод, надеюсь на продолжение.
+ – Ответить
2. slazzy 43 04.04.14 12:07 Сейчас в теме
Это не просто полезно, это просто архиполезно. С огромным удовольствием прочитаю продолжение. Давно хочу заняться изучением алгоритмов, тк это логичное развитие программиста...но что-то погряз в изучении типовых. А тут такая возможность.

Спасибо :)
Leon75; 1cmailru; +2 – Ответить
3. Mi4man 176 04.04.14 13:28 Сейчас в теме
Спасибо автору!
Ну очень интересно!
Будем ждать продолжений!
+ – Ответить
4. fishca 1314 04.04.14 16:07 Сейчас в теме
Спасибо, статья очень полезная!
+ – Ответить
5. ksvd 04.04.14 16:10 Сейчас в теме
Конечно материал очень полезный. Спасибо
+ – Ответить
6. gaglo 04.04.14 17:12 Сейчас в теме
Большое спасибо! Надеюсь на продолжение, хотя понимаю, что труд огромный.
+ – Ответить
7. Патриот 470 04.04.14 17:19 Сейчас в теме
(0), спасибо! Небольшая поправка - "Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда" заменить на "Система проницаема только в том случае, если существует такой объект из верхнего ряда, который соединен с одним из объектов из нижнего ряда".
Т.е. надо поменять квантор всеобщности, на квантор существования (если вы понимаете о чём я =)). Либо пример "проницаемой системы" неверен, потому как есть объекты нижнего ряда, которые не соединены с объектами верхнего ряда (что противоречит данному определению "проницаемости").
DrAku1a; ColaKola; Aleksey.Bochkov; +3 – Ответить
8. утюгчеловек 42 05.04.14 13:32 Сейчас в теме
Готовящимся в аттестации по платформе на заметку.
Вероятно, можно попробовать использовать алгоритм при решении задач из "1С: Специалист" с формулировками типа:
"У некоторых товаров могут быть аналоги – другие позиции номенклатуры с теми же потребительскими свойствами и ценой, причем таких аналогов у товара может быть несколько. Считается, что если «Товар1» имеет аналог «Товар2», а «Товар2» имеет аналог «Товар3», то «Товар3» также является аналогом «Товар1»"
Выглядит несложно.

Я думал решить через матрицу связности, но перспектива каждый раз при вычислении связности несколько раз перемножать матрицы, взамен 
Возврат Корень(й1) = Корень(й2)

меня теперь не прельщает.
+ – Ответить
9. утюгчеловек 42 05.04.14 15:35 Сейчас в теме
(8) ошибся в предыдущем своем псто. Такой подход предполагает что "если p связан с q, то q связан с p", - это в общем случае не является истиной
+ – Ответить
10. davdykin 25 05.04.14 17:15 Сейчас в теме
Если можно расскажите, вкратце как проходит обучение в коурсера, и если можно "исходники" статьи, чтобы понять насколько сложна для понимания версия без перевода. Просто давно интересуюсь подобным образованием, но слабое знание английского останавливает :).
DrAku1a; ColaKola; +2 – Ответить
11. утюгчеловек 42 06.04.14 10:26 Сейчас в теме
(10) davdykin,
там просто всё. Курс не рассчитан на "шибко англоязычных", сложные слова можно подсмотреть, но в основном всё понятно по контексту. Я спокойно переводил со словарем, прошел, учась в универе, два года назад, Machine Learning и Model Thinking с большим удовольствием.

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

+ – Ответить
13. davdykin 25 06.04.14 20:57 Сейчас в теме
(11) утюгчеловек, Спасибо большое, возможно ваша информация поможет решиться послушать курс.

Честно говоря после прочтения статьи осталось несколько вопросов, если не сложно, кто все понял до конца поясните:

1. Сжатие пути. Насколько я понял из кода, через некоторое количество итераций мы получим не деревья а обычный массив, т.е. картинку которую мы видели в 1, т.к. в процедуре поиска корня не анализируется насколько глубокое дерево и стоит ли его перекидывать к корню?
2.
Утверждение (Hopcroft-Ulman, Tarjan): начиная с пустой структуры данных любая последовательность операций объединения-поиска M для N объектов потребует =< c ( N + M lg* N )
- в курсе рассказывается как получили данное уравнение, или, как любил говорить мой учитель по вышке "Нетрудно видеть", когда писал ответ следом за условием задачи?
3. Из
Графики времени выполнения алгоритмов в 1С.
как-то совсем не видно сильного преимущества 5 алгоритма над 1-ым, не говоря уже о разнице в 30 лет и 6 секунд
Последний вариант позволяет сократить время решения задачи с 30 лет до 6 секунд.
. В 1С даже хорошие алгоритмы работают плохо? :)
+ – Ответить
12. DoctorRoza 06.04.14 16:48 Сейчас в теме
Хороший материал, как раз для недопрограммистов 1С-ников! :)
barelpro; +1 – Ответить
14. -fox- 07.04.14 09:14 Сейчас в теме
Очень жалею что так наглядно, просто и интересно в нашем институте не рассказывали лекций. Спасибо! Статья просто супер!
+ – Ответить
15. msirkizyuk 09.04.14 07:48 Сейчас в теме
Большое Вам спасибо! Объём проделанной работы впечатляет.
+ – Ответить
16. m0r0z 09.04.14 09:18 Сейчас в теме
Спасибо за лекцию.
Все очень подробно рассказано.
Есть повод подучить алгоритмы.
+ – Ответить
17. rasswet 82 09.04.14 16:23 Сейчас в теме
здорово, всё очень наглядно и хорошо описано, в детали не вникал. Но по первому впечатлению всё очень доходчиво.
+ – Ответить
18. izidakg 174 09.04.14 18:24 Сейчас в теме
именно так и должны делаться все учебные материалы
терпения автору - учить программированию бывает сложнее самого программирования
+ – Ответить
19. ildarovich 8065 11.04.14 08:38 Сейчас в теме
В статье "Наш ответ американским лекторам" приведено гораздо более быстрое решение той же задачи на 1С
agrustny; ivanitland; Aleksey.Bochkov; +3 – Ответить
20. Aleksey.Bochkov 3713 11.04.14 23:47 Сейчас в теме
(19) ildarovich,
в качестве оправдания :) - я пытался максимально сохранить соответствие примеров кода на java и 1С.
Если примеры будут использовать какие-либо специфичные объекты от 1С, то это получится слегка однобоко и неприменимо к другим языкам программирования.
В последующих лекциях будет аналогичная ситуация.
+ – Ответить
21. ildarovich 8065 13.04.14 15:40 Сейчас в теме
(20) и сама лекция и Ваша интерпретация выше всяких похвал. И я бы очень хотел, чтобы мое решение выглядело не как критика или замечание, а как дополнение к лекции, сделанное мелким шрифтом и нужное тем, кто решит применить результаты сразу на практике. А способ подачи своего решения и задиристое название статьи-спойлера - это просто юмор и способ привлечь к решению внимание.
С другой стороны, я сам долгое время думал, что все алгоритмы давно открыты. Пока не узнал, что алгоритм Боурера-Мура (быстрого поиска подстроки в строке) был открыт аж в 1984 году, когда люди уже лет 30 решали такие задачи. Из этого я сделал вывод, что алгоритмика не закостенела, что можно ждать новых открытий и искать новые решения.
+ – Ответить
23. адуырщдв 28 14.04.14 12:24 Сейчас в теме
(21) ildarovich,
Да не то слово! Я, к примеру сам был в шоке когда узнал, что алгоритм Патерсона был придуман только в 1981 году! А это ведь азы computer science!
+ – Ответить
22. адуырщдв 28 14.04.14 12:18 Сейчас в теме
"Быстрое объединение с оценкой веса" в английской литературе звучит как weighted quick-union, что в нашей литературе переводят как "Взвешенное быстрое объединение". А где взвешенное быстрое объединение с делением пополам (weighted quick-union with path compression by halving)? :) Непроходят чтоль такое в принстоне? :) Ладно я шучу, как сжать путь любой программист придумает кучу методов, если он не очередной "гугл копипаст говнокодер".
+ – Ответить
24. chmv 16.04.14 08:53 Сейчас в теме
Колосальная работа. Только не понятно, зачем?
mafia; agrustny; адуырщдв; +3 – Ответить
25. Патриот 470 21.04.14 13:56 Сейчас в теме
(24) chmv, если после прочтения всей статьи остался вопрос - "зачем она написана", то это печально. Вам, я думаю, эта статья незачем. С таким же успехом можно зайти на любую страницу, с темой не представляющей конкретно для вас интереса (например самолётостроения, или вышивки бисером, или бокса, да чего угодно! Если сказать языком теории множеств, то - универсальное множество минус узкий круг ваших интересов) и спрашивать, зачем она была написана. Но я всё же постараюсь кратенько обрисовать, зачем. Для саморазвития как программист, для развлечения и отвлечения от монотонной работы, может быть и куча других причин. Судя по популярности этой статьи, каждый, кто поставил под ней плюс, извлёк некую ценность из статьи для себя. Если же вы имели ввиду конкретную прикладную ценность для решения задач программистом, который забрёл на этот форум, то таковая имеется. Во-первых, эти алгоритмы могут пригодиться если специалист хочет расширить круг используемых языков, выйдя за рамки 1С, во-вторых статья демонстрирует возможность реализации на 1С стандартных алгоритмов. Наконец, и конкретно в автоматизации бизнеса на 1С встречаются задачи, где необходим поиск оптимального пути (например у моего коллеги была задача, где необходимо было найти наиболее удачный путь денежной транзакции через несколько подразделений одного предприятия в зависимости от набора ограничений - пришлось учить старые добрые алгоритмы).
+ – Ответить
27. ЧИА 170 22.11.14 09:03 Сейчас в теме
(24) chmv,
Колосальная работа. Только не понятно, зачем?


думаю, статья - наглядный и поучительный пример, что иногда надо думать )
т.е. смена алгоритма получения результата часто дает на порядок большее ускорение, чем другие методы

в применении к 1с - если что-то тормозит, не обязательно апгрейдить сервера, можно и запросы переписать, или над регистрами поработать
неоднократно изменение 1 запроса в типовых конфигурациях ускоряло проведение документа с 15-40 минут до 0.1-0.3с
+ – Ответить
26. agrustny 19 22.04.14 11:07 Сейчас в теме
Позабавило:
5. Они могут раскрыть секреты жизни и вселенной.
6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.
Не переводили бы Вы такую дурь ;) - взяли бы лучше хорошую книжку какую-нибудь из прошлого века 19xx
Java - это немножко для другого...
(упрек по поводу выбору гнилого источника, к реализации на 1С - вопросов нет, т.к. это уже для забавы)
+ – Ответить
28. NN2P 423 18.04.17 11:56 Сейчас в теме
Статья отличная.

Прошу простить мое буквоедство и откорректировать:

"...потребует =< c ( N + M lg* N ) числа доступов к массиву.

Где ln*N:.."

на
"...потребует =< c ( N + M lg N * N ) числа доступов к массиву.

Где lg*N:..
"
+ – Ответить
29. Aleksey.Bochkov 3713 20.04.17 19:30 Сейчас в теме
(28) Насколько я понимаю текущий вариант является правильным.
Meaning of lg * N in Algorithmic Analysis
Итерированный логарифм
NN2P; +1 – Ответить
30. NN2P 423 20.04.17 21:12 Сейчас в теме
(29)
Итерированный логарифм
Ого, прошу прощения. Спасибо за просвещение.
+ – Ответить
31. pvlunegov 160 07.11.17 23:28 Сейчас в теме
Взял вашу конфигурацию, на ее основе сделал алгоритм построения дерева путей при тыке мышью на ячейке.
Дерево путей сделал визуальное отображение в виде красных ячеек на месте белых ячеек (свободные).
Коричневые ячейки - препятствие.
Должен заметить что мой алгоритм очень ущербен и на данный момент при размере веток дерева >5 1с уходит в долгий расчет более чем на час.
При размере веток дерева Путей <=5 считается в пределах нормы.

Как я понимаю, после каждого шага расчета (у меня 1 шаг расчета = увеличение всех веток дерева на 1) необходимо уплощать дерево (уменьшать количество листьев, увеличивать количество веток).
Алгоритм уплощения надо додумать.
Думаю, при верном построении алгоритма удастся создать полное дерево связности.

Но пока что нет на это время.
Зато получилось сделать визуальное отображение поиска на малых деревьях в небольшом диапазоне расстояний от точки старта.

См. рисунок
Прикрепленные файлы:
+ – Ответить
32. pvlunegov 160 07.11.17 23:37 Сейчас в теме
Как вариант упрощения алгоритма можно взять предложенный в игровой индустрии так называемый "Муравьиный поиск".
Попробую реализовать его для уменьшения количества вычислений.
В данном алгоритме необходимо реализовать распараллерирование вычислений. Каждый "Муравей" есть отдельный процесс производящий вычисление пути и помечающий его в дерево.
Соседние муравьи "Видят" проложенный собратом путь и не идут по нему.
Таким образом можно запустить несколько параллельных процессов обсчета дерева пути.
Кроме того, в прикладном значении алгоритм важен прежде всего для вычисления кратчайшего пути между 2 точками.
Это можно использовать в муравьином алгоритме.
Например, вычислять "РАсстояние" до целевой точки в каждой точке пути и таким образом вычислять "Рейтинг" каждой точки.
Муравей, при выборе следующей точки для обсчета из соседних, выбирает точку с наибольшим рейтингом.
Таким образом, сокращается радиус поиска и количество вычислений.

Еще одно упрощение задачи - муравей, первый нашедший путь будет считаться выигравшим гонку.
Все поиски завершаются и выбирается данный путь (Может и не самый лучший) - таким образом будет реализация алгоритма поиска первого попавшегося пути (возможно не самого кратчайшего), зато с минимальными затратами времени.
+ – Ответить
33. pvlunegov 160 07.11.17 23:45 Сейчас в теме
(32) Должен заметить особые случаи муравьиного алгоритма.
Если муравей прошел какой то тропой, не самой оптимальной. Его собрат "наткнулся" на след муравья.
Должен ли он пересекать его путь?
Варианты:
1. Муравьи не пересекают свои пути поиска
- В этом случае необходимо реализовывать "жадный" вариант поиска - искать все возможные соседние пути без пропусков
- Только после исчерпания всех соседних клеток искать другие
- Минусы - медленная прогрессия поиска, топтание на месте, тупики обхода, возвращение в исходные точки.
- Реализовать поиск быстрый поиск по рейтингу пути тяжело
2. Муравьи пересекают пути собратьев. Но делать это нежелательно.
Чтобы уменьшить это явление, уменьшать рейтинг тех клеток, которые прошел собрат.
Муравей пересечет путь собрата при острой необходимости (когда другие варианты менее желательны)
- Действует алгоритм поиска пути по рейтингу
- Более быстрый поиск, обход тупиков и слепых пятен.

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

Займусь данным вопросом, о результатах отпишусь.

Всем спасибо за внимание.
+ – Ответить
Для отправки сообщения требуется регистрация/авторизация