Формальные языки и порождающие грамматики

 

Итого: произведено    сравнения (S =   )

 

 

 

Методом турниров с  выбыванием:

Step_1

 

 

 

 

 

 

 

Step_2

 
Step_3

 

 

 

 

 

 

Step_4

 

 

 

 

 

 

 

Step_5

 
Step_6

 

 

 

 

 

 

Step_7

 

 

 

 

 

 

 

Step_8

 
STEP_9

 

 

 

 

 

 

STEP_10

 

 

 

 

 

 

 

 

STEP_11

 

 

 

 

 

Итого произведено   сравнений (S=   )

 

Методом деревьев сравнений:

Исходя из условия задания строим бинарное дерево

145

182

534

168

082

039

194

211

200

013

135

 

 

 

 

 

 

 

 

Итого: произведено    сравнения (S=   )

 

Метод	Tmax	Число выполненных сравнений S	Δ=Tmax-S
пузырька	=
турниров	(n-1)+(n-1)log2n≈
деревьев сравнений	n2=

Для заданной последовательности наиболее предпочтителен

 

Найдём в отсортированной последовательности значений реквизита значение, указанное в позиции №6 исходного задания(039)

 

145

182

534

168

082

039

194

211

200

013

135

 

а) используя метод простого перебора:

суть  метода состоит в том, чтобы поочерёдно сравнивать значение для поиска с  каждым элементом последовательности до первого совпадения, или пока массив не закончится, что будет  означать отсутствие этого элемента.

 

Step_1

013

039

082

135

145

168

182

194

200

211

534

039

Step_2

013

039

082

135

145

168

182

194

200

211

534

039

Значение  найдено, поиск завершён: произведено 2 сравнения.

 

б) используя метод двоичного (дихотомичного) поиска:

суть метода в том, что некоторый упорядоченный набор данных (список) разделяется на две части и операция сравнения всегда выполняется для среднего элемента списка: после сравнения одна половина списка отбрасывается и операция выполняется для оставшейся половины и т.д.

 

Step_1

013

039

082

135

145

168

182

194

200

211

534

039

 

Step_2

013

039

082

135

145

039

 

 

Step_3 

013

039

082

 

 

039

 

Значение найдено, поиск завершён: произведено 3 сравнения.

 

в) используя  метод деревьев сравнений

суть  алгоритма: поиск начинается с корня  дерева, искомое значение сравнивается с узлом, если они равны, поиск  завершён, если оно больше, то переходим  в правую ветвь, иначе в левую.

Для поиска воспользуемся построенным ранее  деревом

 

 

 

 

 

Step_1:  039 < 145

Step_2:  039 < 082

Step_2:  039 = 039

 

Значение  найдено, поиск завершён: произведено 3 сравнения.

 

Метод	Тср	Число выполненных сравнений S
простого перебора	=	2
двоичного поиска	≈	3
деревьев сравнений	1,39*log2 n ≈	3

 

В моём задании  наиболее эффективным оказался метод

 

 

 

Список литературы.

 

1. Информатика в экономике: Учебное пособие / Под ред. Б.Е. Одинцова, А.Н. Романова. – М.: Вузовский учебник, 2008.
2. Информатика. Базовый курс / К.Л. Симонович и др. – СПб: Питер, 2001. – 640 с.
3. Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д.. – Введение в теорию автоматов, языков и вычислений, 2-е изд..: пер. с англ. – М.: издательский дом «Вильямс», 2002. – 528 с.
4. Пентус А.Е., Пентус М.Р. – Теория формальных языков: Учебное пособие. – М.: Издательство ЦПИ при механико-математическом ф-те МГУ, 2004. – 80 с.
5. http://ru.wikipedia.org – материалы из Википедии, свободной энциклопедии