студентикА нужно ли в повседневной работе программиста знание алгоритмов? Под алгоритмами ,я подразумеваю, сложные математически обоснованные наборы инструкций, всегда приводящие к результату. Ведь, наверняка, можно писать даже коммерческие программы, без особого представления о "сложности алгоритма", "структурах данных" и пр. К примеру, с этим я сталкивался в программировании баз данных(правда небольшие проекты). Хочется услышать мнения людей, основанные на их личном опыте.
Все зависит от вашей будущей специализации в программировании. Если будете заниматься математическим и компьютерным моделированием реальных процессов, то без математики шагу не ступишь, а если обычным прикладным программированием, типа разработка различных клиентов (почтовых, баз данных и т.д.) под управлением существующих библиотек БД, то достаточно математики на уровне 4-го класса. Вон меня всегда удивляло, что например бухгалтера не знают простейших правил округления, для них тайна за семью печатями, почему сумма округлений, не равна округлению суммы. Кроме 4-х действий арифметики, других они не знают. Скажем, применение налогового метода амортизации в бухгалтерском учете. Коэффициент налоговой амортизации определяется как квартальный (для налогового учета) и чтобы из него получить месячный коэффициент (для бухгалтерского учета) бухгалтера тупо делят его на 3. Только одна-единственная тетя на всех бухгалтерских Интернет форумах засомневалось в этом, так ее быстро зашугали, ты чё типа, совсем «очевидных» вещей не понимаешь? А для меня «очевидно», что месячный коэффициент следует из квартального по формуле Кмес = 1 - (1 - Ккв)^(1/3) , а не по формуле теть-бухгалтеров Кмес = Ккв/3 . Именно эта формула позволила мне запрограммировать квартальный (налоговый) учет ОС, как ежемесячный (бухгалтерский), с тем же эффектом. А сделано это с целью единообразия форм документов и используемых алгоритмов (правда, ценной, некоторого увеличения объема базы данных).

Что до алгоритмов, то например я уже несколько дней вожусь с одним нелинейным алгоритмом сортировки на базе natural merge sort . Так вот «линейные» реализации этого алгоритма получены достаточно легко и просто и работают без проблем. А «нелинейная» реализация, при кажущейся простоте, реализована пока только на 99%. А последний процент меня уже измотал :) .

Если вы работали с IdaPro , то там есть программа wingraph32.exe , которая строит блок схемы дизассемблерного кода. Очень классная вещь! В Интернете есть ее исходные тексты на чистом Си. Только без знания алгоритмов построения блок схем они дают мало пользы. А вообще-то эту программу хотелось бы улучшить, жаль только, что у меня другая специализация :) .

EmeryЧто до алгоритмов, то например я уже несколько дней вожусь с одним нелинейным алгоритмом сортировки на базе natural merge sort . Так вот «линейные» реализации этого алгоритма получены достаточно легко и просто и работают без проблем. А «нелинейная» реализация, при кажущейся простоте, реализована пока только на 99%. А последний процент меня уже измотал :) .
Ну вот, стоило объявить во всеуслышание о проблеме «последнего процента» и он успешно достигнут! Почти мистика :) . Так что свой нелинейный алгоритм natural merge sort я реализовал полностью, на 100%. Можно идти дальше :) .

студентикСогласен с вами, только не особо часто встретишь на рынке труда предложения о такой работе, где требуется хорошая мат. подготовка. А в чем различие "нелинейной" реализации от "линейной" в приведенной выше сортировке?
Ну, почему? В военной области, в разработке современных систем вооружений, хорошая «мат. подготовка» очень даже нужна и востребована. А в гражданском секторе, да, математика используется значительно меньше, особенно после распада СССР. Это касается вообще любой наукоемкой деятельности. Я думаю, что чем больше государство использует наукоемкую продукцию в гражданском секторе, тем более оно развито. Вот, например, у нас в Украине, мы даже свой первый спутник связи запустить не можем. Занимаем на это дело денег у Канады. И это объясняет многое.

