Следующий день приёма теорзачёта будет после 10 января

Пишите свои пожелания насчёт конкретной даты. Мне пока что довольно безразлично в какой день приезжать.

Шрифт ПТ-Санс

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

С детства мечтал работать со шрифтами, но понимал что у меня никогда не хватит на это терпения.

Новый набор в клуб плагиаторов

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

Примитивный плагиат виден буквально сразу же, максимум через минуту разглядывания кода, а плагиат непримитивный требует от плагиатора усилий, сопоставимых с самостоятельным написанием кода. Этим бесславным делом заниматься не нужно. Нужно просто отковырять себя от интернета/игрушки/пива/etc почитать немного книжек и сделать задание самостоятельно. Или сформулировать свою проблему и попросить преподавателей помочь. Как вы может заметили, мы на матмехе не штаны просиживаем и не план по отчислениям выполняем. Ко всем, кто что-то делает сам, мы с  коллегами по факультету (окей, по группе управления информацией) относимся с уважением и всегда помогаем выбраться из затруднений. С теми же, кто тупо тырит чужую работу, не хочется даже разговаривать.

Вставайте уже с колен Становитесь уже взрослыми. Решать свои проблемы самостоятельно и самому формировать свою судьбу или всю оставшуюся жизнь просить у президента подачек по праздникам -- это ваш личный выбор, который нужно было сделать ещё вчера.

Зачёты в понедельник

Практика будет на второй паре (если конечно кто-нибудь придёт) в компьютерных классах, где именно -- посмотрим на месте. Ищите объявления на дверях 4390. Ко второй же паре можно подходить за теоретическими вопросами и начинать сдавать теорию на БП. Опять же, аудиторию подыщем по ходу действия.

На практику уже можно не приходить Дмитрию Коберу, Станиславу Палитко, Ренату Юлдашеву, Даниле Пономаренко. У вас с некоторыми оговорками всё хорошо, если чешутся руки таки закончить работу, то продолжайте присылать задания по почте.

Не боги фиксят баги.

Боги баги создают :)
Несколько лиричное рассуждение на Хабре про прелесть багфиксинга в работе программиста. И ведь это на самом деле бывает потрясающе интересным занятием.

Кому уже не нужно приходить на практику и кому нужно

Можно уже не приходить:
Надежде Серковой, Марату Юлдашеву

Можно не приходить но рекомендуется закончить работу по почте:
Станиславу Палитко и Павлу Москалевичу

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

Новые сведения о зачёте по СУБД.

Господа студенты, в связи с тем что у нас якобы до 28 числа продолжаются занятия, получить в четверг большую аудиторию на целый день невозможно, а скитаться всей толпой из одной в другую нет никакого желания. Поэтому внимание, слушайте коммюнике. Исправления ещё возможны, поэтому реагируйте быстрее.

Четверг 24 декабря

• Вторая пара, аудитория 2444 - практика. Тем, у кого есть долги по практике (таких немало), будет дан шанс частично или полностью их исправить. Но в этой аудитории не так много компьютеров, поэтому кто успел того будут и тапки. 
• Большой перерыв и третья пара в аудитории 03 - теоретический зачёт. Реально будет поговорить не более чем с десятком человек, при условии что они не будут тупить. Если таковые имеются, приходите в аудиторию 2444 к началу второй пары. Получайте задания и готовьтесь где угодно, после чего приходите на БП в 03 и сразу начинайте сдавать.
• Четвёртой пары, увы, не будет. 

Пятница 25 декабря

• Вторая - четвёртая пары, аудитория 01 - теорзачёт. Поговорить сможем с бОльшим количеством, что не отменяет необходимости не тупить.
  Если в пятницу у вас у всего потока какое-нибудь большое мероприятие, и на теорзачёт никто не придёт, говорите об этом быстрее. Если придёте, то тоже можете сказать, хотя бы в комментариях к этой заметке.

Суббота 26 декабря

• Вторая - четвёртая пары, не знаю где, теорзачёт. Скорее всего много кто не успеет сдать теорию в четверг и пятницу, поэтому я буду на матмехе в субботу и скорее всего буду принимать теорию. Ищите информацию о месте проведения тут на сайте или на дверях аудитории 4390

Понедельник 28 декабря

