Летняя школа Microsoft про структурам данных и алгоритмам

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

Скромный локальный Summer of Code

Сие послание, в основном, адресовано недавно отмучавшимся с САКОДом второкурсникам.
Если кто-нибудь не знает, чем заняться летом,  и не против что-нибудь такое полезное попрограммировать, то у меня есть для вас пара идей, добротная реализация которых может принести вам, как минимум, всемирную славу (это почти не шутка :). Обе связаны с программой GanttProject, с которой я вожусь на досуге.

1. Хочется сделать интеграцию с Google'овским календарём и контактами. Так чтоб в GanttProject'овский проект можно было засосать коллег из контактов в качестве "ресурсов", проассоцировать проект с календарём, а задачи проекта и занятые в них "ресурсы" -- с событиями календаря и их участниками.
   
   
2. Рассказываю историю:
   
   Иван Петрович -- менеджер проекта, он управляет задачами и десятком исполнителей. То задачку создаст, то назначит кого-нибудь её выполнять. Исполнтели, допустим, такие же офисные крысы, сидят за компьютерами и шарятся вконтакте работают. Скажем, делают архитектурный и технический проект торгового центра. Ивану Петровичу хочется чтоб как только он сделает в проекте задачу "нарисовать изометрическую проекцию" и назначит на выполнение 3D-мастера Колю Синицына, то у Коли в его GanttProject'е эта задача бы появилась и Коля увидел бы что у него прибавилось работы.
   
   В принципе, и Коля был бы доволен, если бы по окончании работы нажал на кнопку "задача выполнена" и эта информация мгновенно переслалась бы Ивану Петровичу
   
   А ещё им хочется чтоб это всё "просто работало", без танцев с бубном вокруг какого-нибудь Exchange сервера, системы контроля версий, базы данных или ещё чего-нибудь в этом духе. Они в принципе используют электронную почту и пересылают друг другу файлы, но уже даже Колю подзадолбало отыскивать наиболее актуальную версию файла, что уж говорить про Ивана Петровича, у которого этих Коль десять штук.
   
   Соответственно, идея: хочется чтоб в GanttProject был встроен маленький jabber клиент, который умел бы сериализовывать весь проект или его часть (одну задачу например) в читаемый текстовый вид и посылать через GMail или через QIP или через Яндекс или через локальный jabber сервер другому GanttProject'у. А тот бы полученное сообщение парсил, превращал в свои структуры и вставлял бы в проект. В совсем сказочном мире Иван Петрович просто написал бы Коле в GTalk: "Коля, сделай изометрическую проекцию, срок три часа", а Коля через три часа ответил бы "Сделано". И всё это отобразилось бы в GanttProject. Но мы увы не в сказке и подобный диалог придётся вести между машинами, а людям давать интерфейс с кнопками.

Язык разработки -- Java. Обе идеи предполагают использование сторонних библиотек и чтение документации и стороннего кода. Сроки ничем в общем-то не ограничены, но делать такие задачи дольше чем несколько недель, наверное, не стоит. Система контроля версий -- SVN. Дисциплина строгая :) Реализация должна быть качественной во всех смыслах, поэтому надо, во-первых, быть готовым писать хороший код, во-вторых, следовать стилистическим соглашениям, в-третьих, уметь выдавать код небольшими порциями, а в четвёртых, после code review каждой порции не сидеть букой ((С) не мой) а исправлять указанные недостатки. Всё как у взрослых, короче.

Добротная реализация этх вещей, повторюсь, принесёт как минимум всемирную благодарность (ибо GanttProject -- програмулина довольно таки популярная), а в материальном плане, возможно, принесёт немного денег. Золотые горы не обещаю. Но на несколько хороших книг хватит (может, книги и объявить призом?).

Кому интересно -- пишите. Общие вопросы лучше наверное задавать прям тут (чтоб всем были видны), более приватные -- по почте.

Обновление graph.zip

Спасибо Севе и Артёму за багрепорты, багфиксы, и новые тесты :)
graph.zip

Обновление graph.zip

Очередная версия graph.zip с исправленным тестом testCycleDFS, реализацией интерфейса Paper и примитивными тестами для SearchEngine.

Разминка 14 мая

Вот вам простенький вопросик:
какое максимальное число Фибоначчи можно вычислить этим кодом?

class Fibonacci {
  public static int f(int n) {
    if (n==0) {
      return 0;
    }
    if (n==1) {
      return 1;
    }
    return f(n-1) + f(n-2);
  }

}

1. Что-то близкое к Integer.MAX_INT
2. Что-то близкое к F₈₀₀₀
3. Зависит от параметров запуска java машины

Тесты для топологической сортировки и интерфейсы для поисковика,

Обновлённый graph.zip содержит (простенькие) тесты топологической сортировки и интерфейсы для SearchEngine.

Немного тестов BFS

Добавилось наконец-таки несколько тестов для BFS. На прежнем месте: http://barashev.net/src/graph.zip

Занятие 16 апреля: разминка

Вопрос 1

В каком порядке будут напечатаны строки после выполнения этого кода?

// HashSet -- это множество, реализованное хеш-таблицей

void test(HashSet hs) {

  hs.clear();

  for (int i=0; i<=100; i++) {
    // Строковое представление числа
    hs.add(String.valueOf(i));
  }

  // Проходим по множеству

  for (Iterator i = hs.iterator(); i.hasNext();) {

    System.out.println(i.next());

  }

}

1. В некотором порядке, одинаковом для любого экземпляра hs
2. В порядке, зависящем от конкретного экземпляра hs
3. В порядке добавления
4. В лексикографическом порядке

Графы: алгоритмы

