Путь от быдлокодера до программиста.

Н. Вирт "Алгоритмы + Структуры данных = программы". Потом SICP.

Д. Кнут "Искусство Программирования"

Особенно третью часть. "Поиск и Сортировка"

> Д. Кнут "Искусство Программирования"

Пока на неге у меня нет времени. Надо не сильно обьемное.

По алгоритмам и основным структурам данных есть отличная и офигенно доступная для начинающего(в отличие от Кнута и Вирта) книга - А. Шень Программирование: теоремы и задачи. Написана с расчетом на нетупого быдлокодера/первокурсника/одинадцатиклассника. Електронная версия тут - http://doors.infor.ru/allsrs/math/

Кнут не осилил ФП => печ

>в отличие от Кнута и Вирта

4.2 Если нет ГСМ, вполне понятные и простые книги, даже для начинающего.

Кормен - это всё же больше справочник, учиться по нему смысла особого нет.

SICP - правильный выбор.

> 4.2 Если нет ГСМ, вполне понятные и простые книги, даже для начинающего.

Известная фигня - люди без ГСМ любят изучать предмет по справочникам :)

SICP и HTDP

Кнута поставить на полку для важности, раз в месяц смахивать пыль.

Вирта в печку.

> изучать предмет по справочникам

Почему справочник-то, там и упражнения есть.

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

SICP -- там как бы особо содержательных вещей то и нет.

> SICP -- там как бы особо содержательных вещей то и нет.

Для начинающих, для самых маленьких, там содержательного полно.

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

Тогда сначала - SICP, потом Вирт, потом Кормен (и если потребуется более глубокое понимание - тогда и Кнут).

>одни одно советуют, другие другое

Это же ЛОР, чего еще ожидать ...

А может кто-нибудь скажет о

Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман Структуры данных и алгоритмы

Как книга?

Классика. Как и Вирт, Кормен и Кнут.

Всё читай. А ещё лучше пиши.

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

SICP и HTDP очень полезные книги для прочищения мозга, уже хотя бы отсутствием рекламной мишуры (например о том, что ООП лучше процедурного стиля, а ФП вообще лучше всех). перед "искусством программирования" Кнута имеет смысл прочитать его же (в соавторстве с Грэмом и Паташником) книгу "конкретная математика, основание информатики" - и скорее всего осознать, что прежде чем читать дальше следует подтянуть математику

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

Пожалуй начну с

Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман Структуры данных и алгоритмы

а там посмотрим.

> Кормена полезно использовать как справочник,

не соглашусь. Про Кнута так можно сказать -- его тяжело читать и его много. Кормен содержит идеи которыми должен владеть любой человек, и Кормен, несмотря на объем, читается легко.

>не соглашусь. Про Кнута так можно сказать -- его тяжело читать и его много. Кормен содержит идеи которыми должен владеть любой человек, и Кормен, несмотря на объем, читается легко

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

Кормен - это не справочник, а учебник. Если кто не в курсе, его писали преподы MIT-а для студентов MIT-а. Я вот осили его только на 2/3 за целый год изучения. И хочу сказать, что вот так вот сразу вы далеко не любой пример из Кормена переведёте в реальный код. Книга специально простроена таким образом, чтобы кодирование алгоритма стало возможным только после того, как программист досконально в нём разберётся. А те кто орёт, что Кормен - это справочник... и не читали его вовсе... только обложку на озоне видели. Мне для практики понадобились как то RBTree, и я решил, что так как изучал их, причём доконально по книге Кормена, смогу легко написать соответствующий код. Неичего подобного - пришлось ещё раз читать, вникать и понимать. Так что, мальчики, Кормен - это серьёзная книга, написанная строгим математическим языком, но без упора на математику. Изучить его за месяц-два у вас не получится. А тех балоболов которые осилили Кормена за пару месяцев можно только апоздравить. Поздравляю, придурки!

> Неичего подобного - пришлось ещё раз читать, вникать и понимать

Сам то понял, что сказал, дурик?

Это и называется - справочник. Нельзя прочитать и забыть, оно всё время на столе должно быть.

>Мне для практики понадобились как то RBTree, и я решил, что так как изучал их, причём доконально по книге Кормена, смогу легко написать соответствующий код. Неичего подобного - пришлось ещё раз читать, вникать и понимать

и что же такого сложного в красно-чёрных деревьях, что тебе пришлось "читать, вникать и понимать" ? :)