• Вторая пара -- практика. Ещё одна возможность сдать долги по практике. Где-нибудь в компьютерных классах где будут свободные места. Информация на barashev.net или на дверях 4390
• Третья и четвёртая пары -- по требованию.

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

Контрольная 17 декабря. Take off.

Дано: несколько операторов CREATE TABLE создающих некую БД. Нужно внимательно прочитать операторы и комментарии, после чего реализовать два запроса и процедуру -- они описаны в комментариях в конце листинга. Если нужны вспомогательные представления -- делайте. Если что-нибудь по предметной области непонятно -- спрашивайте.

Задания непростые. Вы можете, если сочтёте нужным, сделать какие-нибудь упрощающие предположения, но если вы будете их делать, то напишите об этом в тексте и лучше всего дополнительно спросите, не сильно ли они упрощающие.

Результат, вне зависимости от того, полностью вы выполнили задание или нет, обязательно пошлите по почте: dbms гавгав barashev.net

• Вариант 3
• Вариант 4

Для должников:

• Первая контрольная

Контрольная 17 декабря: Last Call

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

Только профайлеру известно, где оптимизировать код

Несколько дней назад я ковырялся в запутанном куске (чужого) Java кода, который перекладывает данные из одних структур в другие, сортирует, потом забывает о сортировке, складывая всё в HashSet, потом сортирует снова по тому же признаку, и всё такое прочее. Я знал, что этот код вызывается многократно и подозревал, что он далеко не оптимален.

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

Результат был потрясающ. Влияние этого куска кода на производительность было мизерное. А больше всего времени сервер проводил -- внимание! -- беря остаток от деления больших целых чисел в процедуре проверки валидности cookie и -- внимание ещё раз! -- собирая stack trace для того чтоб сделать INFO запись в логе (java.util.logging.Logger.info(), да).  Что одно, что другое с точки зрения серверного кода выглядело симпатичным вызовом одного метода, на который никто никогда в жизни не обратил бы никакого внимания.

Практика 3 декабря

Разминка
Вы хотите просуммировать зарплаты сотрудников в каждом отделе и дописать в результат ещё кое-что. В каком случае запрос будет делать то что вы ожидаете?

Таблица: Employee(emp_id PRIMARY KEY, emp_name, salary, dep_id, dep_name)

1. SELECT dep_id, dep_name, SUM(salary)
   FROM Employee
   GROUP BY dep_id, dep_name
   
   
2. SELECT dep_id, emp_name, SUM(salary)
   FROM Employee
   GROUP BY dep_id, emp_name

Слайды (полноэкранные)

Практика 26 ноября

Разминка

У вас есть таблицы A(id) и B(a_id, b). Какие из этих запросов найдут те A.id, которые НЕ упоминаются в B.a_id ?

1. SELECT id FROM A WHERE id NOT IN (SELECT a_id FROM B)
2. SELECT id FROM A EXCEPT SELECT a_id AS id FROM B
3. SELECT id FROM A LEFT OUTER JOIN B ON (A.id = B.a_id)
   WHERE B.a_id IS NULL

Слайды (полноэкранные)

Практика 19 ноября: ничего нового, доделка старого

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

Джоэл снова о программировании

Многие любят читать блог Джоэла Спольски "Joel on Software" где публикуются интересные, весёлые, не слишком заумные и в каком-то смысле полезные заметки о разработке ПО. Но английский язык там непростой, а заметки длинные, и осилить их не очень просто. Недавно вышла книжка "Джоэл снова о программировании", в которой избранные заметки очень хорошо переведены на русский, с сохранением всех приколов и стиля автора. Рекомендую для ненапряжного чтения в маршрутке :)

Практика 12 ноября

Разминка

Вопрос 1. Что получится в результате выполнения запроса?

Table1

a   b   c

---------

1   1   1

2   3   4

1   1   7

2   3   8

SELECT * FROM Table1 GROUP BY a

1. Будет напечатана вся таблица 
2. Для каждого значения "a" посчитают сумму в столбцах "b" и "c"
3. Запрос не выполнится потому что не используются агрегатные функции
4. Запрос не выполнится потому что в SELECT используются недопустимые в данном случае атрибуты

Вопрос 2. А с этим запросом и такой же таблицей что будет?

SELECT a, SUM(b) AS foo FROM Table1 GROUP BY a

1. a  foo
   1  2
   2  6
2. a  foo
   1  2
   2  2

Слайды (полнозкранные)

Практика 29 октября

Разминка

Вопрос 1. Вы делаете связь многие-ко-многим между товарами и поставщиками у которой есть собственный атрибут, например, цена данного товара у данного поставщика. Вы хотите чтоб цена была уникальна для пары (товар, поставщик). Чего не хватает в этом операторе?

CREATE TABLE Goods_Supplier(

  goods_id INT FOREIGN KEY REFERECES Goods,

  supplier_id INT FOREIGN KEY REFERENCES Supplier,

  price NUMERIC (10, 2) CHECK (price >= 0)

)

1. Да вроде всё на месте
2. Ограничения UNIQUE для цены
   
3. Ограничения UNIQUE для каждого из внешних ключей
4. Ограничения UNIQUE для пары внешних ключей
5. Ограничения UNIQUE для всей тройки атрибутов

Вопрос 2. Сколько строк будет в результате SELECT'а?

CREATE TABLE Автомобиль(

    рег_номер CHAR(6) PRIMARY KEY, марка VARCHAR(20))

INSERT INTO Автомобиль (рег_номер, марка)

  VALUES ('м000ск', 'Субару')

INSERT INTO Автомобиль (рег_номер, марка)

  VALUES ('м001ск', 'Cубару')

INSERT INTO Автомобиль (рег_номер, марка)

  VALUES ('м002ск', 'Subaru')

SELECT * FROM Автомобиль  WHERE марка = 'Субару'

Слайды

Практика 5 ноября

Разминка

Вопрос 1. Сколько будет в результате выполнения запроса если в таблице N строк?

CREATE TABLE Foobar (id INT PRIMARY KEY, value INT)

SELECT * FROM Foobar f1 JOIN Foobar f2 ON (f1.id = f2.id)

1. 0 строк
2. N строк
3. N*N строк
4. Заранее неизвестно
5. Запрос не выполнится
   

Вопрос 2. Что будет результатом запроса?

Table1
------------------------

group_id value

1        30

1        25

2        10

1        40

2        50

SELECT group_id, MAX(value) AS value FROM Table1

1. Да ничего, не выполнится запрос
2. group_id  value
   1         40
   2         50 
3. group_id value
   1         50
   1         50
   2         50
   1         50
   2         50

Занятие
Fullscreen view

УГ 6

Если вы, так же как и я, нежно ненавидите Internet Explorer 6 и каждый раз в матмеховских компьютерных классах инстиктивно проверяете, не появился ли среди установленных программ Firefox, то вот вам совет.

Скачайте с PortableApps.com дистрибутив Firefox или Chrome, который устанавливается в отдельный каталог на сетевой диск или на флешку безо всяких административных прав. Приходите в класс, втыкаете флешку, запускаете нормальный браузер, наслаждаетесь. В 2410 у меня так получилось. А вот в 2444 "у дверей", к сожалению, нет.

Контрольная No.1

Что нужно:

1. Прочитать описание предметной области
2. Составить схему БД, которая позволила бы корректно эту предметную область смоделировать. Схема -- это операторы CREATE TABLE... и опционально ER-модель на любом носителе.

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

Результат высылайте на email. Если будет бумажное дополнение (ER-модель) -- отдавайте в руки

Работу надо завершить за одну пару

Варианты работы:

1. Вариант 4
   
2. Вариант 5
   
3. Вариант 6
   

Контрольная 22 октября. Last call

Возможно, я недостаточно чётко и громко это сказал, поэтому повторю ещё раз:
пренебрегающие домашней практической работой к контрольной совершенно точно не готовы и будут только зря тратить время, своё и моё. Соответственно, и писать контрольную 22 октября для них смысла не имеет. Приходите в декабре. Или же присылайте до вечера вторника задания по почте. Это, напомню, единственный способ показать что вы таки что-то делали -- если вы присутствовали в классе или даже что-то там набивали, но ничего не показали и не послали, то вы ничего не сделали.

Сообщите pls эту информацию тем, кому это может быть интересно.

IntelliJ IDEA Комунибудь Edition

Замечательная IDE IntelliJ IDEA стала ещё более замечательной тем, что стала бесплатной и open source в базовой комплектации. Наверное, им надоело объяснять, почему почти то же самое в Eclipse стоит на двести баксов дешевле.

Прекрасно, что у Java программистов теперь есть такой широкий выбор отличных средств разработки, которого у C++ не будет никогда :)

В команде серверов замена

Сервер db1, который мы до сих использовали, помер. Вместо него на поле вышел сервер db2. Там, к сожалению, снова надо заводить пользователей и делать персональные базы данных... :/

Практика 15 октября

Разминка

Вопрос 1. Что произойдет в результате выполнения скрипта:


CREATE TABLE A (
a1 INT, a2 VARCHAR, a3 NUMERIC, UNIQUE (a1, a2))

CREATE TABLE B (
b1 VARCHAR, b2 NUMERIC, b3 INT,
FOREIGN KEY (b1, b2) REFERENCES A(a2,a3))

1. Скрипт не выполнится, потому что внешний ключ не может быть составным
2. Скрипт не выполнится, потому что ссылочные атрибуты не являются ключом
3. Скрипт не выполнится, потому что имена ссылающихся и ссылочных атрибутов разные
4. Скрипт выполнится без ошибок

Вопрос 2. Имеются две таблицы и запрос. Сколько строк и столбцов будет в результате выполнения запроса?

1. 4 строки, 5 столбцов
2. 4 строки, 4 столбца
3. 20 строк, 5 столбцов
4. 20 строк, 4 столбца

SELECT * FROM A,B WHERE a.id=B.id


A
a1 a2 id
--------
1
2
3
4
5


B
id b1
-----
4
3
2
1

Спешите видеть.

Попиарю выступление Криса Мессины в ЛИТМО. Не так часто к нам приезжают интересные люди. Спешите видеть!

Практика 8 октября

Разминка

Вопрос 1. Что произойдет в результате выполнения скрипта:

1: CREATE TABLE A (a1 INT, a2 VARCHAR)
2: INSERT INTO A (a2, a1) VALUES ('12345', 12345)

1. Скрипт упадет потому что порядок атрибутов в добавляемом кортеже не соответствует порядку атрибутов в таблице
2. Скрипт упадет потому что строчка '12345' не поместится в отведенный атрибуту a2 тип
3. Скрипт выполнится успешно

Вопрос 2. Что произойдет в результате повторного выполнения этого скрипта?

1. Скрипт упадет потому что таблица уже существует
2. Скрипт упадет потому что двух одинаковых кортежей быть не может
3. Скрипт упадет по той же причине что и в первый раз
4. Скрипт выполнится успешно

Занятие

Слайды (с ошибками)

Практика 1 октября

Разминка

Вопрос 1. Пусть существует связь R между множествами сущностей A и B. Кардинальность участника A равна 1, кардинальность участника B равна *. Какое из этих утверждений является верным?

1. Один экземпляр сущности A может участвовать только в одном экземпляре связи
2. Один экземпляр сущности B может участвовать только в одном экземпляре связи
3. В одном экземпляре связи участвует один экземпляр сущности A и неограниченное количество экземпляров сущности B

Вопрос 2. Пусть класс A наследует класс B, а тот наследует класс С. Пусть есть еще класс D. Какое из этих утверждений является НЕверным?

1. В сущности А есть все свойства определенные в классе С
2. Сущности A и B могут принимать участие во всех связях, в которых могут принимать участие сущности C
3. При удалении какой-либо сущности C удаляются все сущности A и B
4. Сущность C не может участвовать в связи R(A,D)

Работа

Слайды

Два зайца одним махом

Не буду упускать случая укокошить двух зайцев сразу.

Во-первых, на Хабрахабре наткнулся на неплохую короткую статью с рекомендациями студентам, жаждущим стать программистами. Обязательно почитайте, и обязательно до конца. Во-вторых,  раскрываю секрет, зачем я отправился на несколько дней в Калифорнию.

Имеющие глаза да увидят

24 сентября занятий не будет

Если кто вдруг забыл или не знал. 24 сентября не будет лекции и не будет практики у 423 и 424 групп. Через неделю, 1 октября, всё будет в двойном количестве

Практика 17 сентября

Разминка

1. Что из нижеперечисленного можно делать в компьютерном классе?
   
   1. Разговаривать по мобильному телефону с мамой
      
   2. Пытаться сотворить интересные вещи с вашим любимым новостным сайтом путем вбивания HTML
      кода в форуме
      
   3. Пробовать запускать SQL скрипты, написанные для MS SQL Server'а, в программе MS Access
      
   4. Сидеть в углу, жевать бутерброд и запивать его чаем, громко прихлебывая
      
2. Какое из этих утверждений является верным?
   
   1. Схему БД выдумывает администратор БД, и его слово – закон
      
   2. Одна и та же предметная область может быть смоделирована по-разному
      
   3. Задачей бизнес-аналитика является подсчет стоимости выполнения проекта
      
   4. Бизнес-аналитик принимает решение о том, как в системе будет записываться список сущностей:
      именами через запятую или именами через знак переноса строки
      
3. Если свойство “время года” может принимать значения из заранее известного конечного множества,
   то типом этого свойства будет:
   
   1. Строка, в которой записывается строковое представление значения. Например, “весна”
      
   2. Целое число, обозначающее номер значения. Значения отсортированы по алфавиту: “весна, зима,
      лето, осень”
      
   3. Специальный перечислимый тип ВРЕМЯ_ГОДА, содержащий нужное количество различных экземпляров типа
      

Занятие

Часть 1

Часть 2

СУБД: список литературы

Основной книгой курса является К. Дейт "Введение в системы баз данных" Кроме того, использовались материалы из этих книг:

• Д. Кренке "Теория и практика построения баз данных"
• Б. Новиков, Г. Домбровская "Настройка приложений баз данных"
• J.Ullman, J.Widom, H.Garcia-Molina "Database System Implementation"
• Г. Гарсиа-Молина, Дж. Ульман, Дж. Видом "Системы баз данных. Полный курс"

Можно использовать любую другую разумную литературу. Книги типа "освой MySQL за 24 часа" или "Oracle для чайников" разумной литературой не считаются. Одним из признаков, по которым можно отличить разумную литературу, является наличие в книге большого раздела, посвящённого моделям данных.

Новый учебный год!

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

Парочка анонсов.

Не поленюсь попиарить парочку фиговин.

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

Небезызвестный Юрий Лившиц организует Hack Day -- мероприятие, на котором в течении дня сколоченные наспех команды со страшной силой вкалывают, чтоб воплотить какую-нибудь свою давнишнюю мечту в работающий прототип. Не знаю, что получится у организаторов hack day, но вообще встречи в таком формате (хакафоны)  довольно популярны (в том числе и в гугле) и приносят кое-какие плоды. Hack day будет 5-6 сентября -- это практически завтра, торопитесь.

Я ненавижу твой говнокод и тебя лично.

Инспекции кода (code reviews) -- отличный способ повысить качество разрабатываемого кода. В оригинальной статье "Your code sucks and I hate you" и в её переводе можно почитать о некоторых тонкостях проведения инспекций.

В Google инспектируется любое изменение до попадания в систему контроля версий, неважно, написал ли его интерн или Jeff Dean. Это работает. На моей памяти несколько неприятных багов было отловлено во время code review, не говоря уж о многочисленнх исправлениях стиля кодирования и полезных улучшений, не влияющих на логику программы. Разумеется, code review -- не панацея. Многие ошибки прорываются сквозь code review, и нужны и другие средства по борьбе с ними (в первую очередь unit тесты).

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

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

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

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

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

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

Видеозаписи сессий Google I/O

На прошедшей на прошлой неделе в Сан-Франциско конференции Google I/O было много интересных презентаций и лекций. Сейчас начали появляться видеозаписи -- рекомендую смотреть. Из имеющихся на данный момент, на мой взгляд, интересны записи с сессий про Wave. Эта штука впечатляет и как продукт, и как открытая  платформа для написания интересных средств коммуникации.

Обновление 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 машины

Кустарный поисковик на Ruby

Желающим состряпать на коленках маленький, но гордый поисковичок на модном языке Ruby -- слайды в помощь.

http://www.scribd.com/doc/15008618/Building-a-MiniGoogle-HighPerformance-Computing-in-Ruby

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

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

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

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

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

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

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

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

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

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

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

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

Итератор (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!

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

Хотите послушать стенфордский курс лекций по 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());

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

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

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

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

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

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

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

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