Итак, обещанные алгоритмы на графе. Минимальный джентльменский набор -- обход в ширину, обход в глубину, топологическая сортировка. Но они завёрнуты в более-менее взрослые интерфейсы: итераторы и (псевдо-)визиторы.

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

Визитор (Visitor) в классическом виде -- это сложный и практически неприменимый шаблон проектирования. У нас будет профанация визитора, представляющая собой в общем-то тот же итератор, но с вывернутой наизнанку последовательностью управления. Если при переборе итератором команды "стой! шаг вперёд! руки за голову"  отдаются клиентом, а итератор их послушно исполняет, то в случае визитора всё наоборот: клиент инициирует итерирование и передаёт алгоритму объект-визитор. Итерирование идет само, без участия клиента, а при переходе к очередному элементу алгоритм вызывает методы визитора: "эй, ты, у меня тут следующий клиент -- хочешь с ним что-нибудь сделать?". Такой "визитор" называют иногда callback'ом, что на русский переводится корявой фразой "функция обратного вызова".

Архив с интерфейсами графа и алгоритмов на прежнем месте: http://barashev.net/src/graph.zip

Занятие 2 апреля: разминка

Вопрос 1.

Что делает метод hasCycle(), при условии что длина списка равна N?

01: class Node {
02: Node next;
03: Object value;
04: }
05:
06: class List {
07: Node first;
08:
09: boolean hasCycle() {
10: if (first == null) return false;
11:
12: int stepCount = 1;
13: Node t1 = first;
14: Node t2 = first;
15:
16: while (true) {
17: t1 = t2;
18: stepCount *= 2;
19: for (int i = 0; i < stepCount; i++) {
20: t2 = t2.next;
21: if (t2 == null) return false;
22: if (t2 == t1) return true;
23: }
24: }
25: }
26: }

1. Проверяет наличие цикла за время O(log(N))
2. Проверяет наличие цикла за время O(N)
3. Проверяет наличие цикла за время O(N*log(N))
4. Проверяет наличие цикла за время O(N^2)
5. Иногда тупо зависает в бесконечном цикле

Вопрос 2

Какая структура данных больше подходит для реализации обхода в ширину?

1. FIFO
2. LIFO
3. GIGO
   

Написание программ на родном языке является реальностью.

Вы когда-нибудь мечтали написания программ на вашем родном языке, без обучения Java, C + + и все другие вещи? Теперь вы можете. Просто введите программы на русском, китайском или любом другом человеческом языке, а также опубликовать его в Интернете. Вам даже не придется беспокоиться о правильности написания. Поиск кода Google будет автоматически переводить ваш код Английский для тех, кто не говорят Ваш родной язык.

Проверьте перевод на примерах http://google.com/codesearch и FUNNAH!

Тесты для графов

Первый вариант тестов для графов. Брать тут: http://barashev.net/src/graph.zip

Занятие 19 марта: графы

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

Наш граф (интерфейс Graph) состоит из осязаемых объектов-вершин (интерфейс Vertex) и неосязаемых дуг. Граф умеет создавать вершины и отдавать список созданных. Вершина умеет создавать и удалять дуги в другие вершины и хранить произвольные свойства.

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

Интерфейсы можно скачать здесь: http://barashev.net/src/graph.zip
Тестов пока нет, будут позже. На следующем занятии работаем над простешими алгоритмами.

Занятие 19 марта: разминка

Постройте бинарное дерево поиска из этого массива: [10, 15, 5, 12, 20, 25] и напишите результат обходов в глубину и в ширину.

На всякий случай, числа добавляются в дерево именно в таком порядке, в каком идут в массиве.

Занятие 5 марта: разминка

Два вопроса на знание некоторых тонкостей

Вопрос 1.
Что будет напечатано в консоли после выполнения такого кода:

class Test {
  String[] keys = new String[] {"key1", "key2"};

  boolean find(String key) {
    for (int i=0; i<keys.length; i++) {
      if (keys[i] == key) 
        return true;  
    }
    return false;
  }
}

Test t = new Test();
if (t.find("key1"))
  System.out.println("key1");
if (t.find(new String("key2")))
  System.out.println("key2");

Вопрос 2
Что вернёт метод size() ?

class Key {
  int x;
  int y;
  Key(int x, int y) {
    this.x = x;
    this.y = y;
  }
  int hashCode() {
    return x+y;
  }
}
HashTable t = getHashTable();
t.put(new Key(0,0), "value1");
t.put(new Key(0,0), "value2");
System.out.println(t.size());

Первое занятие: хеш-таблицы

На первом занятии 19 февраля начали реализовывать хеш-таблицу. В нескольких словах, задача такая: "с нуля", не пользуясь никакими стандартными классами коллекций из JDK реализовать хеш-таблицу с заданным интерфейсом. Код должен проходить тесты и быть качественным.

Исходный код интерфейса и тестов скачивать тут: http://barashev.net/src/hashtable.zip

САКОД 2009. Поехали.

Где и когда.
Практика по предмету Структуры и Алгоритмы Компьютерной Обработки Данных в группе 243 проходит по четвергам на второй паре в аудиториях 2406 и 2528.

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

Что.
Будем реализовывать (писать код, ага) хм... структуры и алгоритмы :). Начнём с хеш-таблицы, а что будет дальше -- зависит от уровня подготовки и от успехов с хеш-таблицей.

Доколе.
Зачёт получает тот, кто успешно реализовывает структуры и алгоритмы. "Успешно реализовывает" означает что реализации проходят тесты и мой собственный контроль качества. Контроль серьёзный, халявы не будет, но террора тоже не будет. Будет большая польза для будущих хороших программистов.