2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 00:58 
На ЕГ по информатике по графам традиционно предлагают 2 задачи - 1)кратчайший путь между 2 вершинами
2)количество путей между 2 заданными вершинами
Если 1-я задача имеет многочисленные применения
то где может иметь практические применения 2-я задача?
(несмотря на элегантный один из способов решения через возведение матрицы смежности в степени)
Могу только предположить косвенно в задаче о максимальной пропускной способности в сети. Но там считаются потоки а не количества путей

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 05:11 
Выскажу догадку: если кратчайший путь нужен для оптимальности, то количество путей - для вопросов надежности. В том числе поиск узких мест, не обязательно в смысле объёма траффика. Применить можно да даже к структуре администрации чего-либо, если окажется что большинство решений по самым разным вопросам проходят через одного-двух человек (и не на вершине пирамиды) - это узкое место, потенциально уязвимое. Связность дорожной сети тоже сюда относится, не пропускная способность, а именно связность, какие из объектов инфраструктуры являются стратегическими, а какие относительно легко заменяемы (хотя конечно тут вопрос траффика уже не игнорируется).

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 08:37 
да, когда-то давно я занимался надежностью и есть такое понятие как структурная надежность учитывающая резервирование участков сети. Но все же это хоть близкая но другая задача - там надо оценивать вероятности отказа, ВПР

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 09:29 
Аватара пользователя
Во-первых, для прикидки затрат времени для дальнейших вычислений.
Во-вторых, надо же чем-то наполнять программу и сам ЕГЭ.
Информатика самый странный предмет по подбору материала. Притом что овладение ПК, знакомство с основными пакетами, программирование пригодится большинству учеников ещё в школе.
Но предмет как специально делают скучным и тупым. Хотя достаточно разбить весь курс на полсотни комплексных задач, решая которые, школьник овладевает предметом.
Диалоговый интерфейс, основные ЧМ, работа с БД, графика. Этого достаточно для обучения с интересом. Все задачи включают все эти компоненты, - и последовательно усложняются. ПО: Excel и PascalABC.
А "теорию" давать по ходу, между делом. Это знание менее важно.

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение01.02.2018, 06:06 
Численные методы - это для студентов. Хотя я учился при социализме и численные методы не входили в понятие информатика, а обычно читались на курсах повышения квалификации - т.е где задачи оптимизации.
Работа с БД - видимо надо поделить на 1)практические навыки работы с БД ,те оператор БД и 2)проектирование БД - т.е. специальности Microsoft 29 проч
Язык SQL относить к 1) и 2) правда тут его диалекты для MS Access, SQL Server,
и проч

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение03.02.2018, 09:00 
О Диэдр, нафлудили же в теме, совершенно не касающейся того, какие языки и программы применять в обучении. :?

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение03.02.2018, 13:31 
 i 
arseniiv в сообщении #1289645 писал(а):
О Диэдр, нафлудили же в теме, совершенно не касающейся того, какие языки и программы применять в обучении.
Именно, посему оный флуд отделен в «О языках программирования для обучения»

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение05.07.2019, 18:37 
Аватара пользователя
На основе второй задачи в комбинаторике базирует метод матрицы переноса (transfer-matrix method). В этой видео-лекции (на английском) я описал несколько задач, которые можно "раздолбать" этим методом:
Transfer-Matrix Method as a Combinatorial Hammer: Part 1, Part 2

Можно также почитать об этих задачах в статьях:
Making Walks Count: From Silent Circles to Hamiltonian Cycles
Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations

 
 
 
 Re: Практическая значимость задачи о количестве путей
Сообщение05.07.2019, 21:25 
Аватара пользователя
Только мне кажется, что вторая задача оценивает сложность решения "в лоб" первой задачи? И что это за изящное решение с возведением матриц в степени?

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group