Вопрос 31. Основные алгоритмы сортировки и их сложность.

а) сортировка вставками

Простые вставки: К₁K₂…K_j-1 – упорядоченно. Кj сравнивается с K_j-1, K_j-2 и т.д. до тех пор, пока не найдется i: K_i K_j K_i+1. Время работы 2,25N²+7.75N

Бинарные вставки: Сравниваем K_j с K_j/2. Время работы Nlog₂N

б) обменная сортировка

Метод пузырька: К1 сравниваем с К2 и меняем R1и R2, если ключи не упорядочены. При многократном повторении Эл-ты больше всплывают на поверхность. Время работы 7,5N2+0.5N+1

в)посредством выбора

Сложность алгоритма: 2.5N²+3.5N

Выигрыш: производится мало пересылок данных

г) подсчетом

Сравниваем K_j с K_i , 1j<i

Счетчики С[1],…C[N]

Ki<Kj ==> увелич. C[j] на 1

KiKj ==> увелич. C[i] на 1

C[j] указывает на то место, на которое должна быть расположена запись Rj.

Время работы: N(N-1) Порядка N²: 3N²+10N

Вопрос 32. Детерминированные и недетерминированные конечные автоматы, связь м/у ними.

Детерминированный конечный автомат

M=<Q,∑,t,q₀,F,P> где

Q-непустое конечное мн-во состояний

∑-Конечный входной алфавит

t:Qx∑→Q – ф-ия перехода

q₀ Є Q – начальное состояние

F (подмн-во) Q – мн-во заключ. Состояний

p:Qx∑→∑ - функция выходов

W Є W(∑), W=S₁…S_n – входная посл-ность

Начиная из состояния q₀, если q_i=f(q₀,s₁), то под действием

входного действия s₁ автомат переходит в состояние q_i.

Если (q₀,s₁₎ Є δ_p, то при переходе в состояние q_i, на

выходе появляется p(q₀,s₁). f(q_i,s₂)=q_j => осуществляет

переход в состояние q_j c выводом значения p(q_i,s₂)

Процесс продолжается до символа S_n, или до тех пор

пока не встретится символ  ∑

Входная посл-ть W наз. представимой автоматом М, если

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

принадлежит множеству F.

Недетерминированные конечные автоматы

t:Qx∑→ρ(большая)(Q)

f(q_i,s) (подмножество) Q

Возникает выбор состояния: куда идти дальше

A(M) – множество слов, представимых автоматом M.

M=<Q, ∑,t,q_0,F>

W ЄW(∑), W=S₁…S_n

T(W)-мн-во всех заключительных состояний, кот.

дlостижима под действием входной посл-ти W.

T(_/\_)={q₀}

T(W’,S_k)=Uf(q,s_k) qЄT(W’)

W представимо в M, если T(W)∩F#0

A(M)={W|T(W) ∩ F#0}

Теорема: Для любого недетерминированного к.а. М1

сущ. детерм. к.а. М2, т.ч. А(М1)=А(М2)

Док-во: M1=<Q₁, ∑₁,t₁,q₀,F₁>; M2=<Q₂, ∑₂,t₂,q₀,F₂>

Q₂= ρ(большая)(Q₁)={x|x (подмн-во) Q₁}

∑₂=∑₁, q₀’={q₀}

f₂(q₀’,s₁)=мн-во всех состояний в f₁(q₀,s₁)

f₂(f₂(q₀’,s₁),s₂)=мн-во всех состояний в кот можно попасть

из f₁(q₀,s₁) под действием S₂

F₂-подм-во Q₁ содержания символа из F₁ и является

результатом применения функции t₂.

Вопрос 33. Неклассические логики

Тезис Гильберта. Любое док-во можно провести в рамках ИП.

Пропозициональные логики.

1. Многозначные логики.

 - ф-ла ИВ, C  R

 [0, 1]

f() = C, 0C1

 степень достоверности высказыв.

f(₁₂) = min{ f(₁), f(₂)}

 = max

f(₁) = 1-f(₁)

2. Теория вероятностей.

 - ф-ла ИВ, Pr() = c, 0C1

Pr – вероятность наступления события 

3. Модальная логика.

Модальность – св-во суждения характеризующ. степень его достоверности

 (необходимо)

ИВ+связки

 (возможно)

  

Аксиомы: 1) если |-  док-ма, то |- ; 2) |- ()

4. Индуиционистская логика

N |=x (x)?

найдется nN |= (n)