Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Posts Tagged ‘preCybWiki

Конспекти: БД, ЧМ.

leave a comment »

Вчора я купив собі 10 метрів подовжувача, тому мав можливість сидіти на лекції де захочу, з включеним ноутбуком. Тому мені вдалось записати дві лекції.

Правда запис був майже не успішний, бо на лекції з БД, я нічого не розумів. Треба підтягувати теорію. Правда записувати було легко, так як там був майже один текст.

Прочитати решту цього запису »

Advertisements

Written by bunyk

Жовтень 29, 2009 at 16:14

Оприлюднено в Конспекти

Tagged with , ,

Машина Тюрінга

leave a comment »

Машину Тюрінга можна собі уявити, як машину, яка їздить по колії (колія звісно нескінченна в два боки), і малює щось вапном на шпалах. Крім того, вона вміє читати, те, що намалювала на шпалах. Також ця машина має пам’ять ( набір станів).

Машиною Тюрінга з формальної точки зору є впорядкований набір таких елементів:

  • Q – скінченна множина внутрішніх станів
  • T – скінченний алфавіт символів стрічки. Туди обов’язково має входити символ порожньої клітки — „λ”
  • δ:QxT→QxTx{R,L,ε} однозначна функція переходу.
  • q0∈Q початковий стан.
  • q*∈Q кінцевий стан.

Функція переходу задається множиною записів такого вигляду: pa→qbL, pa→qbR або pa→qb, де p,q∈Q, a,b∈T. Це означає: якщо ми знаходимося в стані p, і читаємо символ a, то переходимо до стану q, записуємо на місці a b, і зміщуємося наліво (L), направо (R), чи залишаємося на місці.

Зазвичай початковим станом q0, вважають такий стан, коли всі символи зліва від головки порожні (λ), а головка показує перший непорожній символ вхідного слова.

При переході до фінального стану q* машина зупиняється.

МТ-обчислювана функція — функція, яку можна обчислити за допомогою машини Тюрінга.

Розглянемо МТ—обчислювані функції над числами в одиничній системі числення. Аргументи будемо розділювати символом дієз (#)

Додавання f(x,y)=x+y

q01→q01R
q0#→q01R
q0λ→q1λL
q11→q*λ

Машина спочатку проходить всі символи зліва направо, замінюючи роздільник на 1. Коли дійшла до кінця (порожнього символа), вертається і стирає зайву одиничку.

Урізана різниця f(x,y)=x-y, якщо x>y, і 0, якщо x≤y

q0#→q4λR
q01→q1λR
q11→q11R
q1#→q1#R
q1λ→q2λL
q21→q3λL
q2#→q*1
q31→q31L
q3#→q3#L
q3λ→q3λR
q41→q4λR
q4λ→q*λ

Віднімання трохи складніше. Ми видаляємо по одній одиничці зліва і зправа, поки, не витремо всі одинички зправа. Якщо залишились тільки праві одинички, це значить, що x<y, і результат нуль. Тоді машина переходить в стан q4, і стирає все. В стані q0 витираємо ліву одиничку, q1 — рухаємося вправо, q2 — витираємо праву одиничку, q3 — рухаємося вліво. Варто зауважити, що ми спочатку витерли ліву, одиничку, і коли при спробі витерти праву, ми виявляємо що її вже немає, то кількість одиничок на стрічці менша на одиницю від потрібної. Тому перехід в кінцевий стан супроводжується додаванням одинички.

А той хто знайде алгоритм добутку з поясненням його роботи — молодець. Я пробував розібратись в тому що в методичці Шкільняка С.С. але виявив там помилку. Також стаття частково за мотивами лекцій.

Written by bunyk

Березень 17, 2009 at 00:39

Оприлюднено в Всяке

Tagged with ,

Клас – многочлен

with 3 comments

Маленький клас на C++, який задає тип даних – многочлен, і основні оператори над цим типом. Створений як елемент лаболаторної, тому функціональність не повна. В пам’яті представляється списком одночленів відсортованих за спаданням. Тестувався з Microsoft Visual C++ 2008.

Структура tmonomial задає структуру одночлена. float k – коефіцієнт біля ікса, int pow – степінь ікса.
struct smonomial *next; – посилання на наступний одночлен многочлена.

Клас tpolynomial задає многочлен. В нього є тільки одне захищене поле – head – посилання на список одночленів. Конструктор надає йому нульового значення.

Методи

void addmonomial(float k,int pow) – додає до многочлена одночлен, з коефіцієнтом k і степінню ікса pow. Все одразу скорочується і відсортовується.
void print() – виводить многочлен на консоль в форматі подібному на 2.23x4+1.45x2-7.20x1.
void sscan(char *str) – читає многочлен з рядка такого ж формату.
int maxpow() – максимальна степінь многочлену, або порядок іншими словами
void clear() – обнулити многочлен
void sscan(char *str) – читає многочлен з рядка такого ж формату.

Оператори

+,-,*,/,=,+=,-=,*= – як звичайно, а крім того є *= на тип одночлен, і на число з плаваючою крапкою.

typedef struct smonomial
{
	float k;
	int pow;
	struct smonomial *next;
} tmonomial;
typedef tmonomial *pmonomial;
class tpolynomial
{
protected:
	pmonomial head;
public:
	tpolynomial()
	{
		head=NULL;
	}
	void addmonomial(float k,int pow)
	{
		if(!k) return;
		if(!head)
		{
			head = new tmonomial;
			head-&gt;k=k;
			head-&gt;pow=pow;
			head-&gt;next=NULL;
			return ;
		}
		else
		{
			pmonomial cur=head,curpr;
			pmonomial ins;
			if(cur-&gt;pow==pow)
			{
				cur-&gt;k+=k;
				return; 
			}
			if(cur-&gt;pow&lt;pow) // the highest power
			{
				ins = new tmonomial;
				ins-&gt;k=k;
				ins-&gt;pow=pow;
				ins-&gt;next=cur;
				head=ins;
				return;
			}
			while(cur-&gt;next)
			{
				curpr=cur;
				cur=cur-&gt;next;
				if(cur-&gt;pow==pow) // equal power
				{
					cur-&gt;k+=k;
					return; 
				}
				if((cur-&gt;pow&lt;pow)&amp;&amp;(curpr-&gt;pow&gt;pow))
				{
					//insert between two cursors
					ins= new tmonomial;
					ins-&gt;next=cur;
					ins-&gt;k=k;
					ins-&gt;pow=pow;
					curpr-&gt;next=ins;
					return;
				}
			}
			// else the lowest power
			ins=new tmonomial;
			ins-&gt;k=k;
			ins-&gt;pow=pow;
			ins-&gt;next=NULL;
			cur-&gt;next=ins;
		}
	}
	void print()
	{
		pmonomial cur=head;
		if(!cur) 
		{
			printf(&quot;0x0&quot;);
			return;
		}
		while(1)
		{
			printf(&quot;%.2fx%d&quot;,cur-&gt;k,cur-&gt;pow);
			if(cur-&gt;next)
			{
				if (cur-&gt;next-&gt;k&gt;=0) printf(&quot;+&quot;);
			}
			else
				return;
			cur=cur-&gt;next;
		}
	}
	void sscan(char *str)
	{
		int p;
		float k;
		char extend[1000];
		char *ep=extend;
		while(*str)
		{
			if(*str=='-')
			{
				*ep='+';
				ep++;
				*ep='-';
			}
			else
			{
				*ep=*str;
			}
			str++;
			ep++;
		}
		*ep='';
		str=extend;
		while(*str)
		{
			sscanf(str,&quot;%fx%d&quot;,&amp;k,&amp;p);
			addmonomial(k,p);
			while((*str)&amp;&amp;(*str!='+'))
			{
				str++;
			}
			if(*str=='+') str++;
		}
	}
	int maxpow()
	{
		if(head)
		{
			if(head-&gt;k!=0)
				return head-&gt;pow;
			else
			{
				pmonomial cur=head;
				while((cur)&amp;&amp;(cur-&gt;k==0))
				{
					cur=cur-&gt;next;
				}
				if(cur)
					return cur-&gt;pow;
				else 
					return -1;
			}
		}
		else return -1;
	}
	void clear()
	{
		pmonomial cur=head;
		pmonomial del;
		while(cur)
		{
			del=cur;
			cur=cur-&gt;next;
			delete del;
		}
		head=NULL;
	}
	tpolynomial operator=(tpolynomial op)
	{
		clear();
		pmonomial cur=op.head;
		while(cur)
		{
			addmonomial(cur-&gt;k,cur-&gt;pow);
			cur=cur-&gt;next;
		}
		return *this;
	}
	tpolynomial operator+=(tpolynomial op2)
	{
		pmonomial cur=op2.head;
		while(cur)
		{
			addmonomial(cur-&gt;k,cur-&gt;pow);
			cur=cur-&gt;next;
		}
		return *this;
	}
	tpolynomial operator-=(tpolynomial op2)
	{
		pmonomial cur=op2.head;
		while(cur)
		{
			addmonomial(-cur-&gt;k,cur-&gt;pow);
			cur=cur-&gt;next;
		}
		return *this;
	}
	tpolynomial operator+(tpolynomial op2)
	{
		tpolynomial res;
		res=*this;
		res+=op2;
		return res;
	}
	tpolynomial operator-(tpolynomial op2)
	{
		tpolynomial res;
		res=*this;
		res-=op2;
		return res;
	}
	tpolynomial operator*=(float sc)
	{
		pmonomial cur=head;
		while(cur)
		{
			cur-&gt;k*=sc;
			cur=cur-&gt;next;
		}
		return *this;
	}
	tpolynomial operator*=(tmonomial mul)
	{
		pmonomial cur=head;
		while(cur)
		{
			cur-&gt;k*=mul.k;
			cur-&gt;pow+=mul.pow;
			cur=cur-&gt;next;
		}
		return *this;	
	}
	tpolynomial operator*(tmonomial mul)
	{
		tpolynomial res;
		res=*this;
		res*=mul;
		return res;
	}
	tpolynomial operator*=(tpolynomial op2)
	{
		pmonomial cur=op2.head;
		tpolynomial res;
		while(cur)
		{
			res+=*this*(*cur);
			cur=cur-&gt;next;
		}
		*this=res;
		return res;
	}
	tpolynomial operator*(tpolynomial op2)
	{
		tpolynomial res;
		res=*this;
		res*=op2;
		return res;
	}
	tpolynomial operator/(tpolynomial op2)
	{
		tpolynomial res;
		tpolynomial temp=*this;
		tmonomial t;
		if(temp.maxpow()&lt;op2.maxpow()) return res;
		while(temp.maxpow()&gt;=op2.maxpow())
		{
			t.k=temp.head-&gt;k/op2.head-&gt;k;
			t.pow=temp.head-&gt;pow-op2.head-&gt;pow;
			res.addmonomial(t.k,t.pow);
			temp=temp-op2*t;
		}
		return res;
	}

};

Придирайтеся в коментарях, на здоров’я. Особливо хотілось би почути прихильників красивого коду.

Written by bunyk

Лютий 22, 2009 at 20:55

Оприлюднено в Кодерство

Tagged with ,

Угорський метод

with 3 comments

Угорський метод

Лаболаторна робота з дослідження операцій aka методи оптимізації

В цій статті я хочу розказати про розв’язування задачі про виконавців угорським методом. Тут буде тільки відповідь на запитання: “Як розв’язати задачу”, а не “Чому і як цей метод працює?”. Записано на семінарі в Богдана Валерійовича Довгая.

Умова задачі:

ми маємо n завдань, і n виконавців. При чому кожен виконавець для свого завдання хоче певний розмір зарплати. Потрібно поділити завдання між виконавцями з мінімальними витратами. Крім того один виконавець має робити одне завдання. Не більше і не менше. Запишемо витрати i-того виконавця на j-ту роботу як Ci,j. Наприклад:

3 10 5 9 16
6 8 11 8 18
7 13 10 3 4
5 9 6 21 12
5 4 12 6 13

Розв’язок:

Знаходимо мінімальний елемент кожного рядка:

3 10 5 9 16 3
6 8 11 8 18 6
7 13 10 3 4 3
5 9 6 21 12 5
5 4 12 6 13 4

І віднімаємо від кожного елементу рядка:

0 7 2 6 13
0 2 5 2 12
4 10 7 0 1
0 4 1 16 7
1 0 7 2 9

Далі таке саме робимо для стовпців. Наша мета – зробити хоча б один нуль в кожному рядку і кожному стовпцю:

0 7 2 6 13
0 2 5 2 12
4 10 7 0 1
0 4 1 16 7
1 0 7 2 9

0 0 1 0 1

Отримуємо:

0 7 1 6 12
0 2 4 2 11
4 10 6 0 0
0 4 0 16 6
1 0 6 2 8

Тепер підготовчий етап пройдено. Можна розставляти позначки. Позначки розставляються за таким правилом: “Якщо в рядку є єдиний непозначений нуль, то позначаємо його (символ *). Всі нулі того стовпчика який щойно позначили – викреслюємо (символ ^)”.

0* 7 1 6 12
0^ 2 4 2 11
4 10 6 0 0
0^ 4 0* 16 6
1 0* 6 2 8

Таке саме робимо для стовпців, тобто “Якщо в стовпці є єдиний непозначений нуль, то позначаємо його. Всі нулі того рядка який щойно позначили – викреслюємо”.

0* 7 1 6 12
0^ 2 4 2 11
4 10 6 0* 0^
0^ 4 0* 16 6
1 0* 6 2 8

Тепер рахуємо скільки нулів позначено. Якщо позначено 5 нулів (кількість виконавців і робіт), то ці нулі показують кому яку роботу дати. В нас позначено тільки чотири нулі, тому розв’язок не оптимальний. З матрицею потрібно робити перетворення.

  1. Позначимо символом # (“дієз”) рядки, в яких є непозначені нулі (без *).
    0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
  2. Позначимо стовпчики в яких в позначених рядочках є викреслений нуль.
    0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
    #
  3. Позначимо рядочки, де в позначених стовпчках є позначений нулик.
    # 0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
    #

Тепер викреслюємо непозначені рядки і позначені стовпчики. Але я краще просто підкреслю те що має залишитись.

# 0* 7 1 6 12
# 0^ 2 4 2 11
4 10 6 0* 0^
0^ 4 0* 16 6
1 0* 6 2 8
#

Серед невикреслених (читай “підкреслених”) рядків шукаємо мінімальний емент. В нас він дорівнює 1. Віднімаємо його від невикреслених рядків,

-1 6 0 5 11
-1 1 3 1 10
4 10 6 0 0
0 4 0 16 6
1 0 6 2 8

і додаємо до викреслених стовпчиків. (Важливо, щоб усі елементи залишились додатніми). В нашому випадку додаємо в перший стовпчик.

0 6 0 5 11
0 1 3 1 10
5 10 6 0 0
1 4 0 16 6
2 0 6 2 8

В нашій новій матриці знову починаємо позначати нулі. Якщо їх буде п’ять завершимо роботу.

# 0^ 6 0^ 5 11
# 0* 1 3 1 10
5 10 6 0* 0^
# 1 4 0* 16 6
2 0* 6 2 8
# #

Позначених нулів знову чотири, тому віднімаємо 1 (мінімальний невикреслений елемент) від невикреслених рядків і додаємо в викреслені стовпчики. З новою матрицею знов продовжимо позначення

0* 5 0^ 4 10
0^ 0^ 3 0* 9
6 10 7 0^ 0*
1 3 0* 15 5
3 0* 7 2 8

Опа. В нас 5 позначених нулів. При чому в кожному рядку і кожному стовпці лише один позначений нуль. Наприклад позначений нуль в першому стовпці першого рядка означає, що першому виконавцю будем давати першу роботу. І так далі. Тепер записуємо матрицю розв’язку X. В ній якщо і-тому робітнику дають j-те завдання то елемент в і-тому рядку і j-тому стовпці буде містити одиничку. Всі інші елементи нульові. Отже X:

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

І звісно насамкінець обчислюємо цільову функцію (витрати). Для цього знаходимо суму всіх елементів по i,j=[1..n] Xi,j*Ci,j. Тобто тільки тих де X ненульове. В нас Z(X)=3+8+4+6+4=25.

Уточнення, зауваження, і повідомлення про помилки пишіть в коментарях.

Written by bunyk

Лютий 19, 2009 at 15:24

Оприлюднено в Всяке, Конспекти

Tagged with ,

Машина з натуральночисельними регістрами

with one comment

Машина з натуральночисельними регістрами, – ще одна модель для теорії алгоритмів. Не така відома, як машина Тюрінга, зате (як на мене) для неї легше складати алгоритми.

Але складати алгоритми на папірці не цікаво, тому я написав маленьке середовище, яке допомагає нам складати і перевіряти алгоритми. Ось як воно виглядає:

Інтерфейс середовища

Зкачати можна звідси (213Кб Rar)

А ось довідка до нього:

// Дві похилі риски (як на початку цього рядка) задають коментар
//На початку рядка можна описати мітку на цей рядок записавши
// ідентифікатор мітки (послідовність букв і цифр) і закриваючу дужку.
// Система має 100 регістрів (від 0 до 99).
//Їх вміст можна побачити зправа.
// Всі значення регістрів - цілі числа від 0 до 65 535.
// Система має чотири команди :
// Z(номер_регістру - встановлює
//значення регістру в нуль.
// S(номер_регістру - збільшує
//значення регістру на одиницю
// T(номер_регістру1,номер_регістру2 -
// копіює значення регістру 1 в регістр 2
// J(номер_регістру1,номер_регістру2, ідентифікатор мітки
// - якщо регістри 1 і 2 мають однакові значення,
// то перейти до команди з міткою заданою
//в третьому параметрі. Інакше перейде до наступної команди.
// Команда якої нема в теорії, але вона
//дуже потрібна на практиці - ввід.
// I(номер_регістру - призупиняє роботу,
//щоб попросити користувача ввести дані в регістр
// При переході на мітку якої не існує,
//або після виконання останньої команди програма
зупиняється.
//Зайві пропуски будуть викликати помилки в роботі.
//Кожна команда знаходиться в новому рядку
//Важливо зауважити що закриваюча дужка
//Відділяє мітку від команди, тому не закривайте дужки

А це приклад програми, яка шукає модуль різниці двох чисел. Як бачимо все дуже просто 🙂


//Модуль різниці

I(0//Ввід
I(1
J(0,1,zero//Якщо числа рівні, то різниця - нуль
T(0,10// Копія даних
T(1,11

loop)S(0//Збільшуємо перше
S(2//Збільшуємо лічильник
J(0,1,min1//Якщо після збільшення перше стало рівне 
//другому, то воно менше
J(2,1,min2//Якщо лічильник рівний другому числу, то //вже нема сенсу його шукати
J(0,0,loop

zero)Z(0//Різниця - нуль
J(0,0,exit

//Якщо перше менше, то міняємо перше і друге місцями
min1)T(10,1
T(11,0
J(0,0,sub

//Інакше все робим як було
min2)T(10,0
T(11,1

//Тепер маємо два числа в 0 і 1 регістрах
//При чому перше строго більше ніж друге
//Тому просто їх віднімаємо
//Принцип: z=x-y => x=y+z (знайти z таке що x=y+z)
sub)Z(2
loop2)J(0,1,res
S(1
S(2
J(0,0,loop2

res)T(2,0//Результат має міститись в нульовому регістрі

Written by bunyk

Лютий 10, 2009 at 21:51

Оприлюднено в Всяке, Кодерство

Tagged with ,