Тем не менее, даже если взять двух программистов занимающихся, допустим, только учетом на предприятии, одного с мат подготовкой, другого без, то разница их подходов хорошо различима. Хотя результат может быть один и тот же. «Математик» более склонен к реализации абстрактных моделей и критическому отношению к существующим, а «Технарь» часто-густо предпочитает стандартизированные локальные решения, вплоть до «ломовых», наращивая мощность больше за счет «крутизны» компьютеров, чем за счет оптимизации алгоритмов. Поверьте, что даже в стандартном учете (если вы его сами программируете) есть масса задач, достойных математиков. Это касается и моделей учета и оптимизации алгоритмов и способности из слабых систем получать максимум возможного. Вот простой пример, для конкретики. Все хорошо знают, что такое «1С». Так вот фирма «1С» сделала такое «изобретение» как субконто . Для «Технаря» тут нет никаких вопросов, ну придумали это понятие, ну и ладно, используют, ну и хорошо. «Математик», хорошо владеющий также предметной областью учета, обязательно озадачится, а зачем, почему, какой смысл в этом? И найдет ответ, который перевернет всю прикладную модель учета братьев Нуралиевых с головы на ноги и более того, заставит переосмыслить весь бухгалтерский учет как таковой. И придет к выводу, что бухгалтерский «учет», это не учет вовсе, а «контроль» , а для того, чтобы вести нормальный учет на предприятии нужно реализовать совершенно другую концепцию, которую логично назвать «натуральный учет» , из которого бухгалтерский «учет» должен быть получен уже как следствие. Могу добавить также, что смысла бухгалтерского «учета» очень часто не знают даже профессиональные бухгалтера со стажем, именно его сути, а не формы, которую они обычно знают в совершенстве. Эту тему можно развивать, но думаю для примера достаточно, чтобы показать различие подходов программистов с абстрактным мышлением (которое дает математика) и без. Подобное различие характерно для любой области программирования, вот и делайте вывод сами, нужна математика прикладному программисту или нет?

Насчет «линейной» и «нелинейной» реализации алгоритма сортировки естественным слиянием (natural merge sort) .

Он состоит из основных двух операций.

1. Разделение (расщепление) Split данной сортируемой последовательности S на множество локально упорядоченных (по возрастанию или убыванию) подпоследовательностей {s1, s2, s3, . . . , sK} , где все подпоследовательности, кроме, быть может, последней содержат более одной записи (ключа).

2. Объединение (слияние) Merge смежных пар подпоследовательностей одного уровня в одну (слева направо), с учетом порядка упорядочения этих подпоследовательностей. Т.е., убывающая последовательность сливается с «конца», а возрастающая с «начала».

Эти две операции повторяются до тех пор, пока вся последовательность S не будет состоять из одной только подпоследовательности, т.е., пока она не станет упорядоченной.

Различие между «линейной» и «нелинейной» реализацией, по сути, только в том, чтобы операцию Split применять только одни раз или в один проход по искомой последовательности S (для «нелинейного» случая). Поскольку, этот алгоритм планируется использовать для внешней сортировки файлов (по ключу) больших размеров (не помещающихся в обычную память), то разрешается использовать до двух файловых буферов размером как неизменяемый файл-источник.

Чтобы лучше продемонстрировать "нелинейность" алгоритма, прикладывают демонстрационный рисунок.

студентикВ принципе, у меня была идея подобной сортировки может быть только несколько отличная.
1. Разбить все элементы на группы(возможно рекурсивно) числом элементов мин - 1 макс - 2.
2. Упорядочить элементы в каждой группе для этого достаточно 1 сравнения для 1 групы
3.Упорядоченные группы сливать например слева направо.

Если не ошибаюсь порядок действий такой сортировки равен исходному числу элементов.
Минус в раходах на доп. память.
Если не ошибаюсь, то ваш алгоритм похож на алгоритм Джона фон Нейманом , изобретенного в 1945 году. Вот его корректная формулировка:

