22 апреля 2009

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

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

Drum höher und höher und höher!

Всех с наступившей неделей матмеха, гимн которого пели ещё в 1930 году немецкие бравые парни :)

А заодно и с успешным выступлением команды СПбГУ (читай матмех) в финале чемпионата мира по программированию. Литмошники правда опять впереди планеты всей -- сколько уж можно :)

16 апреля 2009

Занятие 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. В лексикографическом порядке

07 апреля 2009

Дни Санкт-Техника

Не знаю, все ли в курсе про Sun Tech Days и найдёт ли кто-нибудь  там что-нибудь полезное для себя, но таки объявлю: они начинаются завтра.

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

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

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

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

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

02 апреля 2009

Занятие 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

01 апреля 2009

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

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

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