Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 172
Стоит, если они будут описаны доступным языком. Приветствуется применение метфор и т.п.
Картинки, схемки тоже приветствуются, ибо наглядности часто не хватает…
там анимация в большинстве случаев нужна
И в который раз на Хабре ссылочка на подборку визуализаторов:
rain.ifmo.ru/cat/view.php/vis
rain.ifmo.ru/cat/view.php/vis
Как то раз, преподаватель по алгоритмизации, двум девушкам объяснял какую-то сортировку на поезде с вагончиками. =)
И правильно.
А у моей знакомой, была такая задача на первом курсе по алгоритмам.
Задача это про бронирование билетов, есть поезд с определённым числом мест. Есть несколько станций. Каждый пассажир задаётся начальной и конечно станцией от/до которой он едет.
Задача рассчитать за O(n*log n) хватит ли места всем пассажирам в поезде и выдать каждому пассажиру номер его места в поезде.
Поломайте пока головы кому интересно, могу потом написать решение.
Задача это про бронирование билетов, есть поезд с определённым числом мест. Есть несколько станций. Каждый пассажир задаётся начальной и конечно станцией от/до которой он едет.
Задача рассчитать за O(n*log n) хватит ли места всем пассажирам в поезде и выдать каждому пассажиру номер его места в поезде.
Поломайте пока головы кому интересно, могу потом написать решение.
Это стандартная задача про выбор процессов. Сортировка по началу и жадный алгоритм
Автор, поддтвердите (опровергнете) решение. Правильный MaximKat предложил вариант?
У меня такой же вариант решения придумался. =) Вот и интересно.
Сортировка, да будет: O(n*log n)
И пробежек по массиву с раздачей билетов: O(n*log n)?
У меня такой же вариант решения придумался. =) Вот и интересно.
Сортировка, да будет: O(n*log n)
И пробежек по массиву с раздачей билетов: O(n*log n)?
Ну в общем да.
Я делал как-то так: Сначала быстрая сортировка по принципу в самое начало идут те кто вошёл раньше и едет дольше. Потом проходим массив и по очереди кладём в стек (кладя в стек человека вошедшего на станции n удаляем предварительно оттуда всех людей которые выходят на этой станции, они сверху). Смотрим за размером стека, если он превышает размер поезда, то выводим ошибку. Позиция пассажира в стеке и будет номером его места в поезде.
Я делал как-то так: Сначала быстрая сортировка по принципу в самое начало идут те кто вошёл раньше и едет дольше. Потом проходим массив и по очереди кладём в стек (кладя в стек человека вошедшего на станции n удаляем предварительно оттуда всех людей которые выходят на этой станции, они сверху). Смотрим за размером стека, если он превышает размер поезда, то выводим ошибку. Позиция пассажира в стеке и будет номером его места в поезде.
стоит сообществу сделать несколько версий на разных языках(и добавлять их в топик по мере появления), здесь же полно специалистов, кто то на С\C++, кто то на питоне, кто то на brainfuck'е (:…
Стоит однозначно
Да, стоит, с примерами на Python
лучше на C++
лучше на MMIX :)
лучше на русском )
Не обязательно, но желательно на императивно-алгоритмическом языке, хотя если и на декларативно-функциональном будет ещё лучше)
А вы больше языков не знаете что ли?
Не вижу связи между количеством известных языков и предпочтением. На питоне, по крайней мере для меня, нагляднее чем на других. Язык просто больно близок к «учебному», лаконичный и понятный.
но далеко не все его знают, в отличие от того же с++
Какая наивность.
Почему наивность? Мне вот почему-то кажется, что людям, которые С++ не понимают, и BFS не пригодится…
И, да, я не знаю Python.
И, да, я не знаю Python.
Я не знаю С++. Я знаю С, Python.
С чего вы взяли, что С++ — это какой-то эталон?
Python сильно на псевдокод похож, очень выразительный. Ну и сразу код погонять можно.
Но это, конечно, не принципиально.
С чего вы взяли, что С++ — это какой-то эталон?
Python сильно на псевдокод похож, очень выразительный. Ну и сразу код погонять можно.
Но это, конечно, не принципиально.
Во-первых, то, что Вы не знаете С++ и знаете Python, не причисляет Вас к «ненаивному большинству».
Во-вторых, не думаю, что для объяснения алгоритмов могут понадобиться какие-то специфические особенности C++, отсутствующие в том же С.
В-третьих, если Вы питонист, то не означает что другие смогут сразу погонять код. У меня отродясь Python не стоял.
В-четвертых, как какой-то язык может быть похож на псевдокод? o_O
Итого: идеальным вариантом, как по мне, можно считать псевдокод с С-подобным синтаксисом.
Во-вторых, не думаю, что для объяснения алгоритмов могут понадобиться какие-то специфические особенности C++, отсутствующие в том же С.
В-третьих, если Вы питонист, то не означает что другие смогут сразу погонять код. У меня отродясь Python не стоял.
В-четвертых, как какой-то язык может быть похож на псевдокод? o_O
Итого: идеальным вариантом, как по мне, можно считать псевдокод с С-подобным синтаксисом.
Во-первых, наивность заключалась в том, что ВСЕ знают С++
Во-вторых, алгоритмы — это математика, а она, в общем случае, не зависит от языка реализации (кроме специальных оптимизаций «под язык»). Тут важна выразительность.
В-третьих, это всего лишь вопрос личного удобства. Компилировать незнакомый код…
В-четвёртых, сами посмотрите.
С-like — достаточно компромиссный вариант, но, на мой взгляд, питон просто выразительней.
Во-вторых, алгоритмы — это математика, а она, в общем случае, не зависит от языка реализации (кроме специальных оптимизаций «под язык»). Тут важна выразительность.
В-третьих, это всего лишь вопрос личного удобства. Компилировать незнакомый код…
В-четвёртых, сами посмотрите.
С-like — достаточно компромиссный вариант, но, на мой взгляд, питон просто выразительней.
1. Да, С++ знают далеко не все, но алгоритмы, описанные с помощью С++ сможет прочитать большинство.
2. Согласен.
3. Согласен. Мне неудобно.
4. Я не пойму, с каких это пор псевдокод стал стандартизированным? Это ведь неформальный язык описания алгоритмов. И это псевдокод может быть похож на Pascal, на С или на Python, но не наоборот.
2. Согласен.
3. Согласен. Мне неудобно.
4. Я не пойму, с каких это пор псевдокод стал стандартизированным? Это ведь неформальный язык описания алгоритмов. И это псевдокод может быть похож на Pascal, на С или на Python, но не наоборот.
Работа с указателями, выделением/освобождением памяти не делает код читабельный, наверняка ;)
Под псевдокодом я имел в виду некоторый «классический» вариант не предусматривающий «закос» под что-то — что-то вроде www.nesterova.ru/bibl/algorithm_lang/Kniga2/Parts1%5CParts2%5Cindex.htm
Под псевдокодом я имел в виду некоторый «классический» вариант не предусматривающий «закос» под что-то — что-то вроде www.nesterova.ru/bibl/algorithm_lang/Kniga2/Parts1%5CParts2%5Cindex.htm
Конечно же для описания сортировок, BFS, DFS и пр. Вам непременно придется выделять/освобождать память, работая при этом только с указателями :)))
Мне почему-то казалось, что ситуация обратная.
Алгоритнмы и языки программирования не связаны между совсем чуть менее чем полностью.
Думаю, С-подобный синтаксис будет понятен большинству, так как во многих языках он взят за основу. А вот Python я вообще читать не могу.
А что мешает? На самом деле интересно.
Не понимаю я его :) В мой путь развития пролегал мимо Python. Могу читать Basic, Pascal, C, Asm на крайний случай и прочее…
Но я более чем уверен, что 90% программистов сталкиваются с С-шным синтаксисом рано или поздно, чего нельзя сказать про Python.
Но я более чем уверен, что 90% программистов сталкиваются с С-шным синтаксисом рано или поздно, чего нельзя сказать про Python.
Пардон за опечатку :)
Хм. У меня впечатление, как будто мы о разных питонах говорим. Может вы с хаскелем его путаете %)
Он очень похож на паскаль и бейсик но более лаконичный. Я вполне свободно читаю исходники на всех перечисленных языках. Думаю для вас никакой трудности быть не должно.
Он очень похож на паскаль и бейсик но более лаконичный. Я вполне свободно читаю исходники на всех перечисленных языках. Думаю для вас никакой трудности быть не должно.
Не знаю, может мне встречался не совсем тривиальный python-код :) Мне просто непривычна фишка с отступами: не хватает какого-то begin … end что ли.
P.S. Haskell — это конечно да-а-а…
P.S. Haskell — это конечно да-а-а…
Тем кто мне заминусовал карму, спасибо. Вам будет лучше икаться.
Стоит, особенно если с примерами задач, в которых они применяются. Желательно из жизни. :)
что ещё описывать в этом блоге как не алгоритмы?! :-)
ps: нужно конечно :-)
ps: нужно конечно :-)
стоит!!! в коментах я б писал свою реализацию алгоритмов на Delphi))
Обязательно их практическое приминение
Однозначно стоит. Примеры только на Питоне или еще каких-то Рубях не надо. Классика (Си, например) какая-то или блок-схем или чего-то подобного, универсального и общеизвестного будет достаточно, имхо (ну кроме асма, особенно для несуществующей архитектуры… такое уже есть где почитать;).
А потом уже пусть народ на что там ему удобно портирует.
А потом уже пусть народ на что там ему удобно портирует.
стОит, с примерами, не важно на каком языке
Вообще лучше псевдокод, у нас профессор так делает, потом на любом можно написать
А если нет, то питон — его проще всех читать и понимать
А если нет, то питон — его проще всех читать и понимать
примеры алгоритмов всегда надо писать на псевдоязыке, что бы не цеплялся реализации на конкретном языке, так правильнее, имхо.
Жизненно важно :)
Томас Кормен плачет горькими слезами. Никто не хочет читать его книги.
Мне лично было бы интересно не столько банальное описание самих алгоритмов из университетского курса, сколько их продвинутые усовершенствования и интересные или нестандартные применения.
Да стоит! =)
В прошлый раз постеснялся в пост вставить примеры практического приминения этих алгоритмов (и так большой получился).
Извините, что приоткрываю карты… но чтобы подбавитьинтриги интереса наблюдать за обновлениями в блоге, проболтаюсь.
Уже вышеперечисленные алгоритмы широко применяются в сетях: определение петель и динамическая маршрутизация.
Где какой алгоритм — просьба дождаться соотв. интересной статьи.
Поддерживаю автора в его начинаниях! =)
В прошлый раз постеснялся в пост вставить примеры практического приминения этих алгоритмов (и так большой получился).
Извините, что приоткрываю карты… но чтобы подбавить
Уже вышеперечисленные алгоритмы широко применяются в сетях: определение петель и динамическая маршрутизация.
Где какой алгоритм — просьба дождаться соотв. интересной статьи.
Поддерживаю автора в его начинаниях! =)
Стоит, т.к. многие сейчас считают себя «программистами», не зная даже основных алгоритмов, структур данных и их применений.
Все равно они так или иначе применяли какое-то подобие этих алгоритмов на деле, ибо они применяются во многих задачах. Сам помню, как приходилось изобретать велосипед, а позже узнавал, что все уже придумано и как-то называется.
Не хочу начинать холиваров, но я уверен, что половина «программистов» под тот же .NET Framework, к примеру, применяют алгоритмы только в виде методов типа Sort(), но уж никак не пишут сортировки вручную.
Конечно же я утрирую, но готов поспорить, что в какой-то из версий .NET Framework появится метод DoAllShit() :)
Конечно же я утрирую, но готов поспорить, что в какой-то из версий .NET Framework появится метод DoAllShit() :)
Стоит.
И классические, и применения.
И картинки. И примеры в коде.
И классические, и применения.
И картинки. И примеры в коде.
Однозначно За. Поймал себя на мысли, что вспоминая алгоритмы в голове крутится только «пузырьковая сортировка»
А я раньше(пока не выучил Qsort, Heapsort) любил сортировку подсчётом. Хотя все почему-то считали её сложной…
С реальными примерами применения.
ИМХО: Нет. Объясню почему — тот кому это интересно — либо знает их, либо возьмёт классические труды, типа «И.П.» Кнута. Потому, наверно более актуальны станут статьи-напоминания сути алгоритмов, для тех кто забыл, т.е. небольшие дайджесты, вроде 5-ка алгоритмов для красно-черных деревьев и т.д. Словесная суть, мат. формула и короткий пример на мнемокоде.
А вообще не стоит писать то, что разжевано и пережевано на сотнях сайтов, с анимациями и аплетами — лучше сделать акцент на реальном использовании, это полезнее и интереснее, а саму теорию и основы дать ссылками — не нужно будет делать много лишней работы. Тем более большинству сами алгоритмы знакомы.
Нужно-нужно.
Кнут это хорошо, очень.
Но он очень большой и читать его изборочно, когда знаешь что нужно (увидел, прочитал упоминание где-нибудь) значительно удобнее.
Кнут это хорошо, очень.
Но он очень большой и читать его изборочно, когда знаешь что нужно (увидел, прочитал упоминание где-нибудь) значительно удобнее.
Лучше проделать работу и найти алгоритмы полезные на практике, но не входящие в стандартные университетские курсы по той или иной причине. BFS, Dijkstra — это все слишком заезжено.
en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
Знаю этот алгоритм. Хорошая, кстати, задача для собеседования, если определить проблему как нахождение дубликата в массиве за линейное время.
А вот тут поподробнее, пожалуйста. Дубликат же не обязательно будет циклом.
Дан массив длины N + 1, элементами которого являются числа от 1 до N. Понятно, что по крайней мере одно число в таком массиве должно встречается более одного раза (возможно и не одно). Требуется найти любое такое число за O(N) время и O(1) память.
Все равно не понял :( Как ее решать?
Думаем о массиве как о графе. Представьте, что элемент массива a[] под номером i — это вершина графа. Его значение a[i] — это ориентированное ребро на вершину под соответствующим номером. Значения можно рассматривать как индексы в этот же массив, поскольку они ограничены диапозоном от 1 до N.
Далее, почему должен быть цикл? Если имеются повторяющиеся элементы, допустим a[i] и a[j], то это значит, что существуют вершины i и j, из которых лежит путь в одну и ту же вершину a[i]=a[j]. Таким образом, начиная свой обход этого графа мы рано или поздно придем в некоторую вершину повторно, но уже по другому ребру. Теперь достаточно выделить этот цикл и отрезать от него «хвост». Вот начало этого хвоста и будет повторяющимся элементом.
Конечно же, граф может быть и несвязным, т.е. состоять из набора таких цепочек, каждая из которых завершается циклом. Какой из них мы найдем — зависит от выбора начального элемента. Поэтому в условии я написал «любое такое число».
Далее, почему должен быть цикл? Если имеются повторяющиеся элементы, допустим a[i] и a[j], то это значит, что существуют вершины i и j, из которых лежит путь в одну и ту же вершину a[i]=a[j]. Таким образом, начиная свой обход этого графа мы рано или поздно придем в некоторую вершину повторно, но уже по другому ребру. Теперь достаточно выделить этот цикл и отрезать от него «хвост». Вот начало этого хвоста и будет повторяющимся элементом.
Конечно же, граф может быть и несвязным, т.е. состоять из набора таких цепочек, каждая из которых завершается циклом. Какой из них мы найдем — зависит от выбора начального элемента. Поэтому в условии я написал «любое такое число».
Но ведь цикл не обязательно означает наличие дубликата?
Как этот алгоритм будет работать, например, с таким массивом: {2,3,1,4,4}? В первом цикле из 3 элементов дубликата нет. Чтобы определить с какого элемента продолжать обход, нам придется помечать уже просмотренные элементы, т.е. константной памятью не обойтись
Как этот алгоритм будет работать, например, с таким массивом: {2,3,1,4,4}? В первом цикле из 3 элементов дубликата нет. Чтобы определить с какого элемента продолжать обход, нам придется помечать уже просмотренные элементы, т.е. константной памятью не обойтись
Ну ооочень нужно!
Лучше с начала и по-подробнее: картинки, схемы, примеры и т.д.
Будем безгранично благодарны!
Лучше с начала и по-подробнее: картинки, схемы, примеры и т.д.
Будем безгранично благодарны!
Стоит. + список литературы на тему
Но может не сразу же:
— Максимально-оптимальный поток в графах с выигрышами
— Венгерский алгоритм для Максимальной Задачи о назначениях
— Алгоритм нахождения максимального паросочетания в произвольном графе (Габова)
— и.т.п.
т.е. такой уровень сложности что ли? Просто, все ли поймут так сразу.
Думаю неплохо бы написать доступно и для младшекурсников, чтобы у них интерес появился к изучению алгоритмов. Показать что это несложно (если постепенно) и интересно.
А не пугать их сразу Кнутом (Моррисом Праттом) и Кристофидесом.
Выбрать уровень после DFS'а… где-нить от MST, сильно-связных компонент, клик, потоков… и до Венгерки. =)
— Максимально-оптимальный поток в графах с выигрышами
— Венгерский алгоритм для Максимальной Задачи о назначениях
— Алгоритм нахождения максимального паросочетания в произвольном графе (Габова)
— и.т.п.
т.е. такой уровень сложности что ли? Просто, все ли поймут так сразу.
Думаю неплохо бы написать доступно и для младшекурсников, чтобы у них интерес появился к изучению алгоритмов. Показать что это несложно (если постепенно) и интересно.
А не пугать их сразу Кнутом (Моррисом Праттом) и Кристофидесом.
Выбрать уровень после DFS'а… где-нить от MST, сильно-связных компонент, клик, потоков… и до Венгерки. =)
Естественно стоит. Хотелось бы так же историю, если можно.
Эх… для меня поздно уже…
Сегодня сдал экзамен на 5 (из 10) по алгоритмам. А вот если бы были они на хабре, я бы обязательно почитал, разобрался и сдал на 10. Так что обязательно нужны такие топики.
Сегодня сдал экзамен на 5 (из 10) по алгоритмам. А вот если бы были они на хабре, я бы обязательно почитал, разобрался и сдал на 10. Так что обязательно нужны такие топики.
Да, полезно, ты пиши, а не спрашивай.
Особенностью поста про наибольший поток наименьшей стоимости было то, что он цеплял сразу два алгоритма, которые на первый взгляд (если вы читаете о них впервые) могут показаться не очень понятными в учебниках, поэтому и требуют, возможно, такого красочного объяснения с примерами. Нет никакого смысла объяснять базовые классические алгоритмы — ведь это можно сделать, взяв отличнейшие книги Кормена, Кнута и иже с ними. А вот решения каких-то конкретных не очень типичных задач или более сложные алгоритмы — вот это оправдано.
На мой взгляд, затевать описание классических алгоритмов как монографичный материал не стоит (хотя ваше описание классической транспортной задачи великолепно) — таких описаний навалом и вы данными статьями скорее решаете личную задачу укрепления пройденного материала (самый лучший, кстати, способ), а вот составить список примеров _различных_ применений этих алгоритмов было бы гораздо полезнее для сообщества.
Вообще, можно создать отдельный блог типа «от теории к практике» и постить туда конкретные применения теоретических знаний, которыми нас столь усердно пичкают в высших учебных заведениях. Ведь та же транспортная задача, как правило, иллюстрируется (причем опять же — преподаватель фантазирует) «грузовиками», «почтальонами», тележками в цеху и т.д., но гораздо реже — реальными примерами.
Вообще, можно создать отдельный блог типа «от теории к практике» и постить туда конкретные применения теоретических знаний, которыми нас столь усердно пичкают в высших учебных заведениях. Ведь та же транспортная задача, как правило, иллюстрируется (причем опять же — преподаватель фантазирует) «грузовиками», «почтальонами», тележками в цеху и т.д., но гораздо реже — реальными примерами.
Эти «маленькие» алгоритмы тоже находят приминение:
OSPF — алгоритм Djkstra
RIP2 — алгоритм Bellman-Ford
MST — петли в сетях
Клики(мосты) — что-то типа надежность (отказоустойчивость) соединений в сетях
Может их тоже бегло осветить (в пару постов) для тех кто мало знаком?
К сожалению, не во всех университетах нормальный курс по алгоритмам — это норма…
OSPF — алгоритм Djkstra
RIP2 — алгоритм Bellman-Ford
MST — петли в сетях
Клики(мосты) — что-то типа надежность (отказоустойчивость) соединений в сетях
Может их тоже бегло осветить (в пару постов) для тех кто мало знаком?
К сожалению, не во всех университетах нормальный курс по алгоритмам — это норма…
Да, нужно, желательно со схемами на UML
По плюсам поймёшь…
си++ хороший язык, кроссплатформенный.
Но приятночитаемый — нет, извольте.
python.
Но приятночитаемый — нет, извольте.
python.
мне показалсь он имел ввиду по ± самого топика :)
Питон хорош, но некоторые вещи лучше объяснять на плюсовом/сишном коде, чтобы меньше синтаксического сахара было, для лучшего понимания. + к тому же в бОльшей части случаев реализовывать эти алгоритмы и приходится на c-подобных языках в рамках олимпиад.
Я не получал технического образования, и мне это очень нужно. Особенно если на примере С++ и с расшифровкой.
Лишним не будет
Я надеюсь вы все-таки напишите что-то по алгоритмам, а то уже не первый опрос, после которого автор нахватал плюсов и скрылся — видимо, исчезла мотивация :)
Мне кажется автора может смущать реакция профессионалов («все это и так знает, а кто не знает — пусть идёт читать книжки»), из-за этого и не пишут.
В своё время я пытался игнорировать это и писал короткие статьи про Java для новичков, но потом перестал — они оказались довольно низкоэффективными.
В своё время я пытался игнорировать это и писал короткие статьи про Java для новичков, но потом перестал — они оказались довольно низкоэффективными.
Напишу конечно!
Сейчас я просто читаю отзывы и пытаюсь понять что именно требуется от такого материала, на что делать упор. Статьи будут позже, сейчас пока только анализ комментариев.
Сейчас я просто читаю отзывы и пытаюсь понять что именно требуется от такого материала, на что делать упор. Статьи будут позже, сейчас пока только анализ комментариев.
Здесь лучше привести ссылки на качественную литературу по теме.
Автор все равно не сможет описать алгоритмы настолько доступно, чтобы каждый читатель понял. Это ж не таблица умножения, алгоритмами занимаются и занимались сверх умы человечества :-) к примеру, Д. Кнут и нет смысла переписывать их труды сюда, когда можно просто обратиться к книге.
Кроме того, чтобы изучать алгоритмы необходимо знать некий минимум, например основы линейной алгебры.
Я вношу свою лепту в этот пост ссылкой на прекрасную книгу Томаса Кормена — Алгоритмы. Построение и анализ. В этой книге материал изложен доступным языком, снабжен примерами на C и есть необходимое введение в линейную алгебру (при этом ненавязчивое :-) )
www.ozon.ru/context/detail/id/2429691/
Всем рекомендую!
Автор все равно не сможет описать алгоритмы настолько доступно, чтобы каждый читатель понял. Это ж не таблица умножения, алгоритмами занимаются и занимались сверх умы человечества :-) к примеру, Д. Кнут и нет смысла переписывать их труды сюда, когда можно просто обратиться к книге.
Кроме того, чтобы изучать алгоритмы необходимо знать некий минимум, например основы линейной алгебры.
Я вношу свою лепту в этот пост ссылкой на прекрасную книгу Томаса Кормена — Алгоритмы. Построение и анализ. В этой книге материал изложен доступным языком, снабжен примерами на C и есть необходимое введение в линейную алгебру (при этом ненавязчивое :-) )
www.ozon.ru/context/detail/id/2429691/
Всем рекомендую!
Перелистал книгу :-)
Ну да… это, конечно, не С, но доступный для понимания псевдоязык.
Пардон за неточность, если это столь важно.
Наверно чтобы изучать алгоритмы, нужно знать синтаксис каких-нибудь общепринятых для изучения языков программирования, а не в картинках изучать, как тут выше упоминалось :-)
Ну да… это, конечно, не С, но доступный для понимания псевдоязык.
Пардон за неточность, если это столь важно.
Наверно чтобы изучать алгоритмы, нужно знать синтаксис каких-нибудь общепринятых для изучения языков программирования, а не в картинках изучать, как тут выше упоминалось :-)
Классики: Кормен, Ахо, Хопкрофт и Ульман вам в помощь, алголист опять же упоминали — при должном желании изучить можно все
Хотелось бы почитать простое и понятное изложение Венгерского алгоритма и симплекс-метода, с реализациями (можно схематичными, но без лишних алгоритмических упрощений, типа матриц смежности вместо списков).
Вещи вроде обходов вширь-вглубь, на мой взгляд, давать не стоит, их знает любой, кто что-то делал с графами. А если знает, то и применение найдёт.
Вещи вроде обходов вширь-вглубь, на мой взгляд, давать не стоит, их знает любой, кто что-то делал с графами. А если знает, то и применение найдёт.
Писать стоит!
Ка уже писали, желательно с примера из реальной жизни, если вдруг что — то, что все знают, использует один из описываемых алгоритмов.
Лично для меня будут интересны примеры «из жизни» поисковых пауков, робототехники и т.д. Но, в любом случае, будут интересны любые примеры!
Ка уже писали, желательно с примера из реальной жизни, если вдруг что — то, что все знают, использует один из описываемых алгоритмов.
Лично для меня будут интересны примеры «из жизни» поисковых пауков, робототехники и т.д. Но, в любом случае, будут интересны любые примеры!
Вот тебе товарищ, про пауков и роботов :) Учитацо! и даже с картинками :)
logic.pdmi.ras.ru/~yura/internet.html
logic.pdmi.ras.ru/~yura/internet.html
А в чем проблема переписать на любой нужный язык?
Вот вам на си: www-2.cs.cmu.edu/~cburch/251/karat/karat.txt
Интересно
Сложно судить, насколько они известны широкой публике, думаю что далеко не все наслышаны, так что вполне можно.
Для меня, признаться, особой ценности не представляют, я их сам студентам только недавно закончил рассказывать, но а вдруг вы чего-нибудь этакого знаете, что мне неизвестно ;) Кстати, а про деревья Штейнера знаете что-нибудь? Научный интерес.
Для меня, признаться, особой ценности не представляют, я их сам студентам только недавно закончил рассказывать, но а вдруг вы чего-нибудь этакого знаете, что мне неизвестно ;) Кстати, а про деревья Штейнера знаете что-нибудь? Научный интерес.
дак понимаете, там ведь по сути ничего нет, кроме формулировки проблемы, и к тому же это геометрическая задача, которая на самом деле попроще. Для нее кое-какие алгоритмы есть довольно эффективные.
А более общая графовая по сути является логичным обощением как решаемой Дейкстрой задачи минимального пути, так и задачи MST. Ну и в отличие от обоих, ессно она NP-трудна. Так что там одни вопросы на данный момент. Появляющиеся эвристические алгоритмы пытаются бороться за доли процентов и откровенно говоря уже который год топчутся на месте.
(Простите, наболевшее. Мне через год диссер защищать, а у меня каменный цветок выходит пока проблематично)
А более общая графовая по сути является логичным обощением как решаемой Дейкстрой задачи минимального пути, так и задачи MST. Ну и в отличие от обоих, ессно она NP-трудна. Так что там одни вопросы на данный момент. Появляющиеся эвристические алгоритмы пытаются бороться за доли процентов и откровенно говоря уже который год топчутся на месте.
(Простите, наболевшее. Мне через год диссер защищать, а у меня каменный цветок выходит пока проблематично)
Это по которым оптимально прокладываются сети?
Как то встретился с такой задачкой: есть провод и 4 контакта (разположенных в концах квадрата). Какой кратчайший провод понадобится. Долго блися (крест-на-крест, гипотенузы и.т.п.) — пока не нуткнулся на эти деревья. А решается через описанные равносторонние треугольники. И получается:
Интересовался, но не глубоко. И несложные задачки решал. Типа вышеперечисленной.
Как то встретился с такой задачкой: есть провод и 4 контакта (разположенных в концах квадрата). Какой кратчайший провод понадобится. Долго блися (крест-на-крест, гипотенузы и.т.п.) — пока не нуткнулся на эти деревья. А решается через описанные равносторонние треугольники. И получается:
Интересовался, но не глубоко. И несложные задачки решал. Типа вышеперечисленной.
Пишите обязательно, многие будут благодарны.
Знаете в универе рассказывали тоже самое, про те же алгоритмы, но вы сами знаете, как оно бывает в универе. А из-за огромного доверия к хабру, читая статью — я понял, как много полезного пропустил
Прочиталось как «классический алкоголизм..» хД
Я не вижу смысла писать о том. о чем уже писали сотни раз в разных книгах (на русском языке!!) начиная с самых классиков в виде Кнут, Таха, потом Кормен, ну или вообще в самом простом виде это Окулов.
Зато с превиликим удовольствием почитал бы про современные алгоритмы, по которым информация только в различных рассылках и на английском.
Зато с превиликим удовольствием почитал бы про современные алгоритмы, по которым информация только в различных рассылках и на английском.
Мне тоже кажется, что в этом не очень много смысла — за последние десять лет издано довольно много приличной литературы по алгоритмам. У меня есть, по крайней мере, три-четыре хороших «кирпича», в которых нужный алгоритм, скорее всего, обнаружится.
Вот что-то неклассическое (о чём не пишут Кормен и др.) было бы интересно (при условии, что полезно). А если хочется писать — проще отсканировать страницу из хорошего учебника, чего велосипед изобретать.
Вот что-то неклассическое (о чём не пишут Кормен и др.) было бы интересно (при условии, что полезно). А если хочется писать — проще отсканировать страницу из хорошего учебника, чего велосипед изобретать.
Обязательно нужно а то с мойм универом я кроме как в ворде печать ничему не научусь.
а самому на не практические задачи времени не хватает.
а самому на не практические задачи времени не хватает.
А следующим будет Том 2. Получисленные алгоритмы?
Столько интересующихся, а по карме блога «Алгоритмы» и не скажешь, поддержали бы.
Оптимально будет большое количество схем, картинок для наглядности + листинги на python ибо на с++ уже достаточно взять хотя бы книгу сэджвика фундаментальные алгоритмы.
Я бы про суффиксные деревья послушал.
конечно стоит! и добавьте алгоритмы Кнута для больших чисел, конечно можно найти в инете описания и почитать, но я считаю, что не будет лишним снова про них написать/прочитать/посмотреть, особенно если будут хорошие иллюстрации
ага приветствуются. Ну я написал Дейкстры. В результате народ как-то негативно отнесся. А я бы был рад сортировкам на c#. Благо из много всяких разных :)
- Однозначно. Стоит. Любое описание, которое хотя бы на йоту будет делать алгоритм доступным для понимания — имеет полное право быть.
- Не имеет значения, были ли алгоритмы опубликованы ранее, в скольких учебниках напечатаны и т.д. Алгоритмы — частичка вечности. И писать о них можно вечно.
- Желательно давать разжёванное описание с примером. По шагам.
- Также, если есть возможность, желательно делать визуализацию в виде анимации, можно gif
Да, интересна. Она всегда будет интересна.
Желательно подкрепить будущие тексты визуальными моделями.
Желательно подкрепить будущие тексты визуальными моделями.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Классические алгоритмы — интересна ли тема?