*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

воскресенье, 6 июня 2010 г.

Немного об алгоритмах

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

Scheduling для двоих детей, особенно с небольшой разницей в возрасте, конкретно отличается от одного, и является гораздо более сложной оптимизационной задачей, ибо количество переменных увеличивается на порядок. Но в целом - переходный процесс уже начал стабилизироваться, и снова появляется время позависать на всяких сайтах с алгоритмическими задачками (успел даже поучавствовать в двух SRM'ах на TopCoder'е).

Например, сайт Красноярского Дворца пионеров и школьников. Он позиционируется как место для самоподготовки школьников, интересующихся программированием, для олимпиад. Но хвала тем школьникам, которые могут сходу решать задачи сложности 50% и выше с этого сайта. Не всякий, как пишут в резюме, "профессиональный программист с многолетним стажем" сможет "взять" некоторые из них.

Обнаружил просто мега-сайт - e-maxx.ru/algo. Справочник по алгоритмам и их реализациями на С++. Все на русском языке. Как мне тут сказали, что, в принципе, освоив большинство из них, можно показывать неплохие результаты на программистских соревнованиях.

В разделе книг там также отличная подборка.

Из категории, опять-таки, олимпиадного программирования, могу посоветовать:



и



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

Кстати, заметил интересный факт. Лично я не люблю язык Паскаль. Мое субъективное мнение. Многословный и эстетически некрасивый синтаксис. Но Российская школа программирования уважает Паскаль и Дельфи (спасибо вечному Турбо Паскалю 7.0), и поэтому программы в этих книгах написаны на Паскале, а не на С++. И заставляя себя вчитываться в паскалевские куски кода, еще и изуродованные форматированием для печати в книге, получаешь более полное понимание алгоритма. Как говорят: умение читать код может быть даже важнее для программиста, чем писать его.

Далее. Нашел интересную страничну какого-то профессора из MIT, на которой лежат его мини видео лекции с разборами некоторых классических задач динамического программирования. Манера подачи материала очень интересна - видео представляет собой постепенную запись объяснения задачи от руки, сопровожаемую голосом. Например, задача о сдаче, или оба вида задачи о ранце - с повторами и без (0-1).

Алгоритмы - это очень интересно.

Посты по теме:

4 комментария:

  1. Поздравляю с рождением сына. Спасибо за книжки, надо будет на досуге посмотреть.

    ОтветитьУдалить
  2. Поздравляю. Скоро я тоже стану счасливым обладателем второго спиногрыза.
    А Седжвик + google, имхо, по кошернее.

    ОтветитьУдалить
  3. Я для себя выбрал:
    1)Название: Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям
    Авторы: Скиена С.С., Ревилла М.А.

    2)Алгоритмы: построение и анализ
    Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

    Но прочитав ваш пост что-то задумался, правильный ли я выбор сделал. Что можете сказать по поводу этих(моих) двух книг?
    Ссылки на описание:
    http://www.williamspublishing.com/Books/5-8459-0857-4.html

    http://lib.mexmat.ru/books/12641/s2

    ОтветитьУдалить
  4. Incognito: Эти две также однозначно достойны на мой взгляд. Первая, правда - имеет четкую ориентацию на спортивное программирование и просто разбирает конкретные задачи, а вот вторая - классический учебник.

    ОтветитьУдалить