2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 00:58 


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 05:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 08:37 


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение28.01.2018, 09:29 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение01.02.2018, 06:06 


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение03.02.2018, 09:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение03.02.2018, 13:31 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Практическая значимость задачи о количестве путей
Сообщение05.07.2019, 18:37 
Модератор
Аватара пользователя


11/01/06
5660
На основе второй задачи в комбинаторике базирует метод матрицы переноса (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 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group