Жовтень « 2009 « Блоґ одного кібера

Archive for Жовтень 2009

І хоча ми не MIT, та все ж…

Сьогодні знайшов на нашому ftp, кілька папочок з MIT OCW. І почав дивитись курс 6.00 Introduction to Computer Science and Programming.

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

На замітку: Коли я кажу MIT, то маю на увазі їх курс 6, або Department of Electrical Engineering and Computer Science . Там з’явились хакери. Там була написана перша комп’ютерна гра. Там придумали Lisp. А всі інші їх факультети майже нікому невідомі…

І по цьому їхньому курсу, я вирішив вивчати Пайтон, бо крім того, професор Ерік Ґрімсон, казав, що метою курсу, є навчитись думати, як програміст, вміти писати програми, читати чужі програми, і знати межу своїх можливостей.

Опис курсу:

This subject is aimed at students with little or no programming experience. It aims to provide students with an understanding of the role computation can play in solving problems. It also aims to help students, regardless of their major, to feel justifiably confident of their ability to write small programs that allow them to accomplish useful goals. The class will use the Python™ programming language.

Що мені сподобалось в них:

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

Ось такі в них лекції.
Ну, аудиторії в них гарні, але то таке.
І хоча лекції ведуться англійською, я розумію більше, ніж наші українською. Як тільки з’являється незнайоме слово, його зміст одразу пояснюють. (Хоча хто знає що я скажу після n-тої лекції)

Одним словом, в них класно. Але можна зробити так, що в нас буде ще краще. Питання тільки в тому хто цим займеться? Я чи що?

Written by bunyk

Жовтень 30, 2009 at 02:35

Опубліковано в Нещоденник

Tagged with освіта

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

Конспекти 2. Спроба експорту.

Кількість коментарів - 8

Сьогодні я вирішив повторити вчорашній експеримент. Хоча на парі було холодно, пальці мерзли, і набиралось важко. Але все таки, я навіть деколи встигав набирати з майже з тою швидкістю з якою він (Викладач) говорить. (Він давав фору, коли писав по дошці ключові слова). Швидкість формул в мене трохи більша.

Правда це все через те, що я пишу в дивному псевдокоді. Але зате його потім можна легко перетворити в будь-який інший формат.

Правда не зовсім легко, бо мій псевдокод не сильно формальний, і ще багато речей треба робити руками. Але дещо було швидко:
:'<,'>s/!def/<strong>Означення<\/strong>
:'<,'>s/|=/\models
:'<,'>s/.../\ldots

Як приблизно воно має виглядати:

Системне програмування

вівторок, 27 жовтня 2009 10:50:06 +0200

Мінімізація скінченних автоматів (детермінованих)

Існує алгоритм вилучення тупикових станів
вилучення недосяжних станів
Побудови мінімального автомата

Означення
Два стани називаються k-еквівалентними, якщо для ланцюжка
$x, |x| \leq k$
$(q_1,x) \models ^* (q_1,\varepsilon)$
$(q_2,x) \models ^* (q_{f_2},\varepsilon)$
або ні.

Тобто якщо за k-кроків ми попадаємо в заключні конфігурації, або не в заключні (але одночасно).

Алгоритм побудови класів еквівалентних станів для скінченного автомата

0. Спочатку розбиваємо всі стани на два класи $Q\setminus F, F$
…
i. На і-тому кроці ми отримаємо систему множин.
і+1. На наступному кроці ми кажемо що стани залишаються еквівалентні, якщо для будь-якого символа вони переходять в стани з одного класу. Інакше вони потрапляють в різні класи еквівалентності.

(n-2) еквівалентність дає можливість побудувати систему станів.

Програмування скінченних автоматів (детермінованих)

Нагадаємо діаграму переходів скінченного автомата для цілочислових констант. //(Знайти малюнок!)

Нехай слово знаходиться у вхідному файлі. Тоді достатньо написати функцію з таким фрагментом коду:
(розписує код для скінченного автомата, який там намальований)

