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

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

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

leave a comment »

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

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

Бази даних

четвер, 29 жовтня 2009 10:41:06 +0200

КП – код постачальника
КД – код деталі
Т –

Ця реляція не знаходиться в другій нормальній формі.
?Що таке нормальна форма? І що значить друга?

Т | КП | КД | місто

?Аномалія вилучення
?Аномалія вставки

Є засоби щоб з цим боротись і не переходити до другої нормальної форми.

Наприклад аномалія вставки. Коли ми вводимо кортеж, то по місту вводимо значення NULL, і вводимо його тільки тоді коли дізнаємось де проживає T1.

З іншого боку, якщо взяти аномалію вилучення, ми ставимо NULL в тих реляціях які мають зв’язки з нашою. Але перед тим, дивимось, чи воне не зв’язані з ніякою іншою,

Бовсунівський: Переваги другої нормальної форми?
Кулябко: Нехай… //Ніфіга не розумію. Треба буде частіше на пари ходити.

Th: Хіза (Heath)

Якщо для деякої реляції $R$ існує залежність $M_1 \to M_2$ де $M_1$ і $M_2$ – список атрибутів, то реляція $M$ може бути декомпонована, на дві реляції: $R=R[M_1,M_2][M_1 \circ M_1] R[M_1,\overline{M_2}]$ без втрат.

Якщо реляція складається з трьох атрибутів R(A,B,C) і $A \to B$, то ми декомпонуємо її на дві реляції: R[A,B] , R[A,C].

Доведення цієї теореми в повному обсязі наводитись не буде, можна читати книжку Ульмана. Розкажу загальну концепцію.

Суть в тому, що ідея дуже проста, але дуже інтенсивно використовується на практиці. Ідея та ж сама, що я говорив про збережнення без втрат в попередньому прикладі. Тільки поза M_2 знаходяться атрибути які… // Прийдеться читати книжки.

def: 2НФп (Друга нормальна форма посилена) (Друга нормальна форма Бойса Кодда Boyce Codd).
Кажуть що реляція знаходиться в 2НФп, якщо вона знаходиться в 1НФ, і кожен атрибут функціонально повно залежить від кожного квазіключа. Тобтто знімається вимога вторинності атрибуту.

def: Транзитивна залежність
// Пропустив через Костю.

Поговоримо про третю нормальну форму. (Нормальна форма Бойса Кодда)

= NP – повні задачі =
Є задачі, які перебирають всі підмножини деякої деякої підмножини. Вони мають експоненціальну складність. А є задачі, в яких суть справи в тому, що не обов’язково проходити по всіх підмножинах, а можна вгадати потрібну гілку перебору. Такі задачі називають NP повними.


11:31:49 перерва

Оптимальною вважається декомпозиція, коли кількість реляцій найменша. На практиці стараються знайти квазіоптимальну.

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

Колись була вимога, що всі атрибути таблиці повинні бути семантично навантажені. Але потім розробники почали вводити додаткові атрибути (для ключів, і т.п.).

Завдання для контрольної буде полягати в наступному:
Дана реляція, і функціональні залежності.
Їх треба мінімізувати.
А по мінімізованих побудувати структуру третьої нормальної форми.
ДОтримуйтесь теореми Хіза.

Уточнення з проводу 2НФ. Якщо в реляції всі атрибути первинні, то вона знаходиться в другій нормальній формі.
Якщо всі квазіключі реляції складаються з одного атрибута, то вона знаходиться в 2НФ.

Анекдот з 4НФ.

Встановлення реляційної моделі, роботи Хіза , Бойса, Кодда, були пророблені за кілька років становлення реляційної алгебри. Потім щось писалося, але дослідження були незначними. Це були 70ті, тоді інтернету не було, статті друкувались довго, в союзі взагалі кілька років. І ось виходить стаття, де написано, що після 3НФ, нічого немає. А через місяць після цього конференція по БД, і на ній виступ з доповіддю, в якому говориться про 4НФ. Особливо для тих, хто був далекий від цих питань це виглядало як анекдот. Насправді все було нормально. Нормальні форми на основі функціональних залежностей, є тільки до 3НФ. А четверта вже не функціональна.

def: Багатозначні залежності.

Є табличка: { Предмет | Викладач | Курс | Підручники }
Ми не можемо за предметом чітко сказати викладача. Предмет можуть читати кілька викладачів, викладач може читати кілька предметів, підручників взагалі дофіга. Тобто я до чого веду. В такій таблиці немає функціональних залежностей.

Але деякі залежності все ж є. Викладач з історії навряд чи буде читати матан. Тому є певна обмеженість, яка створює залежність. Хоч вона не функціональна. Ну, приблизно такі залежності називають багатозначними.

