Практическая значимость задачи о количестве путей

[eugrita]

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

[Dmitriy40]

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

[eugrita]

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

[atlakatl]

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

[eugrita]

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

[arseniiv]

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

[Pphantom]

arseniiv в сообщении #1289645 писал(а):

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

Именно, посему оный флуд отделен в «О языках программирования для обучения»

[maxal]

На основе второй задачи в комбинаторике базирует метод матрицы переноса (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

[B@R5uk]

Только мне кажется, что вторая задача оценивает сложность решения "в лоб" первой задачи? И что это за изящное решение с возведением матриц в степени?