А где Медный всадник и Александрийский столп? ИМХО сомнительная выборка.
М.б. объекты объеденены по принципу близости расположения?, т.е. исаакиевский собор=исаакиевский собор+ Медный всадник; эрмитаж = эрмитаж +Александрийский столп?
Дерево – это граф без циклов. — формально, надо вводить ориентацию, чтобы соответствовало рисунку.
Формально, не очень удачный рисунок из вики. А где ошибка? Если стрелочки просто линиями заменить, то это дерево останется деревом.
дайте определение AVL деревьев
Надейюсь, из Вики устроит:
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
И что неверного в моей фразе про высоту? Алгоритмы балансировки дерева в обзорной статье, как моя, считаю излишними. Иначе студент не увидит леса из-за сбалансированных деревьев ;)
может быть, миллионов?
Верно. Я использовал вольности языка, принятые на Хабре. А Вы поняли, но придрались.
Да вот незадача-то, большинство химических соединений имеют не только "древовидное", но и "циклическое" строение.
И где я утверждаю обратное? Где сказал, что в органике нет циклов?
Книга Малининых вряд ли про химию.
Да эта книга не про химию. И что из этого следует?
Я замечу, что никто сначала не делил проблему изоморфизма между классами графов.
Я писал не про историю вопроса: что сначала, что потом. Зачем? Может с начала времен начать? Написать, что когда наши предки — пещерные люди выходили на охоту с "кирпичом" на мамонта, они не знали про графы, м.б. только догадывались. Это важно добавить в статью? Те люди хорошо ориентировались на местности — жизнь заставляла, они всегда знали куда бежать, когда на мамонта, а когда от мамонта. Кто не знал — тот не выжил. Но я не об этом пишу. Многие преподы, желая понравиться студентам, начинают с мамонтов и переходят на работы, которые сейчас имеют исторический интерес.
"А проблема изоморфизма графов остается по-прежнему открытой". — нет, ряд работ наших российских ученых и несколько работ зарубежных ученых опровергают ваши слова.
Кто доказал, что изоморфизм 2 графов можно/нельзя найти за полиномиальное время?
Не только я не знаю, но и Вики ;) Читаем:
Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно, является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP).
Про отдельные классы графов много интересных работ. Нпр., про сильно регулярные графы.
вы даже намекнули, что уже составили отрисовки всех органических соединений из справочника Бельштейна,
В Бельштейне достаточно структурных формул. Зачем там еще что рисовать? Другое дело, что поиск там непростой — студентов специально учат.
Про 4 краски не сказал ни слова. Это отдельная тема, про которую еще не так давно спорили — сейчас немного утихли И, да, есть много теорем. Но основной вопрос про изоморфизм остается открытым.
Есть еще множество работ, которые могли бы найти отражение в вашей статье, но не нашли.
Да! Есть! Тогда бы моя статья превысила все мыслимые пределы.
Задача. За окном стоит береза
Не вижу смысла этой задачи. Прошу Вас растолкуйте.
Можно написать: береза: (листьев:100 000; диаметр ствола: 60). И что?
Ближе к тематике сайта статья "СТРАТЕГИИ ПРОВЕРКИ КОРРЕКТНОСТИ МЕТОДА ВЫЯСНЕНИЯ ИЗОМОРФИЗМА ГРАФОВ С ИСПОЛЬЗОВАНИЕМ ГРИД-СИСТЕМ НА ДОБРОВОЛЬНОЙ ОСНОВЕ" Э.И. Ватутин, В.С. Титов
Помню Ватутина по Вики, писали с ним про графы. Оставил отличные впечатления, как спец и как человек. В статье читаем:
Приведено описание стратегий проверки методов выявления изоморфизма графов путем организации попарного сравнения матриц смежности графов выбранной размерности и с использованием построения разбиения на классы изоморфизма, что существенно снижает требуемые вычислительные затраты. Показано, что точная проверка методов возможна только для графов небольшой размерности (N=10).
Далее:
Таким образом, данная стратегия позволяет расширить область проверки до N 9 10
с использованием параллельных вычислительных средств (кластеров, суперкомпьютеров или грид систем), но не более того.
Могу сразу предложить:
При этом на удаленные компьютеры необходима передача данных о множестве кодов матриц смежностидля поиска попарных совпадений инварианта.
Не нужно передавать матрицы — списки смежности гораздо экономнее. И небольшая придирка: авторы пишут "дифференциальную способность", но принято писать "дискриминирующую".
Про использованные индексы (инварианты), типа индекса Рандича, давно известно, что они не полные, но отлаживать методику распределенных вычислений можно и на них, в этом респект авторам!
Почему "Даже"? Считаете, что все отечественные авторы плохие спецы в теории графов? Я упомянул несколько всемирно известных имен: Адельсон-Вельский, Зыков, Малинины (отец и дочь), Пономаренко, Касьянов и Евстигнеев. Могу еще назвать, но думаю, что упомянутых достаточно. Себя называть не буду, хотя печатаюсь в J of Math Chem, и из J of Graph Theory мне рукописи на рецензию присылают ;) Кое-что написал в ru и en Википедии.
Если отечественные авторы плохие спецы, то как обяснить, что крупные издательства, нпр., Springer издают наши переводные научные журналы и деньги за статьи нашим авторам платят?
Спасибо за советы. Именно для таких советов я и писал эту статью.
Про инбридинг надо будет отметить.
Про 10! — это, конечно, не проблема, если надо сравнить 2 графа. А если надо найти граф с 10 вершинами и m ребрами в БД, где много графов с 10 вершинами и m ребрами, то тестировать каждую пару на изоморфизм м.б. затратно.
либо их не нарисовать "наглядно"
Есть наглядные рисунки графов с числом вершин больше 10. Нпр., схема Московского метро — по Вики на настоящий момент — 241 станция (вершина). Но там из самой конструкции следует оптимальное наглядное изображение.
Про трушные графы буду думать. С разумным примером плотного графа, наверное, ничего не выйдет. Даже маленькие деревни — не плотный граф.
Спасибо за интересный обзор. (Сожалею, что не могу за него голосовать).
Одного не понял: как юмор заголовка " развитие алгоритмов сжатия остановилось 20 лет назад" сочетается с итоговой фразой в конце?:
Надеюсь, мне удалось показать, как интересно развиваются алгоритмы сжатия без потерь в последние 20 лет.
Классическая книга это:
Кристофидес, Теория графов. Алгоритмический подход, М.: Мир, 1978 (м.б. есть болеее новые переиздания).
Еще:
В.Липский, Комбинаторика для программистов, М.: Мир, 1988.
И объемный том:
В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, Спб: БХВ-Петербург, 2003.
Почему одного? У Вас маленькая кухня, а речь о не маленьком сайте. Будь Ваша кухня вдвое больше — нашли бы куда машинку поставить, чтобы ничего не мешало.
Разговор про дизайн, а вопрос о размещении нового агрегата на маленькой кухне — это комбинаторный вопрос. В детстве жил в довольно большом частном доме. И кухня была больше нынешних средних. Когда купили холодильник не было вопроса куда поставить. Или. Моя бабушка пошла за продуктами, по дороге зашла в мебельный магазин, там ей понравился диванчик и она его купила. Нашлось место, куда поставить — ничего двигать не пришлось. С большим жилым местом другие проблемы: нужны руки, чтобы уборку делать. Если нанимать, то нужны будут деньги. Но это не имеет прямого отношения к дизайну сайтов. Это ИМХО уход от темы.
не все учителя преподающие в учебных заведениях, могут обладать столь широкими познаниями в графах, также теория графов, к сожалению только одна из тем в большом предмете под названием дискретная математика и не многие учителя могут раскрыть эту тему полностью, из-за нехватки времени.
Совершенно с Вами согласен. Преподаватели непрофильных для вуза предметов часто не имеют представления об интересах студентов, которых учат. Вспоминаю, что на 5 курсе ХФ МГУ к нам пришла молодая девушка, почти нашего возраста, учить нас английскому. Она рассказала нам, что только что закончила иняз, и диплом у нее был по Шекспиру. Язык она знала очень хорошо, но не химический. А химию она не знала — со школы успела забыть, что знала. А у нас были методички с текстами из научных хим. журналов. Думаю, что это было большое упущение нашего деканата: на факультете было много химиков, которые хорошо владели английским. Нужно было к таким учителям английского, как наша девушка, приставить консультантов, которые бы помогали в переводе хим.текстов и, что самое важное, объясняли на русском хим. смысл. Аналогично с учителями дискретной математики. Каждый человек приходя на новую работу должен изучить специфику. Лектор, который чисто формально читает студентам теорию графов и не думает об адресации, поступает плохо. Мог бы сам в деканат обратиться с просьбой дать консультанта.
не многие учителя могут раскрыть эту тему полностью, из-за нехватки времени.
У лектора должно быть время на подготовку, которое ему оплачивают, как и лекцию. Если лектор еще где-то работает по совместительству, то это его выбор — придеться перерабатывать.
Следуя этому ваше сообщения, где как кажется вы подчеркнуто выделили "Ваш подход" выглядит неуместно и честно не слишком приятно.
Честно: очень сожалею, о том, что показалось Вам не приятным. Правда, я не понял, какие именно слова Вам не приятны. Если про методологию, то с моей стороны это был скорее вопрос, а не утверждение. Я привел пример иных методологических подходов и ожидал от Вас услышать обоснование Вашего. Это наука, и ничего личного. Если кто-то напишет, что дважды два пять, и я спрошу: нет ли у Вас здесь ошибки? А он ответит, что я задал не приятный вопрос. Думаю, что всем участникам обсуждения станет не очень приятно.
вы подчеркнуто выделили "Ваш подход"
Я не могу назвать его своим подходом, т.к. его придумали до меня, и я указал на авторов. Но принимаю Ваш вывод:
И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны.
ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.
Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф. и число — последовательность байт — граф, и файл — граф, не говоря о БД.
В Вашем подходе неориентированный граф — частный случай орграфа: ребро выходит из в-ны 1 и заходит в 2, и другое ребро из 2 заходит в 1. На рисунке это будет со стрелочками: 1 ->2, 2 -> 1 или 1 <->2. Но это избыточно. Во многих признанных учебниках орграфы идут отдельной главой — студенту бы просто графы понять, ему не до петель! Видимо, многие авторы таких учебников (Харари, Зыков и др.) сочли бы Ваш подход методологически ошибочным.
в неориентированном графе петля учитывается дважды
Пусть в графе 4 вершины и только одна петля у вершины 1, других ребер нет, тогда м-ца смежности будет иметь 1 в первом элементе (1,1), все остальные будут нули.
Не понял список смежности для первого графа в секции. На рисунке ребро 1-4 кратное, и нет ребра 2-3. Если сделать ребро 1-4 не кратным, то список можно записать проще и экономнее: 1-2, 1-3, 1-4, 2-4, 3-4, всего 5 ребер. А по Вашему списку их больше. Список смежности часто употребляют для ручного ввода, это бывает быстрее, чем матрицу набивать.
В общем согласен. Но всё хорошо в меру. Если обсуждение пустякового вопроса (работы на пару дней) затянется на день или несколько - согласитесь, это не нормально. Хороший руководитель даст всем выступить, а потом, когда выступления пойдут с повторами по второму кругу, предложит сделать перерыв (нпр., на обед). - Мы все здесь немного устали, кто не успел что-то сказать: вот пустая папка и стопка чистой бумаги.Запишите тезисно ваши предложения. Мы - мой заместитель и гл. инженер все учтем и примем решение.
Очень нужно, чтобы обсуждение записывалось: аудио или видео. Запись собирает людей, под запись опасаются сказать лишнее, чтобы потом не смеялись.
А где Медный всадник и Александрийский столп? ИМХО сомнительная выборка.
М.б. объекты объеденены по принципу близости расположения?, т.е. исаакиевский собор=исаакиевский собор+ Медный всадник; эрмитаж = эрмитаж +Александрийский столп?
Спасибо за ответ.
Формально, не очень удачный рисунок из вики. А где ошибка? Если стрелочки просто линиями заменить, то это дерево останется деревом.
Надейюсь, из Вики устроит:
И что неверного в моей фразе про высоту? Алгоритмы балансировки дерева в обзорной статье, как моя, считаю излишними. Иначе студент не увидит леса из-за сбалансированных деревьев ;)
Верно. Я использовал вольности языка, принятые на Хабре. А Вы поняли, но придрались.
И где я утверждаю обратное? Где сказал, что в органике нет циклов?
Да эта книга не про химию. И что из этого следует?
Я писал не про историю вопроса: что сначала, что потом. Зачем? Может с начала времен начать? Написать, что когда наши предки — пещерные люди выходили на охоту с "кирпичом" на мамонта, они не знали про графы, м.б. только догадывались. Это важно добавить в статью? Те люди хорошо ориентировались на местности — жизнь заставляла, они всегда знали куда бежать, когда на мамонта, а когда от мамонта. Кто не знал — тот не выжил. Но я не об этом пишу. Многие преподы, желая понравиться студентам, начинают с мамонтов и переходят на работы, которые сейчас имеют исторический интерес.
Кто доказал, что изоморфизм 2 графов можно/нельзя найти за полиномиальное время?
Не только я не знаю, но и Вики ;) Читаем:
Про отдельные классы графов много интересных работ. Нпр., про сильно регулярные графы.
В Бельштейне достаточно структурных формул. Зачем там еще что рисовать? Другое дело, что поиск там непростой — студентов специально учат.
Про 4 краски не сказал ни слова. Это отдельная тема, про которую еще не так давно спорили — сейчас немного утихли И, да, есть много теорем. Но основной вопрос про изоморфизм остается открытым.
Да! Есть! Тогда бы моя статья превысила все мыслимые пределы.
Не вижу смысла этой задачи. Прошу Вас растолкуйте.
Можно написать: береза: (листьев:100 000; диаметр ствола: 60). И что?
Помню Ватутина по Вики, писали с ним про графы. Оставил отличные впечатления, как спец и как человек. В статье читаем:
Далее:
Могу сразу предложить:
Не нужно передавать матрицы — списки смежности гораздо экономнее. И небольшая придирка: авторы пишут "дифференциальную способность", но принято писать "дискриминирующую".
Про использованные индексы (инварианты), типа индекса Рандича, давно известно, что они не полные, но отлаживать методику распределенных вычислений можно и на них, в этом респект авторам!
Почему "Даже"? Считаете, что все отечественные авторы плохие спецы в теории графов? Я упомянул несколько всемирно известных имен: Адельсон-Вельский, Зыков, Малинины (отец и дочь), Пономаренко, Касьянов и Евстигнеев. Могу еще назвать, но думаю, что упомянутых достаточно. Себя называть не буду, хотя печатаюсь в J of Math Chem, и из J of Graph Theory мне рукописи на рецензию присылают ;) Кое-что написал в ru и en Википедии.
Если отечественные авторы плохие спецы, то как обяснить, что крупные издательства, нпр., Springer издают наши переводные научные журналы и деньги за статьи нашим авторам платят?
Спасибо. Посмотрю.
Добрый день, читатель!
Не нашел у Вас статьи про графы. Пожалуйста, укажите конкретно.
А можно конкретнее? В чем я не прав?
Спасибо за советы. Именно для таких советов я и писал эту статью.
Про инбридинг надо будет отметить.
Про 10! — это, конечно, не проблема, если надо сравнить 2 графа. А если надо найти граф с 10 вершинами и m ребрами в БД, где много графов с 10 вершинами и m ребрами, то тестировать каждую пару на изоморфизм м.б. затратно.
Есть наглядные рисунки графов с числом вершин больше 10. Нпр., схема Московского метро — по Вики на настоящий момент — 241 станция (вершина). Но там из самой конструкции следует оптимальное наглядное изображение.
Про трушные графы буду думать. С разумным примером плотного графа, наверное, ничего не выйдет. Даже маленькие деревни — не плотный граф.
Спасибо за интересный обзор. (Сожалею, что не могу за него голосовать).
Одного не понял: как юмор заголовка " развитие алгоритмов сжатия остановилось 20 лет назад" сочетается с итоговой фразой в конце?:
Развиваются или развитие остановилось??
Классическая книга это:
Кристофидес, Теория графов. Алгоритмический подход, М.: Мир, 1978 (м.б. есть болеее новые переиздания).
Еще:
В.Липский, Комбинаторика для программистов, М.: Мир, 1988.
И объемный том:
В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, Спб: БХВ-Петербург, 2003.
Вы про привычки дизайнеров или про привычки юзеров? У Вас на кухне такого вопроса не возникнет.
Почему одного? У Вас маленькая кухня, а речь о не маленьком сайте. Будь Ваша кухня вдвое больше — нашли бы куда машинку поставить, чтобы ничего не мешало.
Разговор про дизайн, а вопрос о размещении нового агрегата на маленькой кухне — это комбинаторный вопрос. В детстве жил в довольно большом частном доме. И кухня была больше нынешних средних. Когда купили холодильник не было вопроса куда поставить. Или. Моя бабушка пошла за продуктами, по дороге зашла в мебельный магазин, там ей понравился диванчик и она его купила. Нашлось место, куда поставить — ничего двигать не пришлось. С большим жилым местом другие проблемы: нужны руки, чтобы уборку делать. Если нанимать, то нужны будут деньги. Но это не имеет прямого отношения к дизайну сайтов. Это ИМХО уход от темы.
Совершенно с Вами согласен. Преподаватели непрофильных для вуза предметов часто не имеют представления об интересах студентов, которых учат. Вспоминаю, что на 5 курсе ХФ МГУ к нам пришла молодая девушка, почти нашего возраста, учить нас английскому. Она рассказала нам, что только что закончила иняз, и диплом у нее был по Шекспиру. Язык она знала очень хорошо, но не химический. А химию она не знала — со школы успела забыть, что знала. А у нас были методички с текстами из научных хим. журналов. Думаю, что это было большое упущение нашего деканата: на факультете было много химиков, которые хорошо владели английским. Нужно было к таким учителям английского, как наша девушка, приставить консультантов, которые бы помогали в переводе хим.текстов и, что самое важное, объясняли на русском хим. смысл. Аналогично с учителями дискретной математики. Каждый человек приходя на новую работу должен изучить специфику. Лектор, который чисто формально читает студентам теорию графов и не думает об адресации, поступает плохо. Мог бы сам в деканат обратиться с просьбой дать консультанта.
У лектора должно быть время на подготовку, которое ему оплачивают, как и лекцию. Если лектор еще где-то работает по совместительству, то это его выбор — придеться перерабатывать.
Честно: очень сожалею, о том, что показалось Вам не приятным. Правда, я не понял, какие именно слова Вам не приятны. Если про методологию, то с моей стороны это был скорее вопрос, а не утверждение. Я привел пример иных методологических подходов и ожидал от Вас услышать обоснование Вашего. Это наука, и ничего личного. Если кто-то напишет, что дважды два пять, и я спрошу: нет ли у Вас здесь ошибки? А он ответит, что я задал не приятный вопрос. Думаю, что всем участникам обсуждения станет не очень приятно.
Я не могу назвать его своим подходом, т.к. его придумали до меня, и я указал на авторов. Но принимаю Ваш вывод:
Спасибо!
ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.
Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф. и число — последовательность байт — граф, и файл — граф, не говоря о БД.
В Вашем подходе неориентированный граф — частный случай орграфа: ребро выходит из в-ны 1 и заходит в 2, и другое ребро из 2 заходит в 1. На рисунке это будет со стрелочками: 1 ->2, 2 -> 1 или 1 <->2. Но это избыточно. Во многих признанных учебниках орграфы идут отдельной главой — студенту бы просто графы понять, ему не до петель! Видимо, многие авторы таких учебников (Харари, Зыков и др.) сочли бы Ваш подход методологически ошибочным.
Не понял:
Пусть в графе 4 вершины и только одна петля у вершины 1, других ребер нет, тогда м-ца смежности будет иметь 1 в первом элементе (1,1), все остальные будут нули.
Не понял список смежности для первого графа в секции. На рисунке ребро 1-4 кратное, и нет ребра 2-3. Если сделать ребро 1-4 не кратным, то список можно записать проще и экономнее: 1-2, 1-3, 1-4, 2-4, 3-4, всего 5 ребер. А по Вашему списку их больше. Список смежности часто употребляют для ручного ввода, это бывает быстрее, чем матрицу набивать.
Согласен. Сожалею, что не могу голосовать.
Очень много конформистов, похожих на нормальных.
В общем согласен. Но всё хорошо в меру. Если обсуждение пустякового вопроса (работы на пару дней) затянется на день или несколько - согласитесь, это не нормально. Хороший руководитель даст всем выступить, а потом, когда выступления пойдут с повторами по второму кругу, предложит сделать перерыв (нпр., на обед). - Мы все здесь немного устали, кто не успел что-то сказать: вот пустая папка и стопка чистой бумаги.Запишите тезисно ваши предложения. Мы - мой заместитель и гл. инженер все учтем и примем решение.
Очень нужно, чтобы обсуждение записывалось: аудио или видео. Запись собирает людей, под запись опасаются сказать лишнее, чтобы потом не смеялись.
Верно. На производстве м.б. нужен измеритель, у которого высокоомный вход. А обычному электрику не нужен.
Ну на нем же написано "школьный". В школе м.б. нужен был высокоомный вход.