Блог о математике, программировании, алгоритмах. И немного о работе операционной системы Linux.

среда, 11 мая 2011 г.

Булевы функции. Хозяйке на заметку.

Бинарных булевых функций существует 16.










0 0 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0










0 0 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Причем только 10 из них являются по настоящему бинарными. 0 и 1 — нульарные функции. Скролько бы переменных мы в них не предполагали, они все будут не существенными. Функции , , а также их отрицания являются функциями одной переменной.
Перечислим те из приведенных выше операций, которые являются ассоциативными. То есть:
  1. Конъюнкция (логическое И):
  2. Дизъюнкиця (логическое ИЛИ):
  3. Исключающее ИЛИ:
  4. Эквивалентность:
Перечислим те из них, которые являются коммутативными: Заметим, что для того, чтобы операция была коммутативной, достаточно, чтобы значения для этой операции во второй и третьей строках совпадали. Таких операций будет 6.
  1. Стрелка Пирса:
  2. Исключающее ИЛИ (сложение по модулю 2):
  3. Штрих Шеффера:
  4. Конъюнкция (логическое И):
  5. Эквивалентность:
  6. Дизъюнкиця (логическое ИЛИ):

суббота, 19 марта 2011 г.

Язык Vala

Давненько я сюда ничего не писал. Поэтому расскажу о том, как опробовал новый для меня язык программирования Vala. Язык Vala работает с системой объектов GLib и создан для разработки прикладных и системных приложений для GNOME. Являясь языком высокого уровня (по сравнению с C :), и будучи компилируемым в C код, использующий стандартный GLib, он одновременно содержит бинарную совместимость с другими приложениями для GNOME и «удобства» таких языков как C# или Java.
Для того, чтобы установить компилятор языка в мою Ubuntu 10.10, я сказал:
sudo apt-get install valac
Затем, я создал файл first.vala и открыл его редактором Geany. Так как я не писал ещё на этом языке, мне нужен был экзампл, который я радостно слямзил из википедии. Надо отметить, что Geany сама поняла, каким компилятором ей нужно собирать этот текст, так что простого нажатия F9 хватило, чтобы я получил рабочее приложение. Постить сюда код из википедии негоже, поэтому я несколько видоизменил исходную программу. Теперь она считает 10-ое число Фибоначчи (хотел проверить есть ли рекурсия). Полезно, не правда ли? :-)
using GLib;
 
class Sample : Object 
{
    static int main (string[] args)
    {
        var my_sample = new MySamlpe ();
        var i = my_sample.fibonacci(10);
        stdout.printf("I is %d\n", i);
        return 0;
    }
}

class MySamlpe : Object
{
    public int fibonacci(int i)
    {
        if (i < 0) {
            stdout.printf ("I cann't! I just cann't");
            return -1;
        }
        if (i == 1) {
            return 1;
        }
        return (i + fibonacci(i - 1));
    }
}
Скомпилировал и запустил:
numlock@oligochaeta:~/temp/exp$ ./first 
I is 55
Вуаля!
На все вместе ушло около 20 минут и ни в какие туториалы я не заглядывал. Так что все очень просто. Кстати, среда Unity, которая будет средой по умолчанию в Ubuntu 11.04 частично написана на Vala.

понедельник, 20 декабря 2010 г.

Корень n-ой степени из числа

Для вычисления корня n-ой степени из какого-либо действительного числа x достаточно вот таких простых преобразований:
Т.е. на языке, скажем C++, это будет выглядеть так:
double res = exp((1/n) * log(x));

Сбалансированность дерева

Иногда (при работе с деревьями очень часто) бывает нужно понять, насколько дерево сбалансированно. Проблема в том, что эта характеристика более-менее понятна в отношении бинарных деревьев (для них она равна отношению мощности левого и правого поддеревьев), а для «обычных» деревьев, в общем-то, не понятно, что на
что делить.

Итак, пусть T — «обычное» ориентированное дерево, и из каждой вершины может исходить n ребер. В зависимоти от задачи, можно считать сбалансированность разными способами:

Если n четно, тогда сбалансированность можно считать по следующей формуле:
 
где — мощность поддерева, с корнем в j-той вершине данного дерева. Нумерация здесь соответсвует обходу в ширину, а корень дерева имеет нулевой индекс. То есть, мы берем все ребра исходящие из корня дерева и делим это множество на два. Ссуммируем мощность подмножеств, которые начинаются с вершин, в которые входят эти ребра, и делим одну сумму на другую.
Если n нечетно, тогда формула видоизменяется следующим образом:
Смысл формулы здесь не изменился, но мы учитываем также половину мощности «центрального» поддерева и в делимом и в делителе.

Также сбалансированностью можно считать следующую величину:
где — мощность множества уровней дерева, которые содержат листья, а — количество уровней всего.

пятница, 17 декабря 2010 г.

Генерация случайного разбиения

У Кнута в 4-ой части Искусства программирования есть описание алгоритма генерации всех разбиений n-элементного множества на m-частей (раздел 7.2.1.4). Положим, что нам нужно найти какое-нибудь случайное разбиение (например, мне это понадобилось для генерации случайного дерева заданной несбалансированности). Конечно, мы будем использовать случайные числа.
Смысл следующий: берем массив из m элементов и заполняем его случайными числами в диапазоне от 0 до n. Последнему элементу присваиваем значение n. Мы получили массив, в котором содержатся "метки" — значения указывающие на то, в каком именно месте будет разбито наше множество.
Затем сортируем массив, последовательно начиная с m-1-ого элемента находим разность между i-м и i-1-м элементами и записываем её в i-ую ячейку массива. Нулевой элемент массива оставляем без изменений.
Проблема в том, что этот алгоритм не гарантирует, что в результирующем массиве не будут отсутствовать нулевые элементы. С этим можно бороться последующей балансировкой. Заводим специальную переменную (например, diff) для сохранения количества "балансировок" и пока эта переменная не станет равна нулю ходим по массиву и совершаем следующие действия:
  1. Если наткнулись на ячейку содержащую ноль, прибавляем к её значению единицу, а из переменной единицу вычитаем.
  2. Если diff меньше нуля, а текущий элемент массива больше нуля, то прибавляем diff единицу, а из текущего элемента её вычитаем.
Вот как это выглядит у меня:
void
getPartition(unsigned n, unsigned m)
{
    if (n < m) {
        throw out_of_range("N must be greater then M");
    }
    unsigned sum = 0;
    vector< unsigned > partition;
    partition.resize(m);
    // заполнение массива случайными значениями
    for (unsigned i = 0; i < m; i++) {
        partition[i] = rand() % n;
    }
    partition[partition.size() - 1] = n;
    // сортировка
    sort(partition.begin(), partition.end());
    // вычитаение
    for (unsigned i = m - 1; i > 0; i--) {
        partition[i] = partition[i] - partition[i - 1];
    }
    int diff = 0;
    // балансировка
    do {
        for (unsigned i = 0; i < m; i++) {
            if (partition[i] < 1) {
                partition[i]++;
                diff--;
            }
            if (diff < 0) {
                if (partition[i] > 1) {
                    partition[i]--;
                    diff++;
                }
            }
        }
    } while (diff != 0);
    // вывод на экран вместе с суммой всех элементов для проверки
    for (unsigned i = m - 1; i > 0; i--) {
        cout << partition[i] << " ";
        sum += partition[i];
    }
    sum += partition[0];
    cout << partition[0] << " " << sum;
    cout << endl;
}

среда, 15 декабря 2010 г.

Tips & Tricks #2. Удаленный рабочий стол Ubuntu 10.04 по RDP.

