Готтентотская мораль

Готтентотская мораль <былина>

Однажды, один христианский миссионер спросил готтентота:
— >Что такое зло?>
— >Это когда сосед украл у меня барана>, — ответил тот.
— >Ну хорошо, а что же такое добро?>
— >Это когда я украл у соседа барана…>

>Нравственные устои африканского народа кой-коин таковы: если я украл у соседа козу – это доблесть, достойная восхищения; если же сосед украл козу у меня – это подлый поступок, за который соседа надлежит осудить и наказать.>

Неизвестный миссионер XIX века.

Тэги: <мораль, притча, былина, племя готтентотов, готтентот>

Список свободных прокси-серверов для анонимности в Интернете

Список свободных прокси-серверов для анонимности в Интернете

Актуальные списки proxy серверов можно бесплатно взять:
1. socks — sockslist.net,
2. HTTP proxy — proxyhttp.net.

Мой список прокси-серверов

IP Порт Страна Тип Время отклика [секунд]
193.160.225.13 8081 Украина (UA) HTTPS 1.07
186.190.238.65 8080 Чили (CL) HTTPS 2.32
195.138.83.32 81 Украина (UA) HTTPS 2.81
84.50.44.92 3128 Эстония (EE) HTTPS 2.89
178.19.98.173 443 Польша (PL) HTTPS 8.16

Источник: http://foxtools.ru/Proxy

Время отклика сервера можно узнать с помощью команды:

# Время отклика сервера для HTTP proxy
time curl --proxy 193.160.225.13:8081 check-host.net/ip

# Время отклика сервера для socks4
curl --socks4 193.160.225.13:8081 check-host.net/ip

# Время отклика сервера для socks5
curl --socks5 193.160.225.13:8081 check-host.net/ip

Тэги: <web, internet, интернет, анонимность, прокси-сервер, proxy server, Interreto>

Создание динамического массива на C

Создание динамического массива на C

Функция malloc() возвращает указатель на первый байт области памяти размером size, которая была выделена из динамически распределяемой области памяти. Если для удовлетворения запроса в динамически распределяемой области памяти нет достаточного объема памяти, возвращается нулевой указатель. Перед попыткой использовать выделенную память всегда проверяйте, что возвращаемое значение не является нулевым указателем. Попытка использовать нулевой указатель обычно приводит к полному отказу системы.

#include <stdlib.h>    // для функции malloc() и free()
#include <stdio.h>
#include <string.h>

int main()
{
const int STR_LEN_MAX = 100; // константа для максимальной длины строки
	
int n;
int i;
char** pp_str;
char str[STR_LEN_MAX];

scanf("%d", &n); // Вводится количество строк

pp_str = (char**) malloc(n * sizeof(char*)); // Создается массив указателей типа char* из динамической памяти

if(pp_str == NULL) // проверка наличия свободного места в динамической памяти, и выход если проверка провалилась
	{
    printf("Ошибка при распределении памяти\n");
    exit(1);
	}


for(i = 0; i < n; i++) // цикл для заполнения матрицы строками
	{
	scanf("%s", str); // читаем из стандартного входа текущую строку
	
	pp_str[i] = (char*) malloc((strlen(str) + 1) * sizeof(char)); // и выделяем под строку динамическую память для хранения
	
	if(pp_str[i] == NULL) // проверка наличия свободного места в динамической памяти, и выход если проверка провалилась
		{
		printf("Ошибка при распределении памяти\n");
		exit(1);
		}
	
	strcpy(pp_str[i], str);
	}

for(i = 0; i < n; i++) // цикл для вывода введенной матрицы строк в стандартный поток вывода
	{
	printf("%d. %s\n",i+1, pp_str[i]); 
	}

for(i = 0; i < n; i++) // освобождение каждой строки матрицы из динамической памяти
	{
	free(pp_str[i]); 
	}
free(pp_str); // удаление самой матрицы из динамической памяти


return 0;
}
#include <stdlib.h>    // для функции malloc() и free()
#include <stdio.h>

int main()
{	
int n, m;
int i, j;
double** matrico;

printf("Введите количество строк в матрице:\n");
scanf("%d", &n); // Вводится количество строк в матрице

printf("Введите количество столбцов в матрице:\n");
scanf("%d", &m); // Вводится количество столбцов в матрице

matrico = (double**) malloc(n * sizeof(double*)); // Создается массив указателей типа double* из динамической памяти

if(matrico == NULL) // проверка наличия свободного места в динамической памяти, и выход если проверка провалилась
	{
    printf("Ошибка при распределении памяти\n");
    exit(1);
	}


for(i = 0; i < n; i++) // цикл для заполнения матрицы строками
	{
	matrico[i] = (double*) malloc(m * sizeof(double)); // Выделяем под каждую строку матрицы m ячеек типа double из динамической памяти
	
	if(matrico[i] == NULL) // проверка наличия свободного места в динамической памяти, и выход если проверка провалилась
		{
		printf("Ошибка при распределении памяти\n");
		exit(1);
		}
	
	for(j = 0; j < m; j++)
		{
		printf("Введите значение ячейки [%d,%d] [строка, столбец] в матрице:\n", i, j);
		scanf("%lf", &matrico[i][j]); // Вводится значение ячейки [i,j] в матрице
		}
	}

for(i = 0; i < n; i++) // цикл для вывода введенной матрицы строк в стандартный поток вывода
	{
	for(j = 0; j < m; j++)
		printf("%lf ", matrico[i][j]);
	printf("\n");
	}

for(i = 0; i < n; i++) // освобождение каждой строки матрицы из динамической памяти
	{
	free(matrico[i]); 
	}
free(matrico); // удаление самой матрицы из динамической памяти


return 0;
}

