LINUX.ORG.RU

А есть нормальная и адекватная литература по структурам данных и алгоритмам

 , ,


4

2

Собственно потребовалось ручками реализовывать разные деревья, решил книжки посмотреть, а там непотребство пишут - даже на простых вещах обсираются по полной, как пример путают Tree Sort с поиском по BST дереву, хотя Tree Sort в общем случае вполне себе работает с данными, которые дублируются, т.к. работает с частично-упорядоченными бинарными деревьями, а не с BST деревьями, которые по определению полностью упорядоченные.

★★★★★

Седжвик первое издание алгоритмов на C самая вменяемая и компактная книженция. Если хочется больше теории — очевидный Кормен.

anonymous ()
Ответ на: комментарий от xaizek

Точно. По крайней мере википедия упорота на обоих языках (и на русском и на английском), как и большая часть сайтов, а разные авторы трактуют разные вещи одними и теми же терминами или скатываются исключительно к BST, который для сортировки не годен, если не все ключи уникальны.

peregrine ★★★★★ ()
Ответ на: комментарий от ox55ff

Дональд Кнут, «Искусство программирования для ЭВМ»

Эта та книжка, где примеры на ассемблере?

для машины MIX. Она самая.

Хороший способ бесцельно потратить время.

А какая разница, на чём? Ну да, на си или на паскале было бы удобнее. Но скажи ещё спасибо, что не на алголе, потому что систему команд MIX выучить гораздо легче. А ещё там блок-схемы есть кроме кода. Да и какая разница, на чём? Освоил язык (а Кнут намеренно сделал его максимально простым и компактным) и вперёд! Алгоритмы же. А в качестве упражнения и закрепления материала можешь сам реализовывать на си или на чём тебе там больше нравится. А потом в глобальную сеть выложить. Будет и тебе польза, и остальным.

aureliano15 ()
Ответ на: комментарий от peregrine

скатываются исключительно к BST, который для сортировки не годен, если не все ключи уникальны.

Почему? Там просто дубликаты будут идти в одно из поддеревьев, но работать то оно будет.

Точно. По крайней мере википедия упорота на обоих языках (и на русском и на английском), как и большая часть сайтов

Так а у Вас откуда это предстваление том, что как правильно называть? Есть какой-то источник? Меня просто удивляет эта нестандартная трактовка.

xaizek ★★★★★ ()
Ответ на: комментарий от aureliano15

для машины MIX

В новом издании весь код уже переписан на MMIX, если что.

А какая разница, на чём?

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

xaizek ★★★★★ ()
Ответ на: комментарий от peregrine

первое, что приходит в голову - тупо добавить счётчик к каждому узлу дерева и вот тебе дерево для сортировки любого количества повторяющихся ключей. можешь добавить список, если ключи имеют какую-то расширенную информацию

Iron_Bug ★★★★ ()
Ответ на: комментарий от xaizek

Почему? Там просто дубликаты будут идти в одно из поддеревьев, но работать то оно будет.

Не совсем хорошо будет работать - смотри например тут, про описание реализации вставки. И да, там формулировка дерева другая несколько.

Так а у Вас откуда это предстваление том, что как правильно называть?

Что непонятно? Тыц про деревья.

peregrine ★★★★★ ()
Ответ на: комментарий от peregrine

У нас дубль создаст новый узел с точно таким же значением ключа и поместит его в правое поддерево узла с оригинальным ключом. В результате новый узел никогда не будет обнаружен в процессе поиска.

Так это же проблема их реализации (если можно иметь дубликаты, то надо их искать при поиске), а для сортировки вообще не проблема.

Что непонятно?

Не понятно с чего бы вдруг какие-то минорные разногласия в терминологии были проблемой.

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

Есть только первая часть четвёртого тома (из трёх).

Всё-таки неподъёмную задачу он на себя взвалил с этим «Искусством программирования» и так и не осилил до конца. Но то, что осилил, выполнил блестяще.

для машины MIX

В новом издании весь код уже переписан на MMIX, если что.

А в чём между ними разница, если в 2 словах?

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

Это, кстати, тоже полезное дело, даже с учётом поправки на то, что разные машины поддерживают разный набор команд, и одни и те же команды могут быть по-разному реализованы (где-то одни команды оптимизированы, а где-то другие).

С языками так не получится.

Хотя, конечно, с языками высокого уровня попроще. Но тут ещё надо было угадать тренды, какие языки вымрут, а какие останутся.

aureliano15 ()
Ответ на: комментарий от MyLord

В чем проблема с алголом?

Да ни в чём. Против него я ничего не имею. Да и не могу иметь, т. к. не знаю этот язык. Просто он давно умер. И учить его сейчас только для того, чтоб понять книжку, имхо, намного сложнее, чем выучить ассемблер MIX с минимальным набором команд, т. к. Алгол был полноценным высокоуровневым языком.

