Издевательства над студентами в заданиях

Не первый раз мне по теории графов попадается задача следующего содержания: "построить ВСЕ остовные деревья" и дан граф с 10 вершинами и 15 ребрами. На мой взгляд, эта задача - издевательство над студентами, и как интересно преподаватель проверяет =) А какие задания, выносящие мозг попадались Вам?)

Комментарии
122

Не задание, но фраза, не помню от кого на факультете слышанная: "Построим, для простоты, матрицу 7-го порядка"
Иную матрицу 7 порядка можно и в одну строчку записать: например, diag(1,2,3,4,5,6,100).
Добавлю: однажды знакомой надо было сделать задание
1. Расчитать цепь методом контурных токов
2. Расчитать цепь методом узловых напряжений
3. Расчитать численными методами чего-то там
Численные методы на их специальности к тому времени не проходили. Она просто не внимательно слушала, что пункт 3 из методички, делать не надо. От этого нас отговорил человек, который сам умеет решать все пункты методички, и который предупредил, что это будет дорого. И что наверняка преподаватель такого задать не мог
Может ваш клиент и правда ошибся с количеством рёбер?
Нет, такое задания не в одном универе и не первый год =)
P.S. За матрицу 7 порядка - зачет)))
Кстати, хорошая комбинаторная задачка: сколько в таком графе может быть остовных деревьев.
Комбинаторно затрудняюсь (только для полного графа), но можно найти количество остовных деревьев по матрице Кирхгофа
Ну, 10 вершин и 15-то ребер - очевидно, не полный граф, а расклады могут быть разные. Вот и задачка умному студенту: найти минимально возможное и максимально возможное число о. д.
Ну это тоже будет "издевательская" задачка, так как не известно сколько вершин изолировано, может все 15 ребер из одной вершины?
Граф считаем связным, но способов очень много, так что даже не возьмусь решать такую задачу комбинаторно))
Это не издевательская, а именно сложная задачка: в том и смысл, чтобы пересчитать все возможности.
Ну ка попробуйте ка с помощью комбинаторных схем рассчитайте))))
Не, мне лень. Тут с полпинка не посчитаешь, думать надо.
Мне почему-то кажется, что это невыполнимо... И общую формулу не найти, даже если ее привязывать к степеням вершин. Оценить (очень грубо) может и получится, но какой смысл?
Может, и невыполнимо, а может, и выполнимо. Попробовать бы можно. А смысл хотя бы в том, чтобы потренироваться в решении комбинаторных задач.
Ну видно же что хотите решить) Давайте, покажите, что задание выполнимо!!! А то что-то не верится)))
Да ладно Вам))) Тема-то не о том)))
Мне интересно, но лень и некогда. Если я сейчас эту задачку поставлю в конец очереди тех задачек, которые интересно, но лень и некогда, то лет через 8, может, и доберусь до неё.
Вот-вот... нам с Вами интересно, но лень. А студентам неинтересно и лень. Что напрочь отбивает желание заниматься предметом.
К сожалению, это так... Но благодаря этому, у нас есть работа=)
Зато хоть поговорим по-человечески. Если это, хе-хе, не является нарушением правил сайта.
Желание-то есть, ресурсов маловато.
Выполнимо. Ещё как! Кстати, с нужным ПО это делается ещё проще
Например MS Visio. Строится граф копируется на нужное количество листов. И постепенно из него делаются остновные деревья путём удаления лишних рёбер
P.S. За 1000 руб. сделал бы. :D
Вы же читали правила форума, нажав синюю кнопку в разделе "Форум"? У вас есть подозрение, что любое из оставленных вами сообщений в этой теме, нарушает правила? :)
Надеюсь goodhelher теперь оценит свой труд ближе к рыночным ценам, и в теме https://studwork.ru/forum/2463 появится ещё один восторженный комментарий :)
Если честно, не читал. Я на такие вещи обычно не трачу время и считаю, что по умолчанию не нарушаю ничего.
А Вы уверены, что будет правильно?
Естественно будет правильно. Единственные ошибки могут быть в дублировании остовных деревьев по невнимательности.
Заказ довольно опасный в плане доказательства правильности решения. Вот напишет заказчик, что неправильно, еще можно составить несколько деревьев. Как автор сможет доказать, что нельзя? Считаю, что 1000р. тут не оправдывает риск...Можно и отзыв отрицательный заработать ни за что...
Ну, если заказчик опровергнет теорему Кирхгофа и предложит новые доказательства своей теоремы по нахождению количества остовных деревьев, то ему явно место не на сайте заказов работ, а где-нибудь в кабинетах на получении филдсовской премии. =)
Возьмём матрицу смежности графа G, заменим каждый элемент этой матрицы на противоположный, а на диагонали вместо элемента Ai,i поставим степень вершины i (если имеются кратные рёбра, то в степени вершины они учитываются со своей кратностью). Тогда, согласно матричной теореме Кирхгофа, все алгебраические дополнения этой матрицы равны между собой, и равны количеству остовных деревьев этого графа. Например, можно удалить последнюю строку и последний столбец этой матрицы, и модуль её определителя будет равен искомому количеству
Вы про эту теорему?
"Тогда, согласно матричной теореме Кирхгофа, все алгебраические дополнения этой матрицы равны между собой, и равны количеству остовных деревьев этого графа."
Именно про неё.
Так про эту теорему или нет?
Я же ответил. Именно про неё. Сторится матрица Киргхофа, находится количество остновных деревьев. Всё. Дальше рисовать. Способ рисования наиболее простой я описал.
К сожалению у нас не задана конкретная матрица смежности...их надо составлять...а потом для каждой матрицы конечно Кирхгофа применять. Смысл задачи в составлении матриц смежности. Сколько их будет? Все ли мы учтем? Вот тут то заказчик и скажет, что не все учтено...
Также можно программным методом. Составить программу и он сам поиском в глубину, например, построит все остовные деревья. Останется только перерисовать. Но я думаю человеческому, а тем более намётанному глазу проще будет описанный мной метод с программой и удалением лишних рёбер. В любом случае, это быстрее, чем писать программу и отлаживать её работу.
В принципе Вы все верно написали, я с Вами полностью согласна, но как быть с матрицами смежности??
Суть в том, что матрица смежности для конкретного графа как бы одна. о_О
Если задан граф рисунком или как-то ещё, то построить по нему матрицу смежности проще простого. В графе не может быть разных вариаций матрицы смежности. Любой граф задаётся одной матрицей смежности
Ещё раз повторюсь, что это задание не столько сложное, сколько трудоёмкое.
И матрицу Кирхгофа тоже одну строить надо будет. Всего-навсего. От того каким образом задаётся граф не зависит количество каркасов. Иначе мы бы жили в параллельном мире с иными законами. =)
Это как это как бы одна, извините...Так одна или нет???
Речь не о конкретном графе! Сергей предложил комбинаторно найти общую формулу
Общую формулу для нахождения чего? Есть конкретный граф, по конкретному графу можно сказать сколько у него каркасов. А общую формулу для чего? У любого графа из 10 вершин и 15 рёбер может быть сколько угодно вариаций, а значит разное количество остовных деревьев. Если граф задан конкретно, то для него четко можно найти по теореме Кирхгофа количество каркасов.
У нас нет конкретного графа. У нас есть 10 вершин, 15 ребер и пояснили, что граф связный, то есть как минимум 9 ребер связываю 10 вершин, а 6 ребер болтаются и дают нам много-много (вопрос в том сколько?) различных конкретных графов, каждому из которых соответствует единственная (как Вы верно заметили) матрица смежности, для каждой из которых (как Вы верно указали) можно применить правило Кирхгофа. Теперь понятно, почему задачка комбинаторная? Как найти возможное количество смежных матриц? И доказать, что это количество верное?
Мы в курсе, в этом-то и задача! Прочитайте всю ветку внимательно, а то получается диалог слепого с глухим
Читать не возможно уже)))Я тут просто хохочу...Настроение подяли)))
Конкретный граф задаётся ОДНОЙ конкретной матрицей смежности.
Почему слепого с глухим? По-моему, имеет место разговор одного глухого с тремя людьми, которые пытаются что-то объяснить.
""построить ВСЕ остовные деревья" и дан граф с 10 вершинами и 15 ребрами. "
ДАН граф. Значит есть конкретный граф. Как вы хотите найти все остовные деревья для графа, который не задан? Вам нужно будет задать все графы и для каждого просчитать количество каркасов. Потом просуммировать. Никто об этом не будет говорить в задании. Автор топика явно обозначил что ДАН конкретный граф. Иначе как вы будете строить каркасы? Всю жизнь? =)
У нас нет конкретного графа. У нас есть 10 вершин, 15 ребер и пояснили, что граф связный, то есть как минимум 9 ребер связываю 10 вершин, а 6 ребер болтаются и дают нам много-много (вопрос в том сколько?) различных конкретных графов, каждому из которых соответствует единственная (как Вы верно заметили) матрица смежности, для каждой из которых (как Вы верно указали) можно применить правило Кирхгофа. Теперь понятно, почему задачка комбинаторная? Как найти возможное количество смежных матриц? И доказать, что это количество верное?
Создаем новую ветку, а то уже все...
Вот теперь понятно, что Вам все понятно. Сейчас уточним: дан ли конкретный граф или указано количество вершин и ребер?
Мы уже давно не эту задачу обсуждаем))))
С задачей из топика все и так понятно было изначально. Да и топик-то был создан не совсем для обсуждения комбинаторной задачи)))
1. Строим матрицу Кирхгофа
2. Находим количество остовных деревьев
3. Внимательно рисуем одно за одним остновное дерево
4. ??
5. PROFIT. Получаем автомат
Это кажется что задание сложное. Оно несложное, а трудоёмкое: на усидчивость и внимательность.
За алгоритм из статьи в Луркморье - жму плюс один :)
Это хорошо, но было бы ещё лучше, если бы вы поняли смысл задачки.
Откуда из моего алгоритма решения задачи следует, что я не понял смысла задачи?
Вы вообще когда-нибудь сталкивались с задачами по комбинаторике?
А к чему здесь теорема Кирхгофа, если предложена *комбинаторная* задача?
Сталкивался. А к чему здесь комбинаторика, когда давно известно, что количество остовных деревьев находится по теореме Кирхгофа.
Сейчас поясню коллеге, что Вы имеете в виду, говоря о смысле задаче)
Извините за опечатку - задачи)
Ну, хотите считайте комбинаторными методами. Лично я считаю, что изобретать велосипед не имеет смысла. Кирхгоф что зря писал свою теорему?
Это из серии South Park про гномов, которые воруют носки. К сожалению, не подскажу конкретный эпизод. Но думаю можно найти. =) Давно смотрел South Park запомнился момент. =)
Мда. Ну, успехов вам.
Хе-хе, ну попробуйте, пообщайтесь.
Успехов в чём? Я это задание не брал, а описал его решение. Вы теорему Кирхгофа знаете?
Я с Вами согласна)
Ну Вы и приколист))) Пытаюсь...
Успехов в жизни. Я знаю теорему Кирхгофа, и она никакого отношения не имеет к предложенной мной задаче.
Теорема Кирхгофа: "Все алгебраические дополнения матрицы Кирхгофа равны между собой и их общее значение равно количеству остовных деревьев графа."
Да... Не имеет. От слова совсем.
Посмотрите предыдущую ветку, там совсем читать не возможно. Нельзя поправить?
Как Вы составите матрицу Кирхгофа, не имея графа?
Да и даже если граф задан, то МАТРИЦА КИРХГОФА не имеет никакого отношения к КОМБИНАТОРИКЕ
Я же в самом первом комментарии, обращенном к вам, предлагал вам попытаться понять смысл задачи. Вам здесь уже три человека пытаются объяснить про исходно заданного Фому, а вы всё про своего Ерёму.
В условии чётко сказано, что ДАН граф. Не сказано, что нужно строить для ВСЕХ графов (10, 15) ВСЕ остовные деревья.
Если сказано, что граф ДАН
1) Практически всегда означает: есть конкретный граф
2) Редко означает: можно задать любой случайный граф самому.
Вы путаете две задачи, перечитайте тему.
Да уже разобрались, что к чему. :D Тут пошла пьянка про все графы, а я пропустил.
Ага, ну хорошо, что разобрались!
читать уже невозможно (продолжение)
Разработчикам написал. Благодарю за тему, в которой можно оттестировать механизм отображения длинных многоступенчатых веток :)
Можно и обратную сформулировать=
"Найти вероятность того, что в построенном наугад связном графе (из 10 вершин и 15 ребер) 126 ост. дер." =)
О, вот это шикарная задачка.
Ответ: вероятность 0.
Почему 0?
Потому что в любом графе из 10 вершин и 15 рёбер не может быть 126 остовных деревьев. Максимальное количество остовных деревьев будет точно меньше 126.
в моем графе 1220 деревьев))) 10 вершин и 15 рёбер
Кстати, в этой задачке хоть сразу видно, что она объёмная и трудоёмкая, а бывают такие коварные задачки, что условие выглядит невинно, а начнёшь делать - там ужас-ужас.
Согласна
Поэтому настоящие джигиты, когда создаю заказ с задачами, говорят, что уже решили, и готовы выслать результат немедленно после выбора их исполнителем. Видимо, тоже столкнулись пару раз с коротким заданием предполагающим решение на пол-тетради и пару дней работы. Теперь бегут впереди паровоза на всякий случай.
Хм. Это, я подозреваю, либо совсем новички, которые таким образом пытаются выслужиться, либо, наоборот, исполнители, у которых в базе решений такое уже есть - возможно, решённое год-два назад.
Юристы поймут (особенно с опытом работы в следствии) )). Задание: решить задачи по уголовному праву. Потом приходит доработка: оказывается надо было еще к каждой задаче по угол. праву составить постановление о предъявлении обвинения и обвин. заключение. Так, мелочь, ни о чем задание...))))
Вы же помните, что доработки, согласно пользовательскому соглашению, выполняются исполнителем бесплатно, только если просьба что-то доработать - в рамках задания. Надеюсь, о доработках вы речь завели, потирая руки от предвкушения возможности заработать ещё :
Ссылка на пользовательское соглашение, напомню, справа внизу сайта.
"построить ВСЕ остовные деревья" и дан граф с 10 вершинами и 15 ребрами.
Речь идёт о конкретно заданном графе? Да, ествественно.
Моя задача (в теме топика) не требует решения, она приведена для примера
Причина дискуссии
Сергей предложил решить задачу комбинаторно и я предполагаю, что имелось ввиду, что граф задан! Задача: оценить количество остовных деревьев в графе, но именно КОМБИНАТОРНО.
А потом уже возникла идея вывести общую формулу для оценки для связного графа с n вершинами и m ребрами)))
>> Сергей предложил решить задачу комбинаторно и я предполагаю, что имелось ввиду, что граф задан! Задача: оценить количество остовных деревьев в графе, но именно КОМБИНАТОРНО
Вообще-то нет. Я имел в виду: для графа известно, что у него столько-то вершин и столько-то ребер, но сам граф неизвестен.
Еще интереснее ... Совсем меня запутали...
Ну, найдёте вы границы от и до. И что? Их найти легко.
Заодно и потестили интерфейс форума - не справляется он с длинными обсуждениями...
да, по одной букве в столбик - это весело
И новые сообщения, чтобы найти нужно всю страницу проматывать...
Решение для конкретного графа задаём
I спосо
1. Строим матрицу Кирхгофа
2. Находим количество каркасов (n) по теореме Кирхгофа
3. Рисуем сами. Проще всего: строим граф, копируем n раз, например, в MS Visio. Удаляем рёбра и строим остовные деревья
II способ
1. Пишим или находим программу по нахождению остовных деревьев
2. Запускаем программу, вводим данные по графу (матрица смежности, скорее всего)
3. Перерисовываем полученные каркасы
То что тут пошла пьянка про какие-то неведомые комбинаторные формулы для нахождения ВСЕХ остовных деревьев для всех графов из 10 вершин и 15 ребёр... Мда...
Я считаю, что с заданным конкретным графом эта задачка и не интересна вовсе..
А как Вам такие
http://rndnet.ru/part-photop/idiotskie-zadaniya-v-uchebnikah
А без заданного конретного графа она не имеет решения.
Почему это? конечно имеет) Да Бог с ним, мы то с Вами поняли, что мы друг друга не поняли))
Мы вот про студентов пишем, что задания дурацкие дают...А в школах тихий ужас творится..
И в садиках тоже...У меня дочке 3 года, так они уже целый год математику изучают...
Количество каркасов будет различно в разных графах, а значит можно лишь дать оценку от и до. А какой в этом смысл? От минимального до максимального. Причём эти границы легко найти.
Ой, повторяете мои сообщения слово в слово...
goodhelher 1 мая 2015 в 15:14
Мне почему-то кажется, что это невыполнимо... И общую формулу не найти, даже если ее привязывать к степеням вершин. Оценить (очень грубо) может и получится, но какой смысл?
docent Moriartty 1 мая 2015 в 15:1
Может, и невыполнимо, а может, и выполнимо. Попробовать бы можно. А смысл хотя бы в том, чтобы потренироваться в решении комбинаторных задач.
Именно так. Ну, просто я практической значимости не вижу, например. Для конкретных графов задача разрешима без проблем. Поэтому нет смысла в этом (я пока не вижу). Но, может быть, оно для чего-то и пригодится в будущем. =) Можно дерзать и новую теорему доказать: граница от и до в количестве каркасов. Кстати, я почему-то думаю, что количество каркасов для всех графов (n, m) распределено по нормальному закону.
Можно, кстати, промоделировать и проверить эту мою гипотезу. Составить программу для составления всех графов (n, m) и рассчитывать поиском в глубину всех остовных деревьев. Думаю, что реально распределение будет нормальное. Не спрашивайте почему.... Это просто будет красиво, как и всё в математике. =) Кстати, хорошая тема для научной работы. Неплохой.
А я вот что-то не верю в симметричность распределения.
Только если считать решением ответ: от n до m каркасов. Но это не ответ, а оценка границ. Иначе бы все задания, в том числе, и школьные можно было бы решать как "ответ: во множестве действительных чисел результат расположен он минус бесконечности до плюс бесконечности." И ошибаться только в том, случае, когда решения во множестве действительных чисел нет. :D
Поясните, откуда возьмутся бесконечности?
Бесконечности относятся к любому возможному заданию, а не к графам, естественно. Внимательно прочитайте мою шутку. =)
Может лет через 8 мы еще услышим об этой задаче, если Сергей внесет ее в список "интересное, но лень". НОВОСТЬ ДНЯ: "Сергей X вывел формулу подсчета остовных деревьев в графе!" ;-)
Есть такая книга "После трех уже поздно" ..... там написано что маленькие дети могут выучится всему что угодно и основа закладывается до трех лет!
Интересно, что они будут в первом классе делать. Я помню мы весь год таблицу умножения учили
Да сейчас тихий ужас в учебниках... Я уже давно начала собирать коллекцию ляпов и глупостей))) К сожалению, ссылку дать не могу, т.к. это будет расценено, как передача контактной информации
Попробуйте воспользоваться любым файлообменником, чтобы привести ссылки на фотографии бумажных версий или страницы из электронного документа
Яндекс-диск показывает логин пользователя, Google Drive и Облако mail.ru - не проверял, кажется, не показывает.
Для картинок можно фотохостинги использовать
- picdump.r
- postimage.org
oblako.mail.ru точно не показывает логин.
О, неплохо, так это даже очень неплохо. Чем раньше человек начинает изучать математику, тем раньше он становится думающим человеком. =)
Я думал так как и вы, пока не увидел задания, которые вынуждены выполнять студенты факультета лингвистики. Мне показалось, что написать курсовой по механике - это тьфу по сравнению с тем, что у них. Не троллите не-инженеров :)
Не по теме конечно. Администрация, вам самим нравится как этот форум выглядит? Когда переписку ведут 2 человека, отвечая на комментарии друг друга, то в итоге ответы в столбик пишутся, как в Китае. Может стоит ограничить минимальную ширину комментария.
Мне кажется издевательством например задача найти определитель 5,6 и тд порядка, ну если это не в программировании конечно. Для понимания и запоминания темы, приобретения навыка, 4 полрядок более чем достаточно. Возникает ощущение, что препод уже имеет в виду выполнение заданий не студентом а нами)))
Последние статьи
  • Запускаем новый проект – Ворк24!

    Уважаемые пользователи!Долгое время Студворк являлся единственным крупным проектом нашей компании. Сегодня мы рады представить вам наш новый сервис – фриланс-биржу Ворк24.Почему мы решились на создание нового проекта?Удаленная работа окончательно закрепила за собой статус актуальной и доступной. Однако, в связи с санкционными ограничениями, многие зарубежные фриланс-биржи прекратили свою деятельность в РФ. Вывод средств с них существенно усложнился и многие специалисты потеряли источники стабильного заработка.Наш проект предлагает решение этих проблем. Ворк24 – это российский сервис, который объединяет заказчиков и исполнителей, создавая все условия для комфортной работы.Особенности и преимущества Ворк24Ворк24 – это фриланс-биржа широкого спектра для безопасного и удобного сотрудничества исполнителей и заказчиков из разных сфер деятельности. В роли заказчиков могут выступать как юридические, так и физические лица;В роли исполнителей только квалифицированные практики, имеющие подтвержденный опыт: маркетологи, дизайнеры, разработчики, юристы и другие специалисты, которые активно занимаются профессиональной деятельностью в своей сфере.Чем мы лучше российских аналогичных сервисов? Хороший вопрос, на который мы с уверенностью отвечаем:На нашем проекте пока еще низкая конкуренция среди исполнителей, что позволит опытным специалистам, не имеющим опыт фриланса, начать свой путь в этом направлении;Комиссия безопасной сделки в размере 5% для исполнителей – самая низкая по рынку (ниже не найдете, мы проверяли);Комиссия безопасной сделки для заказчиков – 0%.Будьте в числе первыхВорк24 будет полезен и вам, дорогие пользователи Студворк. Расскажем подробнее: На Ворк24 представлено много специальностей. Среди них есть те, что совпадают с вашими рабочими специальностями. В частности:Работа с текстом (копирайтинг и редактура);Инжиниринг (чертежи, схемы и сметы);Переводы (даже с самых сложных языков мира);Юридические услуги (правовое сопровождение, юридическая экспертиза и т.д.);Бухгалтерский и налоговый учет (для физлиц и юрлиц) и другие направления.Поэтому, добро пожаловать, дорогие авторы, ведь дополнительный источник дохода – это всегда прекрасно.Функционал Ворк24 практически идентичен тому, что уже реализован на Студворк. Ваша адаптация на новом сервисе будет максимально мягкой и безболезненной. Дизайн и внутренняя логика сайта во многом совпадают.Убедитесь в этом сами, начав работу на сервисе:В качестве заказчика;Или исполнителя. Но это ещё не всё. Мы дарим всем новым пользователям приветственный бонус в виде бесплатного PRO-аккаунта на месяц по промокоду “STUDWORK31”, чтобы ваше знакомство с платформой было еще более приятным.Желаем успехов в работе!P. S. Размещение и выполнение студенческих и школьных работ на Ворк24 запрещено.

  • Новые идеи — Сентябрь 2024

    Дорогие пользователи!Мы стремимся сделать Студворк сайтом, куда вам захочется возвращаться, где удобно работать и общаться с единомышленниками.Поделитесь своими идеями и предложениями по улучшению функционала в комментариях! Самые полезные идеи постараемся воплотить в жизнь в самое ближайшее время.

  • Технические работы — Сентябрь 2024

    Дорогие пользователи!Наш сайт постоянно совершенствуется благодаря вашим отзывам. Ваша обратная связь для нас невероятно важна – она помогает выявить ошибки и улучшить работу сервиса.Поделитесь своими замечаниями и предложениями в комментариях или воспользовавшись кнопкой «Что можно улучшить на сайте?». Благодаря вашим комментариям мы всегда будем в курсе всех недочетов и сможем сделать наш сервис еще лучше.Спасибо за активное участие в развитии сайта Студворк!

  • Поздравляем с 1 сентября!

    Поздравление с 1 сентября: советы для успешного начала учебного года + промокоды на скидки до 50%!

  • Нужно ли оформлять самозанятость фрилансеру?

    Обязательно ли оформлять самозанятость фрилансеру, работающему на удаленке: преимущества и риски НПД, возможности легализации доходов и налоговые особенности.

Показать еще
Поможем написать учебную работу
Первые отклики уже через 10 минут
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Прямой эфир журнала
Показать ещё
Темы журнала
Показать ещё
Прямой эфир