Ну ладно, допустим Кормен будет пока сложен, а вот Ахо то вышеозначенный нормально будет? А в SICP алгоритмы и структуры данных не рассматриваются? Тогда почему ее все советуют?

SICP пойдёт с нуля; возможно для последнего задания тебе понадобиться ознакомиться с драгон бук.

«Конкретная математика» — очень интересная книга! Ты должен и её проработать.

> и что же такого сложного в красно-чёрных деревьях, что тебе пришлось "читать, вникать и понимать" ? :)

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

>Ну ладно, допустим Кормен будет пока сложен, а вот Ахо то вышеозначенный нормально будет? А в SICP алгоритмы и структуры данных не рассматриваются? Тогда почему ее все советуют?

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

>Поздравляю, придурки!

ПНХ

2топикстартер

начинай с Кормена, зачотная книга

> А в SICP алгоритмы и структуры данных не рассматриваются?

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

Грис, "Наука программирования"

Бентли, "Жемчужины программирования"

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

>А какой язык лучше использовать для написания тестовых программ?

C, Scheme

Pascal

а для отдыха читай CODE петзольда ;)

> Pascal

В слове Python 5 ошибок — логопед за вами уже выехал.

+ 1. Только что скачал и просмотрел содержимое. Отличная книженция. Большое спасибо.

>> А какой язык лучше использовать для написания тестовых программ?

> Scheme

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

> и что же такого сложного в красно-чёрных деревьях, что тебе пришлось > "читать, вникать и понимать" ? :)

Улыбчивый ты мой! Вот тебе один из 7 основных методов красно-чёрных деревьев. Не самый сложный, между прочим. Удаление раза в три сложнее. Нука, скажи-ка нам по-быстрому что тут происходит, структуру объясни. Ты ведь всё поймёшь ну максимум минут за 10. А если развернуть все Rotate то + 5 минут я тебе дам дополнительно.

template<class TRBNode>

void RBTree<TRBNode> :: AddFixup( TRBNode* z ) { while ( z->parent->color == RBNodeColor_Red ) { if ( z->parent == z->parent->parent->left ) { TRBNode* uncle = z->parent->parent->right;

if ( uncle->color == RBNodeColor_Red ) { z->parent->color = RBNodeColor_Black;

uncle->color = RBNodeColor_Black;

z->parent->parent->color = RBNodeColor_Red;

z = z->parent->parent; }

else { if ( z == z->parent->right ) { z = z->parent;

RotateLeft( z ); }

z->parent->color = RBNodeColor_Black; z->parent->parent->color = RBNodeColor_Red;

RightRotate( z->parent->parent ); } }

else { TRBNode* uncle = z->parent->parent->left;

if ( uncle->color == RBNodeColor_Red ) { z->parent->color = RBNodeColor_Black;

uncle->color = RBNodeColor_Black;

z->parent->parent->color = RBNodeColor_Red;

z = z->parent->parent; } else { if ( z == z->parent->left ) { z = z->parent;

RotateRight( z ); }

z->parent->color = RBNodeColor_Black;

z->parent->parent->color = RBNodeColor_Red;

RotateLeft( z->parent->parent ); } } } }

template<class TRBNode> 

void RBTree<TRBNode> :: AddFixup( TRBNode* z )
    {
     while ( z->parent->color == RBNodeColor_Red )
         {
          if ( z->parent == z->parent->parent->left ) 
              {
               TRBNode* uncle = z->parent->parent->right;

               if ( uncle->color == RBNodeColor_Red )
                   {
                    z->parent->color = RBNodeColor_Black;

                    uncle->color = RBNodeColor_Black;

                    z->parent->parent->color = RBNodeColor_Red;

                    z = z->parent->parent;
                   }

               else
                   {
                    if ( z == z->parent->right ) 
                        {
                         z = z->parent;

                         RotateLeft( z );
                        }

                    z->parent->color = RBNodeColor_Black;
                    z->parent->parent->color = RBNodeColor_Red;

                    RightRotate( z->parent->parent );
                   }
              }

          else
              {
               TRBNode* uncle = z->parent->parent->left;

               if ( uncle->color == RBNodeColor_Red ) 
                   {
                    z->parent->color = RBNodeColor_Black;

                    uncle->color = RBNodeColor_Black;

                    z->parent->parent->color = RBNodeColor_Red;

                    z = z->parent->parent;
                   } 
                        
               else 
                   {
                    if ( z == z->parent->left ) 
                        {
                         z = z->parent;

                         RotateRight( z );
                        }

                    z->parent->color = RBNodeColor_Black;

                    z->parent->parent->color = RBNodeColor_Red;

                    RotateLeft( z->parent->parent );
                   }
              }       
         }
    }

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