Інший приклад: { КЛ | КП | рік | зарплата }
{ ПТ | гем | 1979| 180 }
{ ПТ | алг | 1979| 180 }
{ ПТ | гем | 1980| 200 }
{ ПТ | алг | 1980| 200 }
{ СД | ма1 | 1979| 250 }
{ СД | ма2 | 1979| 250 }
{ СД | ма1 | 1980| 270 }
{ СД | ма2 | 1980| 270 }
ПТ – Петренко
СД – Сидоренко

Ця таблиця має надлишок інформації, але залежностей мало. ЇЇ хочеться декомпонувати.

{ КЛ | КП } { КЛ | рік | зарплата}

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

четвер, 29 жовтня 2009 12:10:52 +0200


Друга лекція була ще страшніша, бо це були чисельні методи, з неймовірною кількістю формул. Деякі формули до сих пір не хочуть парситись. Тому якщо ваша ласка, коли побачите жовту картинку з червоним написом formula doesnt parse, подивіться альтернативний текст, може підкажете, де я помилився. Просто сил вже майже нема.

Чисельні методи

четвер, 29 жовтня 2009 12:21:21 +0200

Ми розглядали інтерполяційний поліном. Почали розглядати розділені різниці. Тепер запишемо наступні властивості.

1) Розділена різниця f(x_1,\ldots, x_k) є лінійним функціоналом від функції f. Це означає що, (\alpha_1f_1+\alpha_2f2)(x_1;\ldots;x_k) = \alpha_1f_1(x_1;x_2;\ldots;x_k)+ \alpha_2f_2(x_1;x_2;x_k)

2) Розділена різниця є симетричною функцією своїх аргументів.

Тепер будуємо таблицю.
\begin{array}{llll}   x_1 && f(x_1) && f(x_1;x_2) &&  f(x_1;x_2;x_3) \ \ldots \\  x_2 && f(x_2) && f(x_2;x_3) && \ldots \\  \vdots && \vdots && vdots && \ldots \\  x_n && f(x_n) && f(x_{n-1};x_n) &&  \ldots  \end{array}