int g=0; int c;
while ((c=getchar())!=eof)
	switch(q)
	{
		case 0: if(c&gt;='1'&amp;&amp;c&lt;='9') { q=3; break; }
						if (c== '\emptyset') {q=1; break; }
						myerror();
		....
		case 3: if(c&gt;='0'&amp;&amp;c&lt;=9) {q=3; break; }
		ну, і так далі.
				
	}
	if(q=='1'||q=='3' ... )  // ok
		else ; //error

Цей стиль програмування має великий плюс – ми читаємо тільки по одному символу, і тільки раз. За допомогою getchar.

Далі, якщо ми навчились програмувати маленькі автомати, для нашої лаболаторної потрібно розробити лексичний аналізатор.

Методика програмування лексичних аналізаторів на основі скінченних автоматів

Коли ми виписуємо класи лексем, то множина всіх лексем – об’єднання цих класів.

Малюнок1.

Таким чином ми можемо зобразити діаграму переходів ДСкА який розпізнає лексеми мови C. ПРограма такого автомата виливається в 200-300 рядків тексту. За дві години програмується, якщо на побудову автомата було потрачено годину.

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

Скінченні автомати та праволінійні граматики

Означення
$G=$ називається праволінійною, якщо $P: A_i \to \omega A_j A_i, A_j \in N$
$A_i \to \omega\ \ \omega \in \Sigma^*$

Для довільної праволінійної граматики G можна побудувати автомат M, такий що L(M)=L(G).
Твердження конструктивне, тому пробуємо довести:

$A_i \to \omega A_i$

$\omega = a_1, a_2, \ldots a_p$

$A_i \to a_1,\underbrace{a_2,\ldots,a_p,A_j}_{B_1}$
$A_i \to a_1B_1$
$B_1 \to a_2 B_2$
$\ldots$
$B_{p-1} \to a_pA_j$

де $B_1,\ldots, B_n$ – нові нетермінали.

$A_i \to a_1,a_2, ... a_p$
$A_2 \to a_1B_1$
$B_p \to \varepsilon$

Тепер, спробуємо побудувати скінченний автомат. Як імена станів скінченного автомата M візмемо нетермінали перетвореної граматики. Тобто якщо взяти діаграму переходів, то всі вершини – нетермінали.

$\sigma: A_i \to aB_j$ То на діаграмі переходів це буде $A_j \xrightarrow{a} B_j$ $B_j \in (A_j,a)$

$A_j \to \varepsilon => A_i \in F$

S-аксіома – ім’я початкового стану на діаграмі.

Тепер треба показати, що за n кроків безпосереднього виведення ланцюжка, ми відпрацюєм нашим автоматом. Є ланцюжок $\omega \in L(G)$ тепер спробуємо з конфігурації $(q_0, \omega) \models * (q_1,\varepsilon)$

вівторок, 27 жовтня 2009 11:20:49 +0200 перерва вівторок, 27 жовтня 2009 11:26:46 +0200

$(q_0, a \omega) \models (A_j,\omega) =>$

$S => a A_j => \ldots => \omega$

А якщо $\omega$ виводиться, то існує скінченна послідовність кроків, яка приведе в заключний стан.

для довільного СкА M можна побудувати праволінійну граматику G, таку що, L(M) = L(G), і навпаки.

Тобто ми показали, що механізм на синтез за потужністю еквівалентний механізму на аналіз.

Зображення скінченних автоматів та граматик страждає тим, що ми повинні виписувати формальні множини, що таке множина станів, конкретизувати поняття. Можна спробувати ці множини позначати якимись виразами. В ТП, ці вирази називаються регулярними.

Регулярні множини та вирази

Означення
Рeгулярна множина – це $\emptyset , {\varepsilon}, {a},$ // це я вже записав на CybWiki. Як виявилось після леції, регулярні множини, і регулярні мови це одне і те ж.

Регулярні вирази позначають регулярні множини. Таким чином що порожня множина позначається нулем. // теж CybWiki Ура Карнаух!

Вирази зустрічаются в алгебрах, тому ведем мову про Алгебру регулярних виразів. Сигнатура – $\{+,\cdot,^*\}$ .

Тотожності в алгебрі регулярних виразів

За тотожностями можна оптимізувати регулярні вирази.

P+0=0+p=p
p+p=p
p+q=q+p
(r+q)p=rp+qp
p*+p=p*
0*=\varepsilon

Рівняння в алгебрі регулярних виразів

Називається рівняння виду: X=aX+b, де a,b – РВ. Воно може мати нескінченну кількість розв’язків, або 1, який не залежить від виду a,b. Той що не залежить від виду називаєься мінімальним. Його вид: X=a*b. Перевіримо що це розв’язок підставивши в рівняння:

$a^*b = (aa^*b+b) = (aa^*+ \varepsilon ) b = (\varepsilon +a( \varepsilon +a + a^2 \ldots ))b = a^*b$

Системи рівнянь в алгебрі регулярних виразів:
$\begin{cases} X_1=a_{11}X_1+a_{12}X_2+....+b_1 \\ X_2=a_{21}X_1+a_{22}X_2+....+b_2 \\ \ldots\end{cases}$

Де $a_{i,j} , b_i$ – регулярні вирази. Розв’язується методом Гауса. // Жах! поки не взнаю нащо воно треба, записувати не буду. Крім того я ж знаю метод Гауса.

Існує теорія неруxомої точки та мінімального рішення. //Прогуглити

Давайте візьмемо праволінійну граматику
$A_j \to \omega A_j$
$A_i \to \omega$
, і випишемо її в такому вигляді:
$S \to a_{11} S | a_{12} A_1 | \ldots A_{1n} A_n-1 | \omega_1$
Якщо правила $S \to a_{1j} A_i$ відсутньє, то $a_1j=0$

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

Розв’язок системи рівнянь по змінній S дає нам регулярний вираз, який позначає множину слів які породжуються праволінійною граматикою. // Ну от я знаю нащо воно треба

Залишилось від регулярного виразу дійти до скінченного автомата.

СкА=>Праволійні граматики => Регулярні вирази => СкА

Обчислення (інтерпритація) регулярних виразів. В результаті виходить автомат.
Їх зручно обчислювати коли вони в формі ПОЛІЗ.
Наприклад (a+b*)c
$a b * + c \cdot$
НУ, і як завжди через стек: // я пам’ятаю

В стеку знаходяться автомати. // гг. Треба ще вивчити як робляться операції на автоматах.

вівторок, 27 жовтня 2009 12:09:52 +0200

Вихідний код:

(підсвітка C++, поки не написав свою)

Системне програмування
вівторок, 27 жовтня 2009 10:50:06 +0200

= Мінімізація скінченних автоматів (детермінованих) =

#Існує алгоритм вилучення тупикових станів
#вилучення недосяжних станів
#Побудови мінімального автомата

!def
Два стани називаються k-еквівалентними, якщо для ланцюжка
x, |x| \leq k
(q_1,x) |=* (q_1,\epsilon)
(q_2,x) |=* (q_{f_2},\epsilon)
або ні.

Тобто якщо за k-кроків ми попадаємо в заключні конфігурації, або не в заключні (але одночасно).

== Алгоритм побудови класів еквівалентних станів для скінченного автомата ==
0. Спочатку розбиваємо всі стани на два класи Q\setminus F, F
…
i. На і-тому кроці ми отримаємо систему множин
і+1. На наступному кроці ми кажемо що стани залишаються еквівалентні, якщо для будь-якого символа вони переходять в стани з одного класу. Інакше вони потрапляють в різні класи еквівалентності.

(n-2) еквівалентність дає можливість побудувати систему станів.

== Програмування скінченних автоматів (детермінованих) ==
Нагадаємо діаграму переходів скінченного автомата для цілочислових констант. //(Знайти малюнок!)

Нехай слово знаходиться у вхідному файлі. Тоді достатньо написати функцію з таким фрагментом коду:

(розписує код для скінченного автомата, який там намальований)

int g=0; int c;
while ((c=getchar())!=eof)
    switch(q)
    {
        case 0: if(c>=’1′&&c<=’9′) { q=3; break; }
                        if (c== ‘\emptyset’) {q=1; break; }
                        myerror();
        ….
        case 3: if(c>=’0′&&c<=9) {q=3; break; }
        ну, і так далі.

    }
    if(q==’1′||q==’3′ … )  // ok
        else ; //error

Цей стиль програмування має великий + – ми читаємо тільки по одному символу, і тільки раз. getchar.

== Методика програмування лексичних аналізаторів на основі скінченних автоматів ==
Коли ми виписуємо класи лексем, то множина всіх лексем – об’єднання цих класів.

Малюнок1.

= Скінченні автомати та праволінійні граматики =
!def
G=<N,\Sigma,P,S> називається праволінійною, якщо P: A_i -> \omega A_j A_i, A_j \in N
A_i -> \omega \omega \in \Sigma^*

A_i \to \omega A_i

\omega = a_1, a_2, \ldots a_p

$$A_i \to a_1,\underbrace{a_2,\ldots,a_p,A_j}{B_1}
A_i \to a_1B_1
B_1 \to a_2 B_2
\ldots
B_{p-1} \to a_pA_j$$

де B_1,\ldots, B_n – нові нетермінали.

$A_i \to a_1,a_2, … a_p
A_2 \to a_1B_1
B_p \to \epsilon$

$\sigma: A_i \to aB_j$ То на діаграмі переходів це буде $ A_j \xrightarrow{a} B_j$
B_j \in (A_j,a)

A_j \to \epsilon => A_i \in F

S-аксіома – ім’я початкового стану на діаграмі.

Тепер треба показати, що за n кроків безпосереднього виведення ланцюжка, ми відпрацюєм нашим автоматом. Є ланцюжок \omega \in L(G) тепер спробуємо з конфігурації (q_0, \omega) |=* (q_1,\epsilon)

вівторок, 27 жовтня 2009 11:20:49 +0200
перерва
вівторок, 27 жовтня 2009 11:26:46 +0200

(q_0, a \omega) |= (A_j,\omega) =>

S => a A_j => … => \omega

А якщо \omega виводиться, то існує скінченна послідовність кроків, яка приведе в заключний стан.

для довільного СкА M можна побудувати праволінійну граматику G, таку що, L(M) = L(G), і навпаки.

Тобто ми показали, що механізм на синтез за потужністю еквівалентний механізму на аналіз.

Зображення скінченних автоматів та грамати страждає тим, що ми повинні виписувати формальні множини, що таке множина станів, конкретизувати поняття. Можна спробувати ці множини позначати якимись виразами. В ТП, ці вирази називаються регулярними.

= Регулярні множини та вирази =
!def
Рeгулярна множина – це \emptyset , {\epsilon}, {a}, // це я вже записав на CybWiki

Регулярні вирази позначають регулярні множини. Таким чином що порожня множина позначається нулем. // теж CybWiki Ура Карнаух!

Вирази зустрічаются в алгебрах, тому ведем мову про Алгебру регулярних виразів. Сигнатура – {+,\cdot,*}.

== Тотожності в алгебрі регулярних виразів ==
За тотожностями можна оптимізувати регулярні вирази.

#P+0=0+p=p
#p+p=p
#p+q=q+p
#(r+q)p=rp+qp
#p*+p=p*
#0*=\epsilon

== Рівняння в алгебрі регулярних виразів ==
Називається рівняння виду: X=aX+b, де a,b – РВ. Воно може мати нескінченну кількість розв’язків, або 1, який не залежить від виду a,b. Той що не залежить від виду називаєься мінімальним. Його вид: X=a*b. Перевіримо що це ррозв’язок підставивши в рівняння:

a*b=(aa*b+b)=(aa*+\epsilon)b=(\epsion+a(\epsilon+a+a^2...))b=a*b

Системи рівнянь в алгебрі регулярних виразів
X_1=a_{11}X_1+a_{12}X_2+….+b_1
X_2=a_{21}X_1+a_{22}X_2+….+b_2
….