Однажды у меня возникла необходимость подключиться стандартным "Удаленным рабочим столом" Windows к Ubuntu-машине. Сама Windows использует для этих целей протокол RDP, серверная часть которого в *nix-системах представлена продуктом xrdp.
Итак, для начала, устанавливаем сам xrdp:
sudo apt-get install xrdp
После этого, мы уже можем подключаться к нашему серверу, но по-умолчанию используется протокол VNC. С этим видом подключения у меня возникли проблемы переключения раскладок клавиатуры (по умолчанию удаленная сессия видела только одну раскладку en_US). Настроить переключение удалось только с бубном и через IBus, а не через xkb. К тому же подключение более чем 5 машин вешало сеть. Я решил по-пробовать rdp.
Оказалось, что для этого требуется бинарник x11rdp, который в стандартный пакет не входит. Гугл сказал мне, что исходники можно взять здесь:
svn://server1.xrdp.org/srv/svn/repos/main/x11rdp_xorg71
Итак, качаем исходник куда-нибудь, а потом собираем.
cd ~/
mkdir temp
cd temp
svn co svn://server1.xrdp.org/srv/svn/repos/main/x11rdp_xorg71
cd x11rdp_xorg71
sudo mkdir /opt/x11
sudo ./buildx.sh /opt/x11
В последней строчке мы сказали собирающему скрипту, чтобы он положил все собранное в каталог /opt/x11. У меня во время сборки скрипт вывалился с ошибкой и пожаловался, что нет библиотеки zlib. Ставим:
sudo apt-get install zlib1g-dev
и запускаем скрипт заново. Он не будет повторять ту работу, что уже сделал.
После сборки идем в каталог /opt/x11/bin, и просто копируем оттуда файл x11rdp в каталог /usr/bin.
Для того, чтобы подключение через x11rdp было подключением по-умолчанию идем в каталог /etc/xrdp и в файле xrdp.ini помещаем блок настроек [xrdp6] перед блоком [xrdp1]. Все, теперь можно подключаться к нашей Ubuntu-машине, с помощью стандартного клиента Windows.

P.S. Если пользователь ни разу не логинился непосредственно на сервер (например, если это доменный пользователь), то ему также придется добавить русскую раскладку клавиатуры и настроить сочетание клавиш для переключения. Все это можно сделать через Система->Параметры->Клавиатура.

четверг, 11 ноября 2010 г.

Генерация случайного дерева

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

В качестве структуры данных, для хранения была выбрана матрица смежности. Будем считать, что дерево — ориентированный граф с полустепенью захода у каждой вершины равной 1 (кроме корня: у него 0). Также нам нужно сделать так, чтобы у нас был всего один корень (то есть нам нужно именно дерево, а не лес).
Матрица смежности — это булева матрица, в (i, j) вершине которого содержится информация о том, присутствует ли в графе ребро изходящее из i и входящее в j. Из этого легко получить условия, которые мы должны наложить на матрицу, чтобы она описывала именно дерево.
  1. В столбце i (i > 0) должна стоять одна и только одна единица на месте j (j < i). Таким образом мы обеспечим полустепень захода равную 1 для всех вершин графа, кроме корня. Будем, для удобства считать, что корнем является нулевая вершина.
  2. Ниже главной диагонали (и на ней) должны стоять нули, это обеспечит ориентированность дерева, и тот факт, что вершины с большим номером будут являтся детьми, только вершинам с меньшим номером.
Ниже я привожу небольшу программку для примера, генерирующую случайное дерево и выводящую результат в dot-cовместимом формате.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

int
main(int argc, char** argv)
{
    using namespace std;
    srand(time(NULL));
    vector<vector<int> > matrix;
    #define size 1000
    matrix.resize(size);
    for (int i = 0; i < size; i++) {
        matrix[i].resize(size);
        for (int j = 0; j < size; j++) {
            matrix[i][j] = 0;
        }
    }
    for (int i = size - 1; i > 0; i--) {
        /**
         * (rand() % i) - случайное число в множестве [0, i)
         * i-тый столбец
         */
        matrix[rand() % i][i] = 1;
    }
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (matrix[i][j] == 1) {
                cout << i << " -> " << j << ";" << endl;
            }
        }
    }
}
И на закуску небольшой пример:
0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
Дерево, представленное этой матрицей будет выглядеть так:
Обратите внимание, что четвертая и пятая строки в матрице содержат только нули. На графе они стали листьями. Столбец содержащий одни нули (1-ый) является корнем.