хорошая в общем книжка: Игорь Одинцов "Профессиональное программирование, системный подход" изд-во bhv 2002 ISBN 5-94157-131-3 . Там не про обучение чему-то одному конкретному, а про систему обучения, набор навыков и умений, которые отличают программиста от быдлокодера

+1

Это легко, бесспорно. Как же можно было унизить такой лёгкостью!

А теперь все дружно пробуем разобраться в удалении!

Продолжение в сл. посте!

template<class RBNode>

void RBTree<RBNode> :: Remove( RBNode* z ) { RBNode* y; RBNode* x;

if ( ( z->left == RBTree<RBNode> :: RBNode_Nil ) || ( z->right == RBTree<RBNode> :: RBNode_Nil ) ) { y = z; }

else { y = Successor( z ); }

x = ( y->left != RBTree<RBNode> :: RBNode_Nil ) ? y->left : y->right;

x->parent = y->parent;

if ( y->parent == RBTree<RBNode> :: RBNode_Nil ) { root = x; }

else { if ( y == y->parent->left ) { y->parent->left = x; } else { y->parent->right = x; } }

if ( y != z ) { z->SetKey( y->GetKey() ); }

if ( y->color == RBNodeColor_Black ) { RemoveFixup( x ); } }

template<class RBNode> 

void RBTree<RBNode> :: RemoveFixup( RBNode* x )
    {
     while ( x != root && x->color == RBNodeColor_Black ) 
         {
          if ( x == x->parent->left )
              {
               RBNode* w = x->parent->right;

               if ( w->color == RBNodeColor_Red ) 
                   {
                    w->color = RBNodeColor_Black;
                    x->parent->color = RBNodeColor_Red;
                    RotateLeft ( x->parent );
                    w = x->parent->right;
                   }


               if (   ( w->left->color  == RBNodeColor_Black ) && 
                      ( w->right->color == RBNodeColor_Black )  ) 
                   {
                    w->color = RBNodeColor_Red;
                    x = x->parent;
                   } 

               else
                   {
                    if ( w->right->color == RBNodeColor_Black ) 
                        {
                         w->left->color = RBNodeColor_Black;
                         w->color = RBNodeColor_Red;
                         RotateRight( w );
                         w = x->parent->right;
                        }

                    w->color = x->parent->color;
                    x->parent->color = RBNodeColor_Black;
                    w->right->color = RBNodeColor_Black;
                    RotateLeft( x->parent );
                    x = root;
                   }
              }


          else
              {
               RBNode* w = x->parent->left;

               if ( w->color == RBNodeColor_Red ) 
                   {
                    w->color = RBNodeColor_Black;
                    x->parent->color = RBNodeColor_Red;
                    RotateRight( x->parent );
                    w = x->parent->left;
                   }

               if ( w->right->color == RBNodeColor_Black && 
                    w->left->color  == RBNodeColor_Black )
                   {
                    w->color = RBNodeColor_Red;
                    x = x->parent;
                   } 
                        
               else
                     {
                if ( w->left->color == RBNodeColor_Black )
                                   {
                    w->right->color = RBNodeColor_Black;
                    w->color = RBNodeColor_Red;
                    RotateLeft( w );
                    w = x->parent->left;
                   }

                w->color = x->parent->color;
                x->parent->color = RBNodeColor_Black;
               w->left->color = RBNodeColor_Black;
                RotateRight( x->parent );

                x = root;
               }
                   }
           }

        x->color = RBNodeColor_Black;
   }

Дружок, разберёшься в удалении - получишь пирожок. Только ты эта... быстрее...

"Pragmatic Programmer" by Andrew Hunt, David Thomas (rus: ISBN 0-201-61622-X)

"Programmer's Stone"

чего-нибудь Алистера Кобёрна (Alister Cockburn) про методологию & agile

> Тут вся сложность не в красночёрных деревьях, а в ублюдочности языка. > На том же OCaml, при всей его примитивности, то же самое делается > легко и непринуждённо.

Никто и не отрицает. Даже соглашусь. Но всё равно - рбдеревья - непростые структуры, как списки. И нехрен всяким балоболам, которые "кнута пролистывают" пороть охинею.

> Никто и не отрицает. Даже соглашусь. Но всё равно - рбдеревья - непростые структуры, как списки.

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

Eric Raymond, "The Art Of Unix Programming", гы-гы-гы :))