Видеозаписи лекций ведущих университетов

Хотите послушать стенфордский курс лекций по Programing Methodology ("Технологии Программирования", в вольном переводе) ? Или, может быть, серию лекций по поисковым системам в Беркли, или курс "Теория Игр" Наумовой в Йельском университете? Может быть, вас интересует биология или авиаконструирование? Все эти лекции и еще куча других доступны online на YouTube и AcademicEarth. Бесплатно.

А вот что у нас доступно на лоббируемом министрами школьном портале за 14 миллионов рублей. Ok, вот есть еще десяток лекций университетского уровня. Кто-нибудь может пополнить  коллекцию?

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

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

Идея курсовой или дипломной работы

DSL (доменно-специализированный язык) для управления объектами физического уровня СУБД.

Те, кто посещал лекции по СУБД на 4м курсе, знают, что в СУБД есть такой физический уровень, в котором типичными объектами являются дисковые блоки и записи в блоках, а типичными операциями являются чтение/запись блоков с диска в память и обратно и какие-то действия с записями (например, сортировка).

Для управления физическим уровнем есть всякие библиотеки, написанные на C/C++/Java, пользуясь которыми, в принципе, можно состряпать из блоков и записей какой-нибудь индекс или реализовать алгоритм sort join. К сожалению, у таких библиотек часто довольно высокий "входной уровень", то есть для того чтобы начать ими эффективно пользоваться, нужно потратить на изучение больше чем час-другой. У них много отвлекающих и пугающих артефактов, например какие-нибудь страшные транзакции. Кроме того, все эти библиотеки разные, и мигрировать с одной на другую без полной переделки всего использующего их кода невозможно.

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

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

В моих лекциях по СУБД 2008 года была (далеко не самая удачная) попытка изобрести такой язык. Вот в этой статье можно почитать про нечто похожее (с гораздо более широкими амбициями, насколько я понимаю):

http://doi.acm.org/10.1145/169683.174157

Если есть желание этим заняться -- обращайтесь.

Google Summer of Code 2009

Если вам нравится программировать, если вы хотите, чтобы результат вашего стучания по клавишам увидел кто-то кроме вас, если хотите пообщаться с разработчиками известных программных продуктов и наконец, если летом у вас остаётся время, свободное от походов, костров, озёр и морей, то специально для вас начинается Summer of Code 2009.

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

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

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