Posts Tagged ‘preCybWiki’
Конспекти: БД, ЧМ.
Вчора я купив собі 10 метрів подовжувача, тому мав можливість сидіти на лекції де захочу, з включеним ноутбуком. Тому мені вдалось записати дві лекції.
Правда запис був майже не успішний, бо на лекції з БД, я нічого не розумів. Треба підтягувати теорію. Правда записувати було легко, так як там був майже один текст.
Машина Тюрінга
Машину Тюрінга можна собі уявити, як машину, яка їздить по колії (колія звісно нескінченна в два боки), і малює щось вапном на шпалах. Крім того, вона вміє читати, те, що намалювала на шпалах. Також ця машина має пам’ять ( набір станів).
Машиною Тюрінга з формальної точки зору є впорядкований набір таких елементів:
- 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 — рухаємося вліво. Варто зауважити, що ми спочатку витерли ліву, одиничку, і коли при спробі витерти праву, ми виявляємо що її вже немає, то кількість одиничок на стрічці менша на одиницю від потрібної. Тому перехід в кінцевий стан супроводжується додаванням одинички.
А той хто знайде алгоритм добутку з поясненням його роботи — молодець. Я пробував розібратись в тому що в методичці Шкільняка С.С. але виявив там помилку. Також стаття частково за мотивами лекцій.
Клас – многочлен
Маленький клас на 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->k=k;
head->pow=pow;
head->next=NULL;
return ;
}
else
{
pmonomial cur=head,curpr;
pmonomial ins;
if(cur->pow==pow)
{
cur->k+=k;
return;
}
if(cur->pow<pow) // the highest power
{
ins = new tmonomial;
ins->k=k;
ins->pow=pow;
ins->next=cur;
head=ins;
return;
}
while(cur->next)
{
curpr=cur;
cur=cur->next;
if(cur->pow==pow) // equal power
{
cur->k+=k;
return;
}
if((cur->pow<pow)&&(curpr->pow>pow))
{
//insert between two cursors
ins= new tmonomial;
ins->next=cur;
ins->k=k;
ins->pow=pow;
curpr->next=ins;
return;
}
}
// else the lowest power
ins=new tmonomial;
ins->k=k;
ins->pow=pow;
ins->next=NULL;
cur->next=ins;
}
}
void print()
{
pmonomial cur=head;
if(!cur)
{
printf("0x0");
return;
}
while(1)
{
printf("%.2fx%d",cur->k,cur->pow);
if(cur->next)
{
if (cur->next->k>=0) printf("+");
}
else
return;
cur=cur->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,"%fx%d",&k,&p);
addmonomial(k,p);
while((*str)&&(*str!='+'))
{
str++;
}
if(*str=='+') str++;
}
}
int maxpow()
{
if(head)
{
if(head->k!=0)
return head->pow;
else
{
pmonomial cur=head;
while((cur)&&(cur->k==0))
{
cur=cur->next;
}
if(cur)
return cur->pow;
else
return -1;
}
}
else return -1;
}
void clear()
{
pmonomial cur=head;
pmonomial del;
while(cur)
{
del=cur;
cur=cur->next;
delete del;
}
head=NULL;
}
tpolynomial operator=(tpolynomial op)
{
clear();
pmonomial cur=op.head;
while(cur)
{
addmonomial(cur->k,cur->pow);
cur=cur->next;
}
return *this;
}
tpolynomial operator+=(tpolynomial op2)
{
pmonomial cur=op2.head;
while(cur)
{
addmonomial(cur->k,cur->pow);
cur=cur->next;
}
return *this;
}
tpolynomial operator-=(tpolynomial op2)
{
pmonomial cur=op2.head;
while(cur)
{
addmonomial(-cur->k,cur->pow);
cur=cur->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->k*=sc;
cur=cur->next;
}
return *this;
}
tpolynomial operator*=(tmonomial mul)
{
pmonomial cur=head;
while(cur)
{
cur->k*=mul.k;
cur->pow+=mul.pow;
cur=cur->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->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()<op2.maxpow()) return res;
while(temp.maxpow()>=op2.maxpow())
{
t.k=temp.head->k/op2.head->k;
t.pow=temp.head->pow-op2.head->pow;
res.addmonomial(t.k,t.pow);
temp=temp-op2*t;
}
return res;
}
};
Придирайтеся в коментарях, на здоров’я. Особливо хотілось би почути прихильників красивого коду.
Угорський метод
Угорський метод
Лаболаторна робота з дослідження операцій 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 нулів (кількість виконавців і робіт), то ці нулі показують кому яку роботу дати. В нас позначено тільки чотири нулі, тому розв’язок не оптимальний. З матрицею потрібно робити перетворення.
- Позначимо символом # (“дієз”) рядки, в яких є непозначені нулі (без *).
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 #
Тепер викреслюємо непозначені рядки і позначені стовпчики. Але я краще просто підкреслю те що має залишитись.
| # | |
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.
Уточнення, зауваження, і повідомлення про помилки пишіть в коментарях.
Машина з натуральночисельними регістрами
Машина з натуральночисельними регістрами, – ще одна модель для теорії алгоритмів. Не така відома, як машина Тюрінга, зате (як на мене) для неї легше складати алгоритми.
Але складати алгоритми на папірці не цікаво, тому я написав маленьке середовище, яке допомагає нам складати і перевіряти алгоритми. Ось як воно виглядає:
Зкачати можна звідси (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//Результат має міститись в нульовому регістрі