Тэги: <программирование, программа, C, динамическая память, массив, programado, programo, masivo, matrico>

Чайный гриб

Чайный гриб

Уход за чайным грибом

Для работы и роста чайного гриба необходимо создать питательный раствор из черного или зеленого чая с сахарным песком:
25 — 125 грамм сахара на 1 литр воды [1 - 5 столовые ложки],
10 — 15 грамм заварки чая на 1 литр воды [2 - 3 чайные ложки].

Не рекомендуется при приготовлении питательного раствора для чайного гриба использовать эфиромасличные растения [растения, содержащие много эфирных масел см. список WikiPedia.org "Эфирные масла. Растения — сырьё для производства Эфирных Масел"]:

Ажгон, семена
Аир, корень
Альпиния, корень
Амирис, древесина
Анис, плоды
Апельсин, цедра
Арника, цветы, корни
Базилик, листья, верхние части стеблей с цветами
Бальзамовое дерево Толу, застывший бальзам, собираемый с деревьев
Бархатцы (Тагетес), цветущие растения, наземная часть растения
Бензоин, смола
Бергамот, кожура
Береза белая, почки, листья, ветки
Береза вишневая, кора
Бессмертник, цветущие верхушки растения
Боб Тонка, бобы
Болдо, листья
Борнеол, древесина
Борония, цветы
Бучу, сухие листья
Валериана, корни и корневища в весенний период вегетации
Ваниль, плоды
Вербена лимонная, наземная часть
Ветивер, корни
Восковница, листья
Гардения жасминовая, цветки
Гваяковое дерево, древесина
Гвоздика, почки, листья, цветки, ветки
Герань розовая, все растение (Гераниевое масло)
Гиацинт, цветы
Гибискус, семена
Грейпфрут, кожура
Грушанка, листья
Горчица, семена
Девясил высокий, сухие корни
Девясил душистый, корни, цветущая часть
Донник, сухие цветы
Дубовый мох, все растение
Душица обыкновенная, цветы
Душица испанская, цветы
Дягиль, корень
Ель, хвоя
Жасмин, цветы
Живица, сырой экссудат
Иланг-иланг, свежие цветки
Иллициум настоящий, плоды, листья
Имбирь, корень
Ирис, корень
Иссоп, цветки, листья
Календула лекарственная, цветки
Камфора, древесина, кора
Кананга, цветы
Кардамон, семена
Кассия, цветы
Каяпут, листья, ветки
Кедр, древесина
Кервель, семена
Кипарис, хвоя, побеги, шишки
Клиноног, цветущая верхняя часть растения
Кмин тминовый, семена
Копаифера лекарственная, ствол дерева
Копытень канадский, сухие корни
Кориандр, размолотые семена
Корица, кора, листья
Костус, корни
Критмум морской, цветы и плоды с небольшим количеством листьев
Кротон, кора
Куркума длинная, корни
Лаванда, все растение (Lavandula vera)
Лаванда хлопковая, семена
Лавр американский, листья
Лавр благородный, сухие листья и ветки
Ладан, смола дерева
Ладанная камедь, смола, листья и ветки
Лайм, Весь плод или незрелая кожица
Левзея, плоды
Лиатрис пахучая, листья
Литцея, плоды
Лимон, свежая корка
Лимонная трава, сухая трава
Лимонник китайский, все растение
Линалоэ, семена, листья, побеги, древесина
Липа обыкновенная, цветки
Лиственница сибирская, хвоя, живица
Лотос, цветы
Лук репчатый, луковица
Любисток лекарственный, корни, листья, семена
Майоран сладкий, сухие цветы и листья
Мандарин, кожура
Манука, листья, ветки
Марь, наземная часть, семена
Мелисса, верхушки стеблей с цветами
Метельник прутьевидный, цветы
Мимоза, цветы
Миндаль горький, плоды
Мирокарпус, древесина
Мироксилон, бальзам, древесина, плоды
Мирра, смола или зеленые части растения
Мирт, листья, ветки
Можжевельник, ягоды (шишкоягоды); древесные отходы, опилки
Морковь, семена
Мускатный орех, семена; оболочка семян
Мята колосистая, листья, цветущие верхушки
Мята перечная, листья, цветущие верхушки
Найоли, листья
Нард, корни
Нарцисс, цветки
Нероли, цветы
Пальмароза, свежая или сухая трава
Пачули, Высушенные листья и трава
Перец черный, семена
Петитгрейн, листья, побеги
Петрушка огородная, семена и свежие листья, побеги (иногда корни)
Пижма, наземная часть
Пихта, хвоя, шишки, молодые ветки
Полынь горькая, цветы, листья
Полынь обыкновенная, цветы, листья
Равинтсара, листья
Роза, цветки Rosa damascena и др. виды
Розмарин, цветущая верхушка или все растение
Розовое дерево, ствол
Ромашка голубая, соцветия
Ромашка марокканская, цветки и трава
Ромашка римская, цветы
Рута душистая, все растение
Сандал, Корни и древесная сердцевина
Саро, свежие листья
Сассафрас, кора
Сельдерей, семена, листья
Смолоносица, корни, наземная часть растения
Сосна канадская, хвоя
Сосна обыкновенная, хвоя, молодые ветки
Стиракс, выделения из под коры
Танжерин, кожура
Тимьян, цветущая надземная часть
Тмин, зрелые плоды (семена)
Тубероза, свежие бутоны
Туя, листья, побеги и кора
Тысячелистник, сухая трава
Укроп огородный, семена, листья, стебли
Фенхель, размельченные семена
Ферула, млечный сок
Фиалка душистая, листья, цветы
Фисташка мастиковая, живица, листья
Хмель обыкновенный, шишки
Хо-дерево, листья и молодые побеги
Хрен, корни
Цитронелла, трава
Чабер горный, высушенная трава
Чабер садовый, все растение
Чайное дерево, листья
Чеснок полевой, луковицы
Шалфей лекарственный, соцветия в момент цветения
Шалфей мускатный, высушенное растение
Эвкалипт, листья Eucaliptus globulis и др. видов
Элеми, смола
Эстрагон, наземная часть
Яборанди, листья