1. Сортируемое поле разбивается на две половины примерно одинакового размера;
2. Каждая из получившихся половин сортируется отдельно, например – этим же алгоритмом;
3. Два упорядоченных буфера половинного размера объединяются (сливаются) в один.

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока количество элементов индексируемого поля не достигнет единицы (любое множество длины 1 можно считать упорядоченным по определению).

«Естественное слияние» отличается от «обычного» учетом уже существующего порядка в сортируемых записях . А поскольку порядок может быть как возрастающий (неубывающий) так и убывающий, то приходится принимать во внимание оба этих случая. Именно этот вариант я и реализовал, для случая одного прохода , определяющего упорядоченные подпоследовательности (УПП) и без рекурсии .

макс132если вы действительно такой хороший, вы должны были дать ссылку на гуглю с описанием, а не объяснять)
Так с ссылками не проблема, например:
http://books.google.ru/books?id=k0vUmjua41wC&pg=PA341&lpg=PA341&dq=%22natural+merge+sort%22
http://books.google.ru/books?id=zInY9G915-YC&pg=PA257&lpg=PA257&dq=%22natural+merge+sort%22
http://books.google.ru/books?id=HZ9Z-PS1g0UC&pg=PA51&lpg=PA51&dq=%22natural+merge+sort%22
http://www.daniweb.com/forums/thread190739.html
Только, они не дают реальный оптимизированный алгоритм, только общие идеи или неудачную реализацию в последнем случае. У меня самого есть три или четыре собственных реализаций этого алгоритма, остановился на том, который продемонстрирован рисунком. И он существенно завязан на двоичном представлении числа упорядоченных подпоследовательностей (УПП) данной последовательности. Так что я никого не копирую, за исключением общих идей.

MasterZivRT183.1 пишет:
> Я при всем моем уважении к Кнуту в руках не держал его книжки.
> Во-первых, они очень дорогие,
> во-вторых, там довольно сложная математика

Не, там далеко не везде сложная математика. Но написано исключительно
занудно и, как бы сказать, замедленно. Кнут вообще людит процесс
написания, видимо, читеть его поэтому сложно.
Зря, вы на Кнута наезжаете. Не нужно забывать, что его третий том «Сортировка и поиск» вышел на русском языке аж в 1978 году, а в оригинале в 1973 году. А основные результаты, очевидно, получены в 60-х годах. Так что для своего времени, когда шла борьба за каждый байт памяти его труды были вполне актуальны. Сейчас, да, есть более современные книги, например.

Роберт Седжвик – Фундаментальные алгоритмы на C++ – Части 1-4 – Анализ & Структуры данных & Сортировка & Поиск
и
Роберт Седжвик – Фундаментальные алгоритмы на C++ – Часть 5 – Алгоритмы на графах

Их можно скачать, например в
http://mskd.ru/?id.17174.books.Fyndamental'nie_algoritmi_na_S++_-_R.Sedzhvik

А математика у Кнута никак не связанна с пониманием алгоритмов. Ее роль только определить эффективность работы рассматриваемых алгоритмов. Только для современных условий программирования и компьютеров эту математику нужно вычислять заново или обладать хорошей интуицией или чутьем на применяемые алгоритмы. Единственное с чем я могу вполне согласиться, что Кнут немного морально устарел, но именно на его трудах написаны многие современные книги в этой области.

студентикСтранно а я полагал, что все фундаментальные алгоритмы сложились как раз уже во время написания книг Кнутом. Современные алгоритмы, по-моему, не претерпели каких-либо серьезных изменений, кроме как аппаратных уклонов на распараллеливание вычислений, многопроцессорность и т. д.
Ну, того же «natural merge sort» я у Кнута не нашел, хотя про сортировку слиянием он пишет. Потом B+ деревья , которые весьма интенсивно используются при индексации баз данных и построении на их основе SQL запросов изобретены Рудольфом Байером (Rudolf Bayer) только в 1972 году. И вообще, фундаментальные алгоритмы, имеющие отношение к SQL, у Кнута практически отсутствуют полностью. Так что не надо думать, что фундаментальные алгоритмы перестали появляться после Кнута :) .

механизаторEmery
Ну, почему? В военной области, в разработке современных систем вооружений, хорошая «мат. подготовка» очень даже нужна и востребована Ну, и сколько получает средний разработчик форм на vcl/wpf/winforms и сколько получает специалист с хорошей "матподготовкой" в оборонке? Второй в 2-3 раза меньше первого
Трудно судить о зарплате закрытых контор. На западе «военные» программисты получают чуть ли не на порядок больше «обычных». И потом сейчас не лучшая эпоха в наших странах для подобных сравнений. В Украине даже военный парад бронетехники отменили на день независимости из-за банальной нехватки денег. Да и к тому же «рабочие лошадки» у нас всегда получают значительно меньше тех, кто ими «руководит». Короче если политика оплаты труда никак не связана с качеством этого труда, то о чем тут говорить вообще. Раньше был принцип оплаты: «От каждого по способностям, каждому по труду» , а сейчас работает принцип: «От каждого по способностям, каждому сколько положено» :) .

MasterZivДа он не морально устарел, он по жизни такой. Математик, зануда может
быть, максималист. Кто ещё мог отказаться от публикации своей книги только
потому, что не было шрифтов для её издания, уйти на 2 или 3 года, и вернуться
с новым средством производства этих самых шрифтов ?

Это не хорошо и не плохо, это -- свойство характера. Человек пишет
статью о форматировании параграфа и в лирическом отступлении исследует
вопрос о том, как полиграфисты решали, где закончить очередную строку
абзаца, чуть ли не вплоть до рукописных тексов библии или даже
египедских иероглифов. Ну что поделать, такой он.
Как по мне, то эта информация не имеет никакого отношения к профессионализму Кнута. Все равно, что судить про общую теорию относительности Эйнштейна по тому, как он показал язык всему человечеству или как сплагиатил у Лоренца и др. Я могу повторить еще раз, что его книга была весьма актуальна в свое время, и сейчас она имеет больше академический или исторический интерес.

студентикПросмотрел книгу "Фундаментальные алгоритмы на С++" Сэджвика. Неспорю книга хороша, наверно даже более доступна для начинающих, чем Кнут. Но даже беглого взгляда хватило, чтобы увидеть их разницу. Кнут более фундаментален, исчерпывающ, математически строг, именно поэтому наверно его 3х томник считают чуть ли не библией алгоритмов всех времен. Да у Сэджвика более новый материал, более последние факты, но это явно книги разных уровней. Могу даже предположить, что Сэджвик на страницах своей книги в заданиях вряд ли давал научные неразрешенные проблемы, как это делает Кнут. Правда в чем сила Кнута в том наверно его и недостаток, читать его неимоверно трудно - нужно превосходное знание математики и куча свободного времени, поэтому скорее всего он и не используется практиками. По мне его 3 тома нужно лет 5 основательно изучать либо в учебном заведении, либо самостоятельно и тогда откроется истина:) А так конечно Сэджвик даже предпочтительнее...
Ну, вы рассуждаете, действительно как студент :) , т.е. как человек недавно приступивший грызть «гранит науки». На самом деле Кнут «фундаментален» и «исчерпывающ» только для своего времени, не нужно забывать про это. «Математическая строгость» у него относительная, т.к. свои вычисления он проводит для придуманной им виртуальной машины MIX, с ее псевдо ассемблером, которая весьма далека от современных компьютеров и ассемблерного кода. Поэтому я и говорю, что реальную эффективность алгоритмов следует перерассчитывать заново, с учетом собственной специфики. Конечно, у него можно почерпнуть идеологию математических вычислений и несложный математический аппарат уровня первого – второго курса мехмата, но считать это «серьезной математикой» – увольте! Хотя если вас интересует только порядок эффективности алгоритмов (уровня О-символики), без конкретных коэффициентов, то, пожалуйста, спокойно используйте формулы Кнута. Только его «фишка» состояла в том, что он часто точно вычислял неопределенные коэффициенты для алгоритмов своей виртуальной машины. Так что для «Библии» он уже немного устарел.