Щоб побудувати інтерполяційний поліном в формі Ньютона, розглянемо різницю:
f(x)-L_n(x)=f(x)-\sum_{i=1}^n f(x_i) \prod_{i\neq j} \frac{(x-x_j)}{(x_i-x_j)} =  prod_{i=1}^n (x-x_i) \underbrace{\left( \frac{f(x)}{\prod_{i=1}^n (x-x_i)} + \sum_{i=1}^n \frac{f(x_i)}{x_i-x) \prod_{i\neq j} (x_i - x_j)} \right)}_{f(x;x_1;\ldots;x_n) =  f(x;x_1;\ldots;x_n) \omega_n(x)

\omega_n(x)=(x-x_1)(x-x_2)\ldots (x-x_n)

L_n(x)=L_1(x)+(L_2(x)-L_1(x))+\ldots + (L_n(x)-L_{n-1}(x))

L_m(x)-L_{m-1}(x)

x_i; i=1,..., m-1

L_m(x_i)=f(x_i) L_{m-1}(x_i)=f(x_i)
L_m(x_i) - L_m(x_{i-1})=0, i=\overline{1,...,n-1}
L_m(x_m) - L_{m-1}(x_m)=A_{m-1}\cdot \omega_{m-1} (x_m)

L_m(x_m)-L_{m-1}(x_m)=f(x_m)-L_{m-1}(x_m)

n=m-1; x=x_m

f(x)-L_{m-1}(x_m)=f(x_1;x_2;...;x_m)\omega_{m-1}(x_m)

A_{m-1}=f(x_1;x_2;...;x_m) (7)

отже, підставимо в многочлен:
P_n(x)=f(x_0)+f(x_1;x_2)(x-x_1)+ f(x_1;x_2;x_3)(x-x_1)(x-x_2)+...+ f(x_1;x_2;...;x_m)(x-x_1)(x-x_2)...(x-x_{m-1}) (8)

Це інтерполяційний поліном у формулі Ньютона. Дана інтерполяційна формула називається ітерполяційною формою “вперед”.

Є ще інтерполяційна формула “назад”. Вона виглядає так:
P_n(x)=f(x_n)+f(x_{n-2};x_n)(x-x_1) +f(x_{n-2};x_{n-1};x_n)(x-x_{n-1})(x-x_n) + ... + f(x_1;x_2;...;x_n)(x-x_n)(x-x_{n-1})...(x-x_2) (9)

Тепер ще раз повернемось до порівняльного аналізу:

Якщо ми з вами додамо ще один вузол до (8), то в нас додасться тільки один доданочок. А таблиці тільки одни рядок.

І ще ми дістанемо

f(x)-L_n(x)= \frac{f^{(n)}(x)\cdot \omega_n(x)}{n!} (10)

ЯЧкщо порівняти (10) і (1), то можна зробити висновок, що
f(x;x_1;...;x_n)=\frac{f^{(n)}(x)}{n!}

Схема Ейткена. ЇЇ використовують для спрощення обчислювальної процедури. Щоб її розглянути

Хай
x_i \in [a,b]
f(x_i) i=\overline{1,n}
f(x) x\neq x_i

|x-x_i|
L_{(k)}(x) = f(x_k)
L_{1,...,n)(x)=L_n(x) – інтерполяційний поліном степеня n-1.

L_{(k,k+1,...,l,l+1)}(x) = \frac{( L_{(k+1,...,l+1)}(x)(x-x_k) - L_{(k,...,l)}(x)(x-x_{l+1}) )}{(x_{l+1}-x_n)} (12)

Використовуючи формулу (12) будуємо наступну:

\begin{array}{lll}  L_1(x)		&& L_{(1,2)}(x)		&& L_{(1,2,3)} (x)  L_2(x)		&& L_{(2,3)}(x)		  \vdots		&& \vdots  L_{n-1}(x)  &&   L_n(x) 		&&  \end{array}

Оскільки в нас деякі величини є достатньо малими, ми можемо записати, що
f(x;x_1;...;x_m) \equiv \frac{f^{(m)}(x)}{m!} \equiv f(x_1;...;x_m;x_{m+1} )

Якщо нам потрібно обчислити значення функції f, в x, з точністю \epsilon, ми в кожній точці можемо контролювати, дійшли ми до даної точності, чи ні.

\epsilon_1=L_2(x)-L_1(x) \epsilon_1<E
\epsilon_2=L_3(x)-L_2(x) \epsilon_2<E

Тепер запишемо наступну тему:

Розділені різниці, та формули інтерполяції з кратними вузлами.

Постановка задачі наступна:

Нехай в точках x_i \in [a,b] задана функція $f \in C^{(S)}[a,b]$
f(x_1), f'(x_1), ... , f^{m_1-1} (x_1)
...
f(x_n), f'(x_n), ... , f^{(m_n-1)} (x_n)

будуємо g_s(x), який відповідає наступним умовам:
f(x_1)=g_s(x_1), f'(x_1)=g'(x_1), ... , f^{(m_1-1)}(x_1)=g_s(x_1)
.....
f(x_n)=g_s(x_n), f'(x_n)=g_s'(x_n), ... , f^{(m_n-1)}(x_n) - g_s(x_n)

13:07:16 перерва! 13:19:22

Ітертоляційна задача типу Ерміта. Якщо у вузлах задані тільки значення без похідних, називають інтерполянтами типу Лагранжа. Вони співпадають з інтерполяційною формулою типу Ньютона. Її інколи отримують за рядом Тейлора, але цей підхід який я дала вам на попередній півпарі, зручніше використовувати на практиці.

Задача типу Ерміта. не тільки значення, але й їх похідні до певного порядку включно. постановка вище.

Приклад ітерп. зад. типу Ерміта:

f(0), f'(0), f''(0)
f(1)
f(2), f'(2)
f(3), f'(3), f''(3), f'''(3)

Існує ще інт. зад. типу Ерміта-Бергофа.
Постановку в загальному випадку складно виписати. Як приклад наступний:
f(x_0), f'''(x_0)
f'(x_1), f''(x_1), f^{(10)}(x_2)
f(x_2), f^{(5)}(x_2)

Припустимо що існує ще один розв’язок задачі (1). Тобто \exists p_s(x) \neq g_s(x)

Тепер, якщо ми з вами розглянемо поліном, Q_s(x)=g_s(x)-p_s(x)
він задовольнить такі умови:

Q_s(x_1)=0, Q_s'(x_1)=0, ... ,Q_s^{(m_1-1)}(x_1) =0
... ...
Q_s(x_n)=0, Q_s'(x_n)=0, ... ,Q_s^{(m_1-1)}(x_n) =0

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

Тепер доводимо існування інтерполяційного поліному (називається інтерполянтом Ерміта). Існування випливає з побудови. Візмемо вузли x_{ij}^\epsilon \xrightarrow{\epsilon \to 0} x_i.

x_{ij}^\epsilon = x_i + (j-1) \epsilon

x_{11}^\epsilon \leq x_{12}^\epsilon \leq ... \leq x_{1m}^\epsilon \leq ... \leq x_{nm_n}^\epsilon

\begin{array}{llll}  x_{11}^\epsilon &&  f(x_{11}^\epsilon) &&  x_{12}^\epsilon &&  f(x_{12}^\epsilon) &&  x_{13}^\epsilon &&  f(x_{13}^\epsilon) &&  ... && ... && ... &&  x_{1m_1}^\epsilon && f(x_{1m_1}^\epsilon) &&  ... && ... && ... &&  x_{nm_n}^\epsilon  && f(x_{nm_n}^\epsilon) &&  \end{array}

P_n(x)=f(x_{11}^\epsilon) + f(x_{11}^\epsilon \cdot x_{11}^\epsilon)(x-x_{11}^\epsilon) + f (x_{11}^\epsilon \cdot x_{12}^\epsilon \cdot // Здаюсь… потім в когось перепишу

Перш ніж спрямувати до нуля, на підставі формули (11) пишемо:
f(x_{i2};...;x{im})=\frac{f^{(m-l)}(x^\epsilon_{im_l}}{(m-l)!}

\lim_{\epsilon \to 0} f(x^\epsilon_{ie};...;x^\epsilon_{im})=f(x_i;x_i;...;x_i) = \frac{f^{(m-l)}(x_i)}{(m-l)!}

f(\underbrace{x_i;x_i;...;x_i}_{(p+1)}) = \frac{f^{(p)}(x_i)}{p!}

Після того, як \epsilon \to 0, таблиця розділених різниць буде мати такий вигляд:

// Та йопт! Взяти книжку. Латех в таких таблицях безсильний.
\begin{array}{llll}  x_1 &&  f(x_1) &&  x_2 &&  f(x_1) &&  x_1 &&  f(x_1) &&  ... && ... && ... &&  x_{1m_1}^\epsilon && f(x_{1m_1}^\epsilon) &&  ... && ... && ... &&  x_{nm_n}^\epsilon  && f(x_{nm_n}^\epsilon) &&  \end{array}

І ми нарешті дійшли до вигляду інтерполяційного поліному:
P_n(x)=f(x_1) + f(x_1\cdot x_1)(x-x_1) + f (x_1 \cdot x_1\cdot // Той поліном на якому я здався.

P_n(x)= \sum_{i=1}^{m_1} \frac{f^{(i-1)}(x_1)}{(i-1)!} (x - x_1) ^{i-1} + O(|x-x_1|^{m_1}) (6)

далі можна написати
P_n(x)= \sum_{i=1}^{m_k} \frac{f^{(i-1)}(x_k)}{(i-1)!} (x - x_k) ^{i-1} + O(|x-x_k|^{m_k}) (7)

На цьому ми з вами закінчимо. 13:54:37

Початок обробки: 14:14:29
Кінець обробки1: 14:23:58

Висновки:

  1. Записувати можна і складні лекції на великій швидкості, але треба вдосколалити знання нюансів LaTeX.
  2. Переноска – це те що треба студенту щоб всидіти на лекції.
  3. Викладачі на твою переноску, і ноутбук реагують адекватно (тобто взагалі не реагують). Вони все одно раді бачити тебе на парі.
  4. Записувати економіку напевне взагалі буде як два пальці…
  5. І основне – треба більше формалізувати мову запису. Можливо з досвідом я навіть зможу зразу публікувати на CybWiki.
  6. І хоча мало хто ще зрозумів, що структура даних в форматі вікіпедії нагадує формат знань в нашому мозку (я про зв’язки між статтями), тому редагування її доволі надійно впаює знання в голову, але люди кажуть “Вау! Ти встиг записати? Я ручкою ледве встиг.” Сподіваюсь, що через деякий час, я не буду один з Улідтко
  7. Принаймі кількість ноутбуків з Linux почала переважати кількість з Windows. (я про тих, хто прийшов на лекцію).
  8. Вибачте за такий великий і негарний пост. Я буду вдосконалюватись.
  9. Для малювання наприклад скінченних автоматів мені не підходить ні Inkscape (xoча я й поставив для нього підтримку LaTeX, ні Dia (який взагалі про LaTeX не чув). Може написати свою програму? Скрипт до InkScape який вставляє TeXText написаний на Пайтоні, і не дуже довгий. Правда ще треба почитати специфікацію SVG, і вивчити GTK. А сесія все ближче… А писати щось крім курсової мені не сильно хочеться? Народ, може хто з вас візьме таку тему курсової? Вона потрібна. Набагато потрібніша ніж вся ця наша математика, бо буде корисна навіть простим смертним.
  10. Ах, мало не забув. Заохочується, копіювання, тиражування, і вдосконалення цих конспектів. Хочете, можемо завести колективний блог потоку?
Advertisements

Written by bunyk

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

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

Tagged with , ,

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: