Подходит к концу очередной год

Подходит к концу очередной год. Этот год очень сильно отличался от всех предыдущих.

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

В мае я пришёл на работу в московский офис компании Яндекс. Год я закончил именно в этой компании.

В июле я поступил в Школу анализа данных. Поступление доставило мне определённое удовольствие, поскольку пришлось отстаивать свою позицию в споре с очень умным человеком.

В сентябре была поездка в Воронеж, где я принял участие в RuSSIR-2010 и конференции молодых учёных. Там, вместе с Сергеем Пупыревым, мы опубликовали свою работу о прогнозировании величины транспортного потока. Работа эта была написана по следам участия в конкурсе Интернет-математика проходившего в апреле и первой половине мая.

Сейчас я вспоминаю эту конференцию лишь отрывками. Запомнились: вечер в течение которого было много дружеских разговоров про книги и информационный поиск; ночь, в течение которой мы делали макет плаката для выступления; и участие в конкурсе, где я на мгновение увидил образ своей Любаши. Именно её я нарисовал, и зал был впечатлён.

С сентября до середины декабря была работа в Яндексе и учёба в Школе анализа данных.

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

Деревья поиска

Заинтересовался следующим вопросом: какая структура данных лучше всего подходит для хранения статуса в алгоритме заметающей линии. Естественным выбором были деревья поиска, вот только какие?

Нашёл следующие структуры:

1. B-tree
2. Red-black tree
3. AVL tree
4. Cartesian tree
5. Splay tree
6. AA tree
7. 2-3 tree

Отдельный интересные вопрос: какие из этих деревьев можно реализовать как intrusive?

Требования к смартфону

1. Хорошая телефонная книга
   • Длинные имена и фамилии
   • Несколько телефонных номеров на один контакт
   • Возможность хранить телефонную книгу только локально
2. Телефонные звонки
   • Захват голоса в шумной среде
   • Возможность записывать звонки
   • История всех звонков
3. Короткие сообщения
   • Быстрый поиск в сообщениях
   • История всех сообщений
4. Почта
   • Протокол imap
   • Поддержка GMail (в том числе на собственном домене)
   • Быстрый поиск в сообщениях
5. Менеджер задач
6. Просмотр документов: PDF, djvu, fb2, txt
7. Поддержка национальных символов
8. WiFi
9. Время автономной работы не менее 24 часов
10. Вес не более 130 грамм
11. Клиент для Skype
12. Клиент для Sip
13. Клиент для Atom/RSS
14. Клиент для Twitter
15. Multitouch (не менее двух честных точек)
16. Фонарик

FWD: Астрономия в школах

http://pphantom.livejournal.com/17873.html

Числа, которые полезно знать

Обращение к кэшу L1	0.5 нс
Ошибка при предсказании условного перехода	5 нс
Обращение к кэшу L2	7 нс
Открытие/закрытие мьютекса	25 нс
Обращение к памяти	100 нс
Сжатие 1 Кб быстрым алгоритмом	3,000 нс
Пересылка 2Кб по сети со скоростью 1 Гб/с	20,000 нс
Чтение 1 Мб последовательно из главной памяти	250,000 нс
Передача сообщения туда/обратно в одном дата-центре	500,000 нс
Произвольный доступ к жёсткому диску	10,000,000 нс
Чтение 1 Мб последовательно с жёсткого диска	20,000,000 нс
Передача пакета из Калифорнии в Нидерланды и обратно	150,000,000 нс

Первоисточник: Google: Designs, Lessons and Advice from Building Large Distributed Systems

Перешёл на rxvt-unicode

Мне очень нравится настройки gnome-terminal в ubuntu. Но сам эмулятор терминал мне не очень нравится. Решил мигрировать на rxvt-unicode.

Пересобрал последнюю версию из репозатория:

$ cvs -z3 -d :pserver:anonymous@cvs.schmorp.de/schmorpforge co rxvt-unicode
$ cd rxvt-unicode
$ ./configure ./configure --enable-everything --prefix=$HOME/slash
$ make -j7 install

Прописал следующие настроки:

!! ~/.Xdefaults

!! Terminal name
!! FIXME: Enabled bold font for Midnight commander 
URxvt*termName: rxvt

!! Minor setups
URxvt*scrollBar: False
URxvt*saveLines: 10000

!! Select fonts
URxvt*font: xft:Monospace:size=10:style=regular:antialias=True:hinting=True
URxvt*boldFont: xft:Monospace:size=10:style=bold:antialias=True:hinting=True
URxvt*letterSpace: -2

!! Foreground and background colours
URxvt*background: #FFFFDD
URxvt*foreground: #000000

!! Colour palette schema: Tango
URxvt.color0  : #000000
URxvt.color8  : #555753

URxvt.color1  : #CC0000
URxvt.color9  : #EF2929

URxvt.color2  : #4E9A06
URxvt.color10 : #8AE234

URxvt.color3  : #C4A000
URxvt.color11 : #FCE94F

URxvt.color4  : #3465A4
URxvt.color12 : #729FCF

URxvt.color5  : #75507B
URxvt.color13 : #AD7FA8

URxvt.color6  : #06989A
URxvt.color14 : #34E2E2

URxvt.color7  : #D3D7CF
URxvt.color15 : #EEEEEC

Пока нравится ;)

Появился клиент skype под android

Из книги "Вы, конечно, шутите, мистер Фейнман!"

Главный принцип (науки, примечание моё) -- вы не должны обманывать себя. Обмануть себя проще всего. Поэтому вы должны быть очень осторожными. И когда вы не обманываете себя, то становится легко не обманывать других учёных. Для этого уже достаточно обычной частности.

The first principle is that you must not fool yourself -- and you are easiest person to fool. So you have to be very careful about that. After you've not fooled yourself, it's easy not to fool other scientists. You just have to be honest in a conventional way after that.

Алгоритм приближённого вычисления квадратного корня

#ifndef __fast_inv_sqrt_h__
#define __fast_inv_sqrt_h__

#include <cassert>
#include <stdint.h>


/**
 * Fast approximation of the inverse square root
 *  (http://en.wikipedia.org/wiki/Fast_inverse_square_root)
 *
 * @param x
 *             32-bit floating point (IEEE 754-2008)
 * @return the approximated inverse square root of x
 */
inline float InvSqrt(float x) {
    assert( sizeof(x) == 4 );
    assert( x >= 0 );

    union {
        uint32_t i;
        float y;
    };

    y = x;
    i = 0x5f375a86 - (i >> 1);
                 /* Approximation step */

    return y * (1.5f - 0.5f * x * y * y);
                 /* One step more of the Newton's method */
}

#endif /*_fast_inv_sqrt_h__*/

Об уязвимостях в приложениях

Виды уязвимостей приложений:

• Уязвимости в правах доступа к приложению
• Уязвимости в коде форматирования строк
• Уязвимости при работе с общими ресурсами
• Ошибки при вычислении размеров буферов
• Ошибки в работе приложения при исчерпании внешних ресурсов или динамической памяти
• Ошибки в работе приложения с внешними ресурсами или динамической памятью

Факторы усиливающие уязвимости:

• Фиксированное расположение (layout) программы в памяти
• Избыточные права доступа у приложения

Цели атак:

• Внедрение новой функции в приложение
• Нарушение работы приложения
• Получение информации из приложения
• Атака или подготовка атаки на иное приложение

Как правило, чтобы получить управление в коде приложения:

• Перезаписывают стек
• Перезаписывают управляющие секции

Требования к системному языку программирования

(навеяно http://apenwarr.ca/log/?m=201007#21)

1. Реализация любой идеи на новом языке должна быть не сложнее её реализации на языке C
2. Должная быть возможность напрямую вызывать подпрограммы на C и ASM
3. Должны быть детерминированные конструкторы и деструкторы (RAII)
4. Нужна поддержка таблиц виртуальных методов
5. Не должно быть отдельных заголовочных файлах (import вместо include)
6. Не должно быть динамической типизации
7. Не должно быть встроенного в язык сборщика мусора
8. Не должно быть встроенной в язык системы нитей исполнения
9. Не должно быть намертво встроенной в язык стандартной библиотеки
10. Исключения: либо управляемые, либо отсутствуют
11. Сложные типы должны всегда передоваться внутрь функции по ссылке
12. Синтаксис работы с указателями должен быть таким же как и синтаксис работы со ссылками
13. Нужна поддержка преобразований типов (type casting) определяемых пользователями
14. Нужна поддержка обобщенных типов
15. Нужна поддержка анонимных функций
16. Нужна поддержка перегрузки операторов

О сочетаниях цветов

Код на jscript для проверки сочетания цветов на ``читабельность'':

function color_brightness(red, green, blue) {
    return 0.299 * red + 0.587 * green + 0.114 * blue;
}

function color_is_good(bg_red, bg_green, bg_blue,
                       fg_red, fg_green, fg_blue) {
    var brightness_diff = Math.abs(
        color_brightness(bg_red, bg_green, bg_blue) -
        color_brightness(fg_red, fg_green, fg_blue));
    var color_dirr =
        Math.abs(bg_red - fg_red) +
        Math.abs(bg_green - fg_green) +
        Math.abs(bg_blue - fg_blue);
    return (brightness_diff > 0.490 && color_dirr > 1.961);
}

Задача на "правильную" запись

Дано множество:
и определена функция:

Определим следующее множество:

Для того, чтобы на этом множестве выполнялось следующее условие:

необходимо и достаточно, чтобы


Предполагается, что если эти утверждения переписать "правильно", то можно увидеть что-то!

Установка vim в ubuntu

После установки следующих пакетов у меня заработал vim в ubuntu:
vim vim-scripts vim-doc vim-latexsuite vim-gui-common vim-gnome

Классификация нестандартных ситуаций

1. Является ли ситуация допустимой?

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

Пример, в нормальных условиях следующее предположение верно:
assert( 2+2 == 4 );

Другой пример, если подпрограмма, считающая для любой квадратной матрицы обратную, получит на вход сингулярную матрицу, такая ситуация будет нестандартной, но вполне ожидаемой (допустимой).

2. Возможен ли преодолеть нестандартную ситуацию?

Для некоторых нестандартных ситуаций возможен возврат к нормальной работе программы. Одна и та же нестандартная ситуация может быть как преодолимой, так и непреодолимой на разных уровнях абстракции.

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

Ещё пример, если на уровне операций с файлами программа обнаружила непреодолимую ошибку, то на другом уровне программа может отключить функцию работы с файлами и продолжить работу.

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