aureliano15 ()
Ответ на: комментарий от xaizek

Не понятно с чего бы вдруг какие-то минорные разногласия в терминологии были проблемой.

Подумаешь в арифметике заменили бы деление с остатком делением нацело...

peregrine ★★★★★ ()
Ответ на: комментарий от aureliano15

При знании паскаля алгол читается очень легко, как псевдокод. Тем более учебные алгоритмы сортировки. Но первый том вышел в 68 году. Тогда ещё не было Паскаля, Микрософта и IBM pc, а программирование на ассемблере было обычным занятием.

MyLord ()
Ответ на: комментарий от MyLord

первый том вышел в 68 году. Тогда ещё не было Паскаля, Микрософта и IBM pc, а программирование на ассемблере было

и си не было, зато алгол-68 как раз появился.

Нет, высокоуровневое программирование, конечно, уже давно практиковалось. Кроме алгола ещё и фортран был распространён. Наверно, было и ещё что-то, но даже этих 2 языков достаточно.

Скорее всего, он действительно хотел, чтоб читатель мог оценить скорость алгоритма чуть ли ни в машинных тактах. Возможно, дополнительной задачей было показать, что и на ассемблере можно писать ясный код.

aureliano15 ()
Ответ на: комментарий от aureliano15

Скорее всего, он действительно хотел

Я Кнута не читал, но разве он при введении своей абстрактной машины не объясняет причины такого выбора? Обычно принято хоть как-то обосновывать причину выбора инструмента при наличии альтернатив.

Virtuos86 ★★★★★ ()
Ответ на: комментарий от Virtuos86

разве он при введении своей абстрактной машины не объясняет причины такого выбора?

Он объяснил, что реальные ассемблеры приходят и уходят и их очень много, поэтому каждый из них по отдельности мало кому нужен. С другой стороны, он оговорился, что ассемблер для несуществующей машины вообще никому не нужен. Но MIX очень похожа на все существующие (на тот момент) машины и в этом плане идеальна.

А вот что он написал про языки высокого уровня Алгол и Фортран (этого я не помнил, специально сейчас открыл предисловие к 1-му тому, ниже краткий пересказ, — перепечатывать полностью лениво):

  1. они больше подходят для численных задач;
  2. они сильно влияют на программиста, навязывая ему не самые оптимальные конструкции с точки зрения машины;
  3. большинство примеров в книге очень короткие, и ассемблера для них достаточно;
  4. все обязаны знать ассемблер, потому что без него никуда (напомню, что сей с крестами в то время не было);
  5. для нескольких программ из нескольких глав необходим ассемблер.
aureliano15 ()
Ответ на: комментарий от aureliano15

В новом издании весь код уже переписан на MMIX, если что.

А в чём между ними разница, если в 2 словах?

У MMIX 64-бита, RISC-архитектура, 256 регистров общего назначения и никакого двоично-десятичного кодирования.

xaizek ★★★★★ ()
Ответ на: комментарий от anto215

И кажись есть этого же автора аналогичная книга только применительно к C++

Начиналось все с Алгоритмов на Си (1990 год). Эта книга Седжвика самая кошерная. Дальше он занялся коммерцией: накачивание водой и дублирование под разные язычки. И примеры стали неряшливые.

anonymous ()
Ответ на: комментарий от peregrine

Подумаешь в арифметике заменили бы деление с остатком делением нацело...

Нету такой разницы в терминах, хоть путаница иногда бывает. Просто никаких «единственно правильных» терминов не существует. Какие-то авторы добавляют определения для частных случаев, а какие-то нет. Какие-то термины популярны, какие-то нет, какие-то дублируют понятия. Я поэтому и удивился, услышав, что какой-то источник является более правильным чем другие.

P.S. Aho+Ullman «The Design and Analysis of Computer Algorithms», кажется, никто не вспомнил.

xaizek ★★★★★ ()
Ответ на: комментарий от aureliano15

Классика: Дональд Кнут

Это для лохматых ботанов из 70-х. Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух. Совершенно бесполезный талмуд.

anonymous ()
Ответ на: комментарий от Bobby_

Скажи, что не осилил.

Открою страшную тайну: его никто не осиливает в полном объеме. А те кто таки осилил, как Седжвик тот же (учившийся у Кнута), тут же бегут писать книги по алгоритмам для людей.

anonymous ()
Ответ на: комментарий от Bobby_

книжку рассчитанную на начинающего

Эта книжка расчитана на начинающего ученого, балда. Просто возьми старые книги для кодеров (Вирт, Ахо) и сравни с этим талмудом. Можешь чисто внешне, даже не открывая.

anonymous ()
Ответ на: комментарий от anonymous

Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух.

Первый том - самый полезный.

tailgunner ★★★★★ ()
Ответ на: комментарий от anonymous

Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух.

если бы ещё еду заносили )

Harald ★★★★★ ()