Де a_{i,j} , b_i – регулярні вирази. Розв’язується методом Гауса. // Жах! поки не взнаю нащо воно треба, записувати не буду. Крім того я ж знаю метод Гауса.

Існує теорія нерузомої точки та мінімального рішення. //Ооо, як замерзли пальці. Я вже мимо клавші попадаю

давайте візьмемо праволінйну граматику
A_j \to \omega A_j
A_i \to \omega
, і випишемо її в такому вигляді:
S \t a_11 S | a_12 A_1 | … A_1n A_n-1 | \omega_1
Якщо правила S \to a_1j A_i відсутньє, то a_1j=0

Розв’язок системи рівнянь по змінній S дає нам регулярний вираз, який позначає множину слів які породжуються праволінійною граматикою. // Ну от я знаю нащо воно треба

Залишилось від регулярного виразу дійти до скінченного автомата.

СкА=>Праволійні граматики => Регулярні вирази => СкА

Обчислення (інтерпритація) регулярних виразів. В результаті виходить автомат.
Їх зручно обчислювати коли вони в формі ПОЛІЗ.

Наприклад (a+b*)c
a b * + c \cdot
НУ, і як завжди через стек: // я пам’ятаю

В стеку знаходяться автомати. // гг. Треба ще вивчити як робляться операції на автоматах.

вівторок, 27 жовтня 2009 12:09:52 +0200

Written by bunyk

Жовтень 27, 2009 at 15:59

Опубліковано в Інструменти, Конспекти, Нещоденник, Розмітка

Tagged with зміни, LaTeX, Vim

Vim і конспекти

Кількість коментарів - 14

Все тече, все змінюється. І хоча я дещо консервативний, і навіть дотепер пишу чорнильною ручкою, але все таки маю сторону яка постійно шукає нового.

Сьогодні на лекції з ТП як завжди підключав проектор, але презентацію показували з ноутбука Стружа^[1]. Тому мій ноутбук виявився незайнятим, і включеним в резетку. Волею випадку було відкрито робоче середовище:

Процес конспектування

Прочитати решту цієї замітки »

Written by bunyk

Жовтень 26, 2009 at 15:01

Опубліковано в Інструменти, Конспекти, Нещоденник, Розмітка

Tagged with освіта, цілі, Vim

Цікаві формули і картинки

з коментарем

Я мав би сидіти, писати курсову, чи ще щось корисне, але замість цього сиджу і граюся зі своєю програмкою. І єдине виправдання яке я собі придумав – ну яка курсова може бути без гарних картинок. І хоча вони в мене поки що ще не дуже, але добре було б мати формули для цікавих множин. Бо хто не бачив якогось там тора?

А як зробити якусь цікаву фігуру? Застосовувати до відомих фігур перетворення. Цікавими є не афінні перетворення, і бажано навіть не гомеоморфні (хоча з визначенням гомеоморфізму в моїй програмі є проблеми. Відкритий відрізок гомеоморфний всій числовій прямій, а закритий – ні, так як гомоморфізм зберігає компактність. А в мене поняття замкненості множини взагалі не існує.)
Прочитати решту цієї замітки »

Written by bunyk

Жовтень 24, 2009 at 14:52

Опубліковано в Графіка, Кодерство

Tagged with графіка, математика

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

Archive for Жовтень 2009

І хоча ми не MIT, та все ж…

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

Конспекти 2. Спроба експорту.

Системне програмування

Мінімізація скінченних автоматів (детермінованих)

Алгоритм побудови класів еквівалентних станів для скінченного автомата

Програмування скінченних автоматів (детермінованих)

Методика програмування лексичних аналізаторів на основі скінченних автоматів

Скінченні автомати та праволінійні граматики

Регулярні множини та вирази

Тотожності в алгебрі регулярних виразів

Рівняння в алгебрі регулярних виразів

Вихідний код:

Vim і конспекти

Цікаві формули і картинки

Стараюсь вписатись в рамки:

Останні публікації

Літописи

Варто читати

Друзі

Баннери

Хмарка тем

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