Результат переработки чайным грибом эфирного масла неизвестен и как следствие может быть опасен для здоровья.

Тэги: [чайный гриб]

Шифрование файлов в FreeBSD

Шифрование файлов в FreeBSD

Шифрование по алгоритму AES с помощью OpenSSL

Для шифрования/расшифрования файла в FreeBSD можно свободно воспользоваться пакеджем OpenSSL. В приведенных примерах для шифрования будет использоваться алгоритм AES с шифроключем длинной 256 бит.

Зашифровать файл:

$ openssl enc -e -aes-256-cbc -salt -in имя_файла -out имя_файла.enc

Примечание:
Для ввода пароля в командной строке можно использовать ключ «-k» ["openssl enc -e -aes-256-cbc -salt -k "пароль" -in имя_файла -out имя_файла.enc"].
Для увеличения криптостойкости алгоритма шифрования используется ключ «-salt» для примешивания случайной «соли», данный ключ включен по умолчанию.

Расшифровать файл:

$ openssl enc -e -aes-256-cbc -in имя_файла.enc -out имя_файла

Для шифрования/расшифрования директорий в FreeBSD сперва необходимо заархивировать её в «*.tar.bz2″.

Зашифровать директорию:

$ tar -cvjf имя_архива.tar.bz2 </путь/к/папке>
$ openssl enc -e -aes-256-cbc -salt -in имя_архива.tar.bz2 -out имя_файла.tar.bz2.enc

Расшифровать директорию:

$ openssl enc -e -aes-256-cbc -in имя_файла.tar.bz2.enc -out имя_архива.tar.bz2
$ tar -xvjf имя_архива.tar.bz2 -C </путь/к/папке>

Шифрование по алгоритму BlowFish с помощью OpenSSL

Для шифрования/расшифрования файла в FreeBSD по алгоритму BlowFish в режиме CBC нужно выполнить следующие команды.

Зашифровать файл:

$ openssl enc -e -bf-cbc -salt -in имя_файла -out имя_файла.enc.bf_cbc

Расшифровать файл:

$ openssl enc -d -bf-cbc -in имя_файла.enc.bf_cbc -out имя_файла

Быстрая зашифрованная резервная копия [tar, BlowFish]

Зашифровать директорию:

$ tar -cvf имя_архива.tar </путь/к/папке> 
$ openssl enc -e -bf-cbc -salt -in имя_архива.tar -out имя_файла.tar.bf

Расшифровать директорию:

$ openssl enc -d -bf-cbc -in имя_файла.tar.bf -out имя_архива.tar
$ tar -xvf имя_архива.tar -C </путь/к/папке>

Тэги: [FreeBSD, BSD, BlowFish, шифрование, OpenSSL]

Решение Задачи о четырех красках

Решение Задачи о четырех красках

1. Условие

Дано: карта со странами.

Требуется: раскрасить страны в наименьшее количество цветов (красок).

Гипотеза: любую карту можно раскрасить, используя не более 4 (четырех) различных цветов (красок).

Требуется: доказать или опровергнуть данную гипотезу.

2. План доказательства

  1. Условие;
  2. План доказательства;
  3. Формализация условия;
  4. Главная идея доказательства;
  5. Доказательство;

3. Формализация условия

Опр.: Страной называется связанная область (фигура) на плоскости ограниченная не самопересекающимися замкнутыми кривыми, которые называются границами Страны.

Опр.: Границей Страны называется объединение кривых ограничиваемых данную страну.

Примечание: Количество замкнутых кривых, их длина и площадь области (страны) должны быть конечными величинами.

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

Опр.: Картой называется ограниченная не самопересекающимися замкнутыми кривыми связанная область (фигура) на плоскости, с разбиением на неперекрывающиеся (непересекающиеся) области называемые Странами.

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

Примечание (к определению терминов Карта и Страна): Из практических соображений, само понятие страны, равно как и понятие карты в контексте отдельном друг от друга мало применимы. Далее по тексту правильно следщует читать термин страна (или страны) на карте вместо термина страна (или страны) и термин карта со странами вместо термина карта.

Опр.: Соседними Странами на карте называютя Страны, имеющие общий участок границы.

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

Опр.: Раскраской Карты является такая пометка каждой Страны из множества пометок M, такая что любые (или каждые) две соседние страны на карте имеют разные пометки.

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

Опр.: Графом G(V,E) называется совокупность двух конечных множеств — непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E — множество ребер).

Опр.: Если задана функция F: V -> M и/или F: E -> M, то множество M называется множеством Пометок, а граф называется Помеченным (или Нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (рёбра) имеют разные пометки, то граф называется Нумерованным.

4. Главная идея доказательства

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

Проблемы раскраски карты на глобусе и плоскости эквивалентны.
Действительно, в случае карты на сфере можно вырезать кусок внутренней области какой-либо страны; продырявленную сферу можно деформировать (растянуть) в плоскую область — представим, что карта сделана из тонкой резины. На плоской карте отверстие превратится в «океан», омывающий со всех сторон одну страну. Разумеется, длины границ, их форма, размеры стран подвергнутся при растяжении значительным изменениям, но сетка границ останется, добавится лишь растянутая граница прорезанного отверстия, внешняя граница океана. Её можно убрать, то есть раскрасить океан так же, как и окруженную им страну. Такие деформации стран и их границ, очевидно, не меняют задачи раскраски. Ниже рассматривается плоская карта.

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

Опр.: Полным графом с n вершинами (или коротко полным n-графом или n-полным графом) называется такой граф, у которого каждые (или любые) две вершины соединены ребром. Такой граф принято обозначать Kn, где n — количество вершин полного графа.

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

Опр.: Подграфом называется граф G|(V|,E|), где V| ⊆ V и/или E| ⊆ E.

Примечание: Отметим, что в плоском графе не допускаются петли (ребро, имеющие началом и концом одну и ту же вершину).

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

Примечание: На самом деле задача о раскраске плоской карты это всего лишь вершина айсберга задач о раскраске, ведь раскрашивать можно не только плоские фигуры, но и отрезки (ребра графа), и объемные фигуры (тела) и даже n-мерные фигуры. Причем n-мерные фигуры можно раскрашивать на поверхности n+k-мерной фигуры, также как грани в многограннике. Более того, вся сложность данного класса задач о раскраске заключается скорее в определении свойств графов, получаемых при переходе к эквивалентной задачи, то есть непосредственно от карты к графу. На данный момент мы знаем, какие классы подграфов не должен содержать планарный граф, но для более изысканных графов доказательство аналогичное Теореме Понтрягина-Куратовского может быть на порядок сложнее.

Теорема Кёнига о двудольном графе

Формулировка: В графе все циклы четные тогда и только тогда, когда граф является двудольным.

Опр.: Двудольный Граф — это Граф, все вершины которого разбиты на две доли (части или непересекающиеся подмножества множества вершин V V1 V2 которые удовлетворяют условиям: V1 ∩ V2 = ∅ и V1 ∪ V2 = V), а ребра проходят только между вершинами из разных доль.

Опр.: Ребром (или кликой 2) в графе называется подграф K2.

Опр.: Говорят, что в графе вершина инцидентна ребру или наоборот, если данная вершина является подграфом данного ребра.

Опр.: Говорят, что в графе две вершины смежные, если они соеденины ребром.

Опр.: Говорят, что в графе два ребра смежные, если у них есть общая вершина.

Опр.: Маршрутом (путем) в графе называется чередующаяся последовательность вершин и ребер v0,e1,v1,e2,v2, … ,ek,vk, где элементы vi из множества вершин V графа, а ei из множества ребер E графа, в которой любые два соседних элемента Инцидентны.

Опр.: Если v0 = vk, то Маршрут Замкнут, иначе Открыт.

Опр.: Если все ребра различны, то Маршрут называется Цепью.

Опр.: Если все вершины (а значит и ребра) различны, то Маршрут называется Простой Цепью.

Опр.: Замкнутая Цепь называется Циклом.

Опр.: Замкнутая Простая Цепь называется Простым Циклом.

Опр.: Граф без циклов называется Ацикличным.

Опр.: Связанный граф без циклов называется Деревом.

Доказательство теоремы Кёнига

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

Необходимость. Если граф несвязаный, то проведем доказательство отдельно для каждой компоненты. Пусть граф связаный и все циклы в нем четные. Выделим произвольную вершину v0 и найдем произвольные цепи между v0 и всеми остальными вершинами (например, самые короткие алгоритмом Дейкстра). Если одна цепь (v0,vi) нечетной длины, то и любая цепь (v0,vi) нечетная, иначе бы эти цепи образовали нечетный цикл. Аналогично, если (v0,vi) — четная, то и любая (v0,vi) — четная. Разобъем вершины на две доли: в одну войдет вершина v0 и все, находящиеся от v0 на четном расстоянии; в другую долю поместим все вершины, находящиеся от v0 на нечетном расстоянии. Если вершины u1 и u2 принадлежат одной доле, то между ними не может быть ребра, иначе это ребро вместе с цепями (v0,u1) и (v0,u2) образовали бы нечетный цикл. Ч.т.д.

Примечание: Поскольку данная теорема доказана, то можно изменить условие теоремы на равносильное, чтобы показать суть теоремы. Смысл данной теоремы сводится к тому, что для определения двудольности графа необходимо и достаточноопределить двудольность определенных классов подграфов, которые в данном случае являются циклами. То есть если в графе все циклы являются двудольными, то и сам граф тоже является двудольным. Также заметим, что циклы графа вполне однозначно могут быть раскрашены в два цвета при заданной начальной раскраске любого подграфа цикла K2 (полного графа с двумя вершинами), в случае если данный цикл двудольный. Подробнее об эквивалентности задач раскраски и дольности смотреть в Лемме №1 ниже.

5. Доказательство

Опр.: N-дольный Граф — это Граф, все вершины которого разбиты на n доль (частей или непересекающихся подмножест множества вершин V V1,V2, … ,Vn, которые удовлетворяют условиям: Vi ∩ Vj = ∅, 1 ≤ i,j ≤ n, i ≠ j и V1 ∪ V2 ∪ … ∪ Vn = V), а ребра проходят только между вершинами из разных доль.

Лемма №1: Задача раскраски графа в наименьшее количество цветов и задача определения наименьшей дольности графа являются эквивалентными. И действительно, пусть дан граф, у которого наименьшее количество доль равно n, тогда данный граф можно раскрасить в наименьшее количество цветов также равное n (то есть вершины в каждой доли можно раскрасить в один цвет, поскольку они не являются смежными). В противном случае, если раскраска в наименьшее количество цветов возможна, то есть в n-k цветов, где n,k ∈ N, тогда вершины данного графа можно разбить на доли в соответствии с цветами (вершины, раскрашенные в одинаковые цвета можно поместить в одну долю, а в разные цвета соответственно в разные доли). Поскольку вершины, раскрашенные в одинаковые цвета не смежные, то ребер между вершинами в одной доли не будет. И так как количество доль в графе уменьшилось на k, то это будет противоречить начальному условию, что данный граф емеет наименьшее количество доль равное n. В обратную сторону эквивалентность этих задач доказывается также легко, и не стоит пристального внимания.

Во многих случаях решению задачи способствует введение новых терминов. Единственное что необходимо для доказательства теоремы о n-дольном графе это соблюдать аналогию с теоремой Кенига. Как уже было описано выше, в примечании к теореме Кенига, для проверки графа на двудольность было необходимо и достаточно проверить лишь определённые классы подграфов (в теореме Кенига данные классы подграфов являются циклами), которые в случае положительного результата проверки можно однозначно раскрасить в два цвета при заданной начальной раскраске K2 подграфа. И так по аналогии с теоремой Кенига нам необходимо придумать некие классы подграфов после проверки, которых можно будет судить о n-дольности графа в целом. Также можно предположить, что данные классы пдграфов в случае положительного результата проверки на n-дольность будут однозначно раскрашивать в n-цветов и состоять из Kn. Попробуем развить данное предположение в описанной ниже терминологии.

Опр.: Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются Гипердугами, а Граф называется Гиперграфом.

Опр.: Ребром, состоящим из Kn, просто Kn-ребром или Ребром Kn (или кликой n или гипердугой n) в Графе называется подграф Kn.

Опр.: Говорят, что в Графе вершина инциндентна ребру Kn (клика) или наоборот, если данная вершина является подграфом данного ребра Kn.

Опр.: Говорят, что в Графе ребро Kn (клика) инциндентно ребру Kn+1 (клике) или наоборот, если данная ребро Kn (клика) является подграфом данного ребра Kn+1 (клике).

Опр.: Говорят, что в Графе два Ребра Kn (клики) смежные, если у них есть общее Ребро Kn-1 (клика).

Опр.: Маршрутом Kn (Путем Kn) Графа называется чередующаяся последовательность ребер Kn и ребер Kn+1 kn,0,kn+1,1,kn,1,kn+1,2,kn,2, … ,kn+1,l,kn,l, где элементы kn,i из множества Ребер Kn Графа, а kn+1,i из множества ребер Kn+1 Графа, в которой любые два соседних элемента Инцидентны.

Опр.: Если kn,0 ∩ kn,l ≠ ∅ (пересечение множества вершин из начального ребра Маршрута Kn и конечного ребра Маршрута Kn не пустое), то Маршрут Kn Замкнут, иначе Открыт.

Опр.: Если все наборы Ребер Kn+1 различны, то Маршрут Kn называется Цепью Kn.

Опр.: Если все наборы Ребер Kn различны (а значит и наборы Ребер Kn+1), то Маршрут Kn называется Простой Цепью Kn.

Опр.: Замкнутая Цепь Kn называется Циклом Kn.

Опр.: Замкнутая Простая Цепь Kn называется Простым Циклом Kn.

Опр.: Граф без Циклов Kn называется Ацикличным относительно Kn.

Опр.: Связанный Граф без Циклов Kn называется Деревом Kn.

Опр.: Сведением (или Склеиванием) Вершин Графа называется такая операция над исходным Графом, при котором Вершины v1,v2, … ,vn удаляются из Графа вместе с инцидентными ребрами, а вместо них появляется вершина с названием <<v1,v2, … ,vn>>, которая соединяется ребрами с бывшими смежными вершинами для удаленных вершин v1,v2, … ,vn.

Рисунок №1. Альбом: Задача о 4 красках

Примечание: В приведенном примере граф состоит из открытых маршрутов K3. При этом каждые/любые два соседних (смежных) ребра K3 имеют общий подграф — ребро K2. Более того, каждая/любая вершина в ребре K3 соединена ровно с двумя вершинами из соседнего ребра K3. По аналогии можно создать подобные примеры для графов, состоящих из маршрутов K4, K5, …, Kn. Также заметим, что раз данный подграф состоит только из открытых маршрутов K3, то его можно однозначно раскрасить, используя наименьшее три цвета при заданной начальной раскраски одного из его ребер K3. И как следствие означает, что данный граф является трех-дольным, то есть разбивается наименьшее на три доли. Можно провести аналогию данного графа с деревом, также по аналогии можно дать название данному графу как дерево K3. Более подробно это будет описано при доказательстве теоремы о n-дольности графа.

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

По поводу операции склеивания вершин в графе, название склеенной вершины (то есть добавленной вместо удаленных вершин) является строкой, в которой через запятую перечисляются названия удаленных вершин, делается это только ради удобства. Поскольку данная операция будет применятся для склеивания вершин окрашенных в одинаковые цвета, чтобы не потерять информацию об изначальных вершинах их удобнее запоминать в названии новой созданной вершине в ходе операции преобравзования над графом. К тому же в определении графа нет явных указаний и ограничений на именование вершин графа. Правда, из практических соображений, принято вершины нумеровать натуральными числами. Таким образом, при выполнении операции склеивания над вершинами, раскрашенными в один цвет, с названиями <<4>>, <<7>>, <<47>> и <<13,1>> получаем новую вершину с названием <<4,7,47,13,1>>, а оперируемые вершины удаляем. Тогда новую вершину можно раскрасить в заданный цвет, не беспокоясь о том, что в последствии преобразований графа мы забудем в какой цвет нужно раскрасить вершины исходного графа.

Теорема о n-дольном графе

Формулировка: В графе все маршруты Kn сводятся к ребру Kn тогда и только тогда, когда граф является n-дольным.

Примечание: В формулировке теоремы используется термин «сводятся» для краткости. Если более подробноостановиться на этом, то под этим терминомподразумевается следующая операция над графом. Поскольку необходимо проверить граф на n-дольность, то соответственно находим в заданном графе клику kn и раскрашиваем вершины данной клики kn в n разых цветов произвольным образом. Далее поскольку данная клика kn входит в подграф маршрута Kn, то соответственно можно раскрасить и данный маршрут в n цветов единственным способом. Это можно добиться последовательным раскрашиванием вершин из данного маршрута Kn граничащих с n-1 вершиной с разными цветами в оставшийся цвет. Теперь к вершинам с одинаковыми цветами применим операцию сведения. В результате получим либо новое ребро Kn, либо новый маршрут Kn, либо петлю. В случае получения нового маршрута Kn необходимо заново произвести операцию сведения для текущего маршрута Kn. Из того, что количество вершин в исходном графе конечно, получим в результате операции сведения маршрута Kn либо ребро Kn (тогда говорят, что маршрут Kn сводится к ребру Kn), либо петлю (тогда говорят, что маршрут Kn не сводится к ребру Kn). Применив данную операцию сведения для каждого маршрута Kn в данном графе в результате получим либо одиночные ребра Kn (тогда говорят, что граф сводится к ребрам Kn или что все маршруты Kn сводятся к ребру Kn), либо петлю (тогда говорят, что граф не сводится к ребрам Kn или что есть маршруты Kn, которые не сводятся к ребру Kn).

Лемма №2. Пусть дан граф, задача заключается в том, чтобы определить на какое наименьшее количество доль его можно разбить. Соответственно, если в графе есть максимальная клика Kn, то данный граф разбить на меньшее чем n доль не получится. Поскольку по принципу Дирихле при любой разбивке на меньшее чем n доль две или более вершины максимальной клики Kn окажутся в одной доле, а так как эти вершины принадлежат подграфу Kn, то между ними должно быть ребро, чего не может быть в одной доле по определению n-дольного графа.

Примечание: Поскольку нам необходимо разбить граф на наименьшее количество доль, то применять данную теорему бессмысленно для маршрутов Kn, где n меньше чем у максимальной клике в графе. Другими словами, если дан граф, в котором заведомо известно, что максимальная клика равна 10 (K10), то бессмысленно в этом графе искать маршруты K2, K3, …, K9, поскольку данные маршруты не будут сводится к соответствующим ребрам и соответственно теорема будет давать отридцательный ответ на вопрос 2-, 3-, …, 9-дольности данного графа. Такого же результата можно добиться просто применив Лемму №2 и сразу же приступив к проверке графа на 10-дольность.

Для сравнения, если в данной формулировке теоремы о n-дольном графе заменить условие для двудольного графа, то получим: «В графе все маршруты сводятся к ребру тогда и только тогда, когда граф является двудольным». И действительно, открытые маршруты всегда будут сводится к ребру, а циклы только в случае четности количества их ребер, что в точности соответствует условию теоремы Кенига.

Доказательство теоремы о n-дольном графе

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

Необходимость. Пусть в графе все маршруты Kn сводятся к ребру Kn. Тогда сведем все эти маршруты Kn к ребрам Kn. Далее поскольку после проделанной операции над графом все маршруты Kn преобразовались в ребра Kn, то в полученном графе не найдется ни одной вершины (непринадлежащей ребру Kn) соединенной сразу с n-1 вершиной одного ребра Kn, поскольку такая вершина входила бы в маршрут Kn, который мы должны были бы свести к ребру Kn. На данном этапе мы уже свели часть вершин данного графа, осталось свести оставшиеся вершины изначально непринадлежащие маршрутам Kn.

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

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

Данная операция напоминает построение дерева, только в нашем случае дерево будет состоять из ребер Kn.

Итак, возьмем вершину, непринадлежащую ребрам Kn, и добавим ребра из данной вершины к вершинам любого ребра Kn.

Если мы докажем, что граф с добавленными ребрами является n-дольным, то и исходный граф также будет являтся n-дольным.

Итак, после добавления новых ребер выбранная вершина будет соединена маршрутом Kn с ребром Kn, следовательно, данную вершину можно свести к данному ребру Kn. После сведения данная вершина окажется в ребре Kn, и нам необходимо проверить, не стали ли смежные вершины для сведенной нами вершиныпрепятствовать дальнейшей работе.

Рассмотрим все смежные вершины, поскольку до преобразования (сведения вершины с ребром Kn, но после сведения маршрутов Kn к ребру Kn) они могли быть смежными наибольшее только n-2 вершинами с любым из ребер Kn, так как не входили в маршрут Kn, то после преобразования вершины могли стать смежными с n-1 вершиной из ребра Kn и как следствие образовывать маршрут Kn. Тогда сделаем сведение к данному ребру Kn для данных вершин. Получим картину, соответствующую графу со сведенными маршрутами Kn. В итоге будет уменьшаться количество вершин в графе, пока не закончатся вершины, непринадлежащие ребрам Kn.

Теперь по аналогии, данные ребра Kn соединить маршрутом Kn, и свести все к одному ребру Kn.

Поскольку для сведения всего графа к ребру Kn потребовалось, лишь проверить сведение маршрутов Kn, то соответственно, раз сведенный граф раскрашивается в n цветов, то и исходный граф также раскрашивается в n цветов и также является n-дольным. Ч.т.д.

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

Следствие №1: Граф с наибольшей кликой n имеет наименьшее либо n-доль, либо (n+1) доль.

Доказательство: Поскольку в графе есть наибольшая клика n (Kn), то граф необходимо проверить по теореме о n-дольности. В случае положительного результата граф имеет наименеьшее n-доль. В случае отридцательного результата, поскольку в графе нет маршрутов Kn+1, то соответственно до каждой вершины можно достроить маршрут Kn+1, используя алгоритм, описанный в теоремео n-дольности, который будет сводиться к ребру Kn+1. Таким образом, граф будет наименьшее (n+1)-дольным. Ч.т.д.

Примечание: На самом деле теорему Кёнига правильнее формулировать так:
В графе нет нечетных циклов тогда и только тогда, когда граф является двудольным.

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

Соответственно и формулировку теоремы о n-дольности необходимо скорректировать по аналогии следующим образом:
В графе нет маршрутов Kn, которые не сводятся к ребру Kn тогда и только тогда, когда граф является n-дольным.

Применим данную теорему о n-дольности к задаче о 4-х красках.

Задача о 4-х красках

Поскольку планарный граф, к раскраске которого сводится раскраска плоской карты не содержит клики K5, то данный граф по следствию из теоремы о n-дольнсти можно раскрасить либо в 5, либо в 4 цвета. Для того чтобы доказать возможность раскраски в четыре цвета для любого планарного графа, необходимо доказать, что все маршруты K4 планарных графов сводятся к ребру K4.

Итак, рассмотрим полный граф K4, маршрут K4 и дерево K4 на плокости.

Для начала рассмотрим единственное возможное изображение полного графа K4 на плоскости:

Рисунок №2. Альбом: Задача о 4 красках

И маршрута K4:

Рисунок №3. Альбом: Задача о 4 красках

Решение: Заметим, что в графе K4 на плоскости имеется центральная вершина, которая не может граничить ни с какой вершиной вне треугольника, иначе будет нарушение условия планарности. Тогда до всех вершин, находящихся внутри треугольника достроим маршрут K4. В итоге получим нечто наподобие Рисунка №3. Теперь начнем сводить данный маршрут K4, начиная с самой центральной вершины, поскольку данная вершина не смежна вершинам не из данного треугольника, то при сведении получение петли исключается полностью. Следовательно, в планарном графе все маршруты K4 сводятся к ребру K4, что как следствие означает 4-дольность всех планарных графов и возможность их раскраски в наименьшее количество цветов, используя максимум 4 цвета. Ч.т.д.

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

Тэги:
[задача, теорема, доказательство]

Настройка торрент-клиента rTorrent в FreeBSD

Настройка торрент-клиента rTorrent в FreeBSD

Установка

Установка из пакеджей:

# pkg_add -r rtorrent

Установка из портов:

// Узнаём где находится порт rTorrent
# whereis rtorrent

// Переходим в директорию порта rTorrent
# cd /usr/ports/net-p2p/rtorrent

// Компилируем и устанавливкаем rTorrent
# make install clean

Конфигурация

Скопируем стандартный конфиг в директорию пользователя:

$ cp /usr/local/share/examples/rtorrent/rtorrent.rc /home/_имя_пользователя_/.rtorrent.rc

.rtorrent.rc

# This is an example resource file for rTorrent. Copy to
# ~/.rtorrent.rc and enable/modify the options as needed. Remember to
# uncomment the options you wish to enable.

# Maximum and minimum number of peers to connect to per torrent.
#min_peers = 40
#max_peers = 100

# Same as above but for seeding completed torrents (-1 = same as downloading)
# Устанавливает значение минимального и максимального количества пиров
# в раздаваемом (сидируемом) торренте, по умолчанию -1, то есть неограничено.
#min_peers_seed = 10
#max_peers_seed = 50

# Maximum number of simultanious uploads per torrent.
#max_uploads = 15

# Global upload and download rate in KiB. "0" for unlimited.
# Определяет скорость скачивания в Кб/с. Значение "0" - отключает ограничение по скорости.
#download_rate = 0
# Определяет скорость раздачи в Кб/с. Значение "0" - отключает ограничение по скорости.
#upload_rate = 0

# Default directory to save the downloaded torrents.
# Опция указывает директорию по умолчанию для сохранения закачаных файлов.
#directory = ./
directory = /mnt/disk1/_torrent

# Default session directory. Make sure you don't run multiple instance
# of rtorrent using the same session directory. Perhaps using a
# relative path?
# Опция позволяет сохранять текущее состояние (прогресс) ваших загрузок.
# Рекомендуется создать директорию с названием ".session"
#session = ./session
session = /home/opencoder/.rtorrent_session

# Watch a directory for new torrents, and stop those that have been
# deleted.
# Опция наблюдает за определенными директориями на наличие новых торрент-файлов.
# Сохранение торрент-файла в эту директорию, автоматически начнет загрузку.
#schedule = watch_directory,5,5,load_start=./watch/*.torrent
#schedule = untied_directory,5,5,stop_untied=

# rTorrent каждые 20 секунд проверяет этот каталог на новые *.torrent файлы
# и если они есть то ставит их на закачку
schedule = watch_directory,20,20,"load_start=/mnt/disk1/_my/torrent/*.torrent,d.set_directory=/mnt/disk1/_torrent"
# Для другой директории аналогично
schedule = watch_directory_2,20,20,"load_start=/home/opencoder/Downloads/*.torrent,d.set_directory=/home/opencoder/Downloads"

schedule = untied_directory,2000,2000,stop_untied=
schedule = untied_directory_2,2000,2000,stop_untied=


# Close torrents when diskspace is low.
#schedule = low_diskspace,5,60,close_low_diskspace=100M

# Stop torrents when reaching upload ratio in percent,
# when also reaching total upload in bytes, or when
# reaching final upload ratio in percent.
# example: stop at ratio 2.0 with at least 200 MB uploaded, or else ratio 20.0
#schedule = ratio,60,60,"stop_on_ratio=200,200M,2000"

# The ip address reported to the tracker.
#ip = 127.0.0.1
#ip = rakshasa.no

# The ip address the listening socket and outgoing connections is
# bound to.
#bind = 127.0.0.1
#bind = rakshasa.no

# Port range to use for listening.
# Параметр задает порт(ы) для прослушивания.
# Рекомендуется использовать порт, который больше чем 49152.
#port_range = 6890-6999
port_range = 6890-6999

# Start opening ports at a random position within the port range.
# Включить использование случайного номера порта для прослушивания rTorrent.
# Лучше не использовать случайный порт.
#port_random = no
port_random = no

# Check hash for finished torrents. Might be usefull until the bug is
# fixed that causes lack of diskspace not to be properly reported.
# Опция выполняет проверку хэш-кода, когда загрузка завершена.
# При запуске, она проверяет на наличие ошибок завершенные (загруженные)
# файлы.
#check_hash = no
check_hash = yes

# Set whetever the client should try to connect to UDP trackers.
# Использовать UDP протокол.
# Полезно для открытых торрент-трекеров для минимизации количества запросов к трекеру.
#use_udp_trackers = yes
use_udp_trackers = yes

# Alternative calls to bind and ip that should handle dynamic ip's.
#schedule = ip_tick,0,1800,ip=rakshasa
#schedule = bind_tick,0,1800,bind=rakshasa

# Encryption options, set to none (default) or any combination of the following:
# allow_incoming, try_outgoing, require, require_RC4, enable_retry, prefer_plaintext
#
# The example value allows incoming encrypted connections, starts unencrypted
# outgoing connections but retries with encryption if they fail, preferring
# plaintext to RC4 encryption after the encrypted handshake
#
# Параметр включает или отключает шифрование.
# Очень важно включить эту опцию, не только для Вас, но так же для Ваших коллег (пиров).
# Некоторым пользователям нужно скрыть использование своей пропускной 
# способности от их интернет-провайдера.
# allow_incoming - принимать зашифрованные входящие соединения.
# try_outgoing - шифрование исходящих соединений.
# require - запретить незашифрованные обращения.
# require_RC4 - также запретить передачу текста после первичного зашифрованного установления связи
# enable_retry - если первоначальное исходящее установление связи окажется неудачным, повторить с 
# шифрованием, если оно было отключено, и без, если шифрование использовалось.
# prefer_plaintext - использовать текст если пир предлагает выбор между открытым текстом и 
# шифрованием RC4, иначе будет использоваться RC4. 
# encryption = allow_incoming,enable_retry,prefer_plaintext
encryption = allow_incoming,try_outgoing,enable_retry

# Enable DHT support for trackerless torrents or when all trackers are down.
# May be set to "disable" (completely disable DHT), "off" (do not start DHT),
# "auto" (start and stop DHT as needed), or "on" (start DHT immediately).
# The default is "off". For DHT to work, a session directory must be defined.
# 
# Опция включает поддержку DHT.
# Значение DHT по умолчанию "off".
# DHT распространен среди открытых трекеров и позволяет клиенту получить больше пиров.
# Для правильной работы DHT каталог сеансов "session" должен быть определен.
# dht = auto
dht = auto

# UDP port to use for DHT. 
# 
# dht_port = 6881
dht_port = 6881

# Enable peer exchange (for torrents not marked private)
#
# peer_exchange = yes
peer_exchange = yes

#
# Do not modify the following parameters unless you know what you're doing.
#

# Hash read-ahead controls how many MB to request the kernel to read
# ahead. If the value is too low the disk may not be fully utilized,
# while if too high the kernel might not be able to keep the read
# pages in memory thus end up trashing.
#hash_read_ahead = 10

# Interval between attempts to check the hash, in milliseconds.
#hash_interval = 100

# Number of attempts to check the hash while using the mincore status,
# before forcing. Overworked systems might need lower values to get a
# decent hash checking rate.
#hash_max_tries = 10


# Лог-файл
# log.execute = /home/opencoder/rtorrent.log
log.execute = /home/opencoder/rtorrent.log

Управление с клавиаруры


Ctrl-q

— Выход из приложения.


Ctrl-s

— Начать загрузку. В первую очередь запускает хэширование, если оно уже не было сделано.


Ctrl-d

— Остановка активной загрузки или удаление остановленной загрузки.


Ctrl-k

— Остановить и закрыть файлы активной загрузки.


Ctrl-r

— Инициировать хэш-проверку торрента. Без запуска загрузки/отдачи.


Ctrl-o

— Изменить директорию на загрузку (торрент должен быть закрыт).


<- (влево)

— Возврат к предыдущему экрану.


-> (вправо)

— Переход к следующему экрану.


Backspace/Enter

— Добавляет указанный *.torrent.


a | s | d

— Регулировка увеличения глобальной скорости отдачи на 1|5|50 КБ/с


A | S | D

— Регулировка увеличения глобальной скорости загрузки на 1|5|50 КБ/с


z | x | c

— Регулировка уменьшения глобальной скорости отдачи на 1|5|50 КБ/с


Z | X | C

— Регулировка уменьшения глобальной скорости загрузки на 1|5|50 КБ/с

Совет

Удобнее всего использовать rTorrent с консольным мультиплексором tmux.

Источник:
ВикиУчебник [http://ru.wikibooks.org/wiki/RTorrent]
ArchLinux wiki[https://wiki.archlinux.org/index.php/RTorrent_(%D0%A0%D1%83%D1%81%D1%81%D0%BA%D0%B8%D0%B9)]

Тэги:
[FreeBSD, BSD, rTorrent, torrent, торрент]