Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Последний раз редактировалось eugrita 28.01.2018, 01:46, всего редактировалось 4 раз(а).
На ЕГ по информатике по графам традиционно предлагают 2 задачи - 1)кратчайший путь между 2 вершинами 2)количество путей между 2 заданными вершинами Если 1-я задача имеет многочисленные применения то где может иметь практические применения 2-я задача? (несмотря на элегантный один из способов решения через возведение матрицы смежности в степени) Могу только предположить косвенно в задаче о максимальной пропускной способности в сети. Но там считаются потоки а не количества путей
Dmitriy40
Re: Практическая значимость задачи о количестве путей
28.01.2018, 05:11
Выскажу догадку: если кратчайший путь нужен для оптимальности, то количество путей - для вопросов надежности. В том числе поиск узких мест, не обязательно в смысле объёма траффика. Применить можно да даже к структуре администрации чего-либо, если окажется что большинство решений по самым разным вопросам проходят через одного-двух человек (и не на вершине пирамиды) - это узкое место, потенциально уязвимое. Связность дорожной сети тоже сюда относится, не пропускная способность, а именно связность, какие из объектов инфраструктуры являются стратегическими, а какие относительно легко заменяемы (хотя конечно тут вопрос траффика уже не игнорируется).
eugrita
Re: Практическая значимость задачи о количестве путей
28.01.2018, 08:37
да, когда-то давно я занимался надежностью и есть такое понятие как структурная надежность учитывающая резервирование участков сети. Но все же это хоть близкая но другая задача - там надо оценивать вероятности отказа, ВПР
atlakatl
Re: Практическая значимость задачи о количестве путей
28.01.2018, 09:29
Последний раз редактировалось atlakatl 28.01.2018, 09:30, всего редактировалось 1 раз.
Во-первых, для прикидки затрат времени для дальнейших вычислений. Во-вторых, надо же чем-то наполнять программу и сам ЕГЭ. Информатика самый странный предмет по подбору материала. Притом что овладение ПК, знакомство с основными пакетами, программирование пригодится большинству учеников ещё в школе. Но предмет как специально делают скучным и тупым. Хотя достаточно разбить весь курс на полсотни комплексных задач, решая которые, школьник овладевает предметом. Диалоговый интерфейс, основные ЧМ, работа с БД, графика. Этого достаточно для обучения с интересом. Все задачи включают все эти компоненты, - и последовательно усложняются. ПО: Excel и PascalABC. А "теорию" давать по ходу, между делом. Это знание менее важно.
eugrita
Re: Практическая значимость задачи о количестве путей
01.02.2018, 06:06
Последний раз редактировалось eugrita 01.02.2018, 06:07, всего редактировалось 1 раз.
Численные методы - это для студентов. Хотя я учился при социализме и численные методы не входили в понятие информатика, а обычно читались на курсах повышения квалификации - т.е где задачи оптимизации. Работа с БД - видимо надо поделить на 1)практические навыки работы с БД ,те оператор БД и 2)проектирование БД - т.е. специальности Microsoft 29 проч Язык SQL относить к 1) и 2) правда тут его диалекты для MS Access, SQL Server, и проч
arseniiv
Re: Практическая значимость задачи о количестве путей
03.02.2018, 09:00
О Диэдр, нафлудили же в теме, совершенно не касающейся того, какие языки и программы применять в обучении.
Pphantom
Re: Практическая значимость задачи о количестве путей
Re: Практическая значимость задачи о количестве путей
05.07.2019, 18:37
На основе второй задачи в комбинаторике базирует метод матрицы переноса (transfer-matrix method). В этой видео-лекции (на английском) я описал несколько задач, которые можно "раздолбать" этим методом: Transfer-Matrix Method as a Combinatorial Hammer: Part 1, Part 2