Ну, что из того, что Кнут в качестве упражнения предложил доказать теорему Ферма, а Сэджвик – нет? Для поиска научных проблем вполне можно использовать другую литературу. Однако, если вы занимаетесь реальной научной работой, то вам собственных «научных проблем» хватит за глаза. У меня даже в курсовых и дипломном проекте, были сформулированы классы задач, которые еще «не знала математика» . Ну и что из того? И практически в каждой статье, посвященной прикладной науке, которыми я «баловался» в свое время я всегда выходил на неизвестные классы математических задач. Причем, все мои исследования были посвящены практическим приложениям. В то время я часто думал, что неплохо было бы привлекать профессиональных математиков для решения этих новых классов задач, и им было бы интересно и прикладной науке полезно. А то они (математики – теоретики) в своей аспирантуре, как правило, решают задачи, которые наверняка еще сотни лет не будут востребованы наукой. К сожалению, для этого у меня не было и нет соответствующих ресурсов. Скажем, недавно мне приходилось консультировать одного к.т.н-а, которому были выделены жалкие финансовые крохи на исследования в области борьбы с газовыделением в шахтах, так вот я с огромным удивлением обнаружил, что гибель шахтеров от взрывов метана и угольной пыли связанна не с «абсолютно случайной, неуправляемой природной стихией», типа землетрясений и вулканов, а с тем, что до сих пор нет адекватной математической модели образования катастрофически быстро растущей трещинноватости в горных породах (часто со сверхзвуковой скоростью) на средних и больших глубинах (для малых глубин матаппарат вполне адекватен). Самое смешное, что есть человек, который занимается проблемой сверхзвукового образования трещин на больших глубинах шахт уже более 20-ти лет. Фамилия его А.В. Шестопалов (ИПКОН РАН, Москва). Но, как легко предположить, и так на самом деле, он как Дон Кихот пытается побороть академическую науку с ее непотопляемыми заблуждениями относительно взрывоопасности в шахтах. А шахтеры, как гибли, так и гибнут. По сути это опальный или оппозиционный ученый. Да, у него сейчас есть собственный сайт и даже сторонники, но нет финансов и поддержки. Когда я ознакомился с его концепцией происхождения взрывов в шахтах, то стразу ему «поверил», в отличие от других ученных, исповедующих традиционные взгляды в этих вопросах. Проблема только за малым, воплотить концепцию Шестопалова в математическую модель. Но у него не хватает математического образования, а добровольные помощники предлагают строить модель на базе конечных автоматов, что вряд ли приведет к успеху, по моему мнению. В данном случае научная проблема сформулирована не мной, но важно другое, что нет пока математиков профессионалов, которые бы «занялись» ею. Прошу прощения, за столь длинный экскурс примера формулирования реальных научных проблем, взамен абстрактно-теоретических (и часто никому не нужных).

Далее по Кнуту. Можно спокойно игнорировать его математику, достаточно конечных формул определяющих порядок производительности алгоритмов (но конкретным коэффициентам особо не следует верить для современных реализаций этих алгоритмов). Потом, знание всех алгоритмов совершенно не обязательно, достаточно общий идей для какого класса задач, какие алгоритмы наиболее подходящи. И 5 лет его совершен не нужно изучать, достаточно пары месяцев и то урывками. Для современного программирования он мало приспособлен. Скажем мне понадобился хороший алгоритм внешней сортировки, так нашел я его не у Кнута, понадобились B+ деревья, их также не было у Кнута. И даже алгоритм быстрой сортировки, который есть у Кнута, гораздо лучше исследован в http://www.codenet.ru/progr/alg/qsort.php . Еще можно рекомендовать «Методы сортировки и поиска» С.Д. Кузнецова http://www.citforum.ru/programming/theory/sorting/sorting2.shtml