64)_Дополнительные материалы для подготовки к практической части итоговой контрольной работе по информатике 11 класс, уч. Полякова К.Ю.

Подготовка к итоговой контрольной работе 11 класс-2 часа 2017-2018

Материал подготовлен на основе презентаций

автора учебника Полякова К.Ю.

Обход КЛП – обход «в глубину»

*

(1+4)*(9-5)

+

-

4

9

5

1

2

Вычисление арифметических выражений

?

40–2*3–4*5

Что будет в корне дерева?

В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.

-

-

-

*

40–2*3

4*5

-

*

4

5

40

-

*

3

2

2*3

5

4

40

Количество программ

Задача . У исполнителя Утроитель есть команды:

1. прибавь 1

2. умножь на 3

Сколько есть разных программ, с помощью которых можно из числа 1 получить число 20 ?

?

Как решать, не выписывая все программы?

Количество информации

4

Формула Хартли (1928)

I – количество информации в битах

N – количество вариантов

Ральф Хартли

Пример: В аэропорту стоит 10 самолетов, из них один летит в Санкт-Петербург. Оценить количество информации в сообщении «В Санкт-Петербург летит

второй самолет»?

бита

7

Алфавитный подход

N – мощность алфавита

Информационный объём

символа:

вверх до целого числа

сообщения длиной L :

Пример : сообщение длиной 100 символов закодировано с помощью алфавита из 50 знаков.

6 битов

бита

бита

600 битов

8

Количество различных сообщений

алфавит: А , Б , В , Г

А , Б , В , Г

А , Б , В , Г

всего: 4

всего: 4  4 = 4 2 = 16

А , Б , В , Г для каждого варианта

N – мощность алфавита

L – длина сообщения

Q – количество различных сообщений

10

Вероятность и информация

Аддитивность:

по 8 шариков разного цвета

всего 8  8 = 64 варианта

бита

битов

битов

!

Аддитивность выполняется!

Скорость передачи информации

11

Скорость передачи данных

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

бит/с = 1 bps ( bits per second )

1 кбит/с = 1000 бит/с

скорость передачи

1 Мбит/с = 10 6 бит/с

время

1 Гбит/с = 10 9 бит/с

Объём переданных данных:

v = 512000 бит/с, t = 1 мин

I = v  t = 512000 бит/с  60 с = 30 720 000 битов

= 3 840 000 байтов = 3750 Кбайт.

11

Что такое сложность вычислений?

Задачи теории алгоритмов :

• существует ли алгоритм решения задачи?
• можно ли им воспользоваться?

Шахматы :

• алгоритм существует (конечное число позиций)
• полный перебор нереален

Требования к алгоритму :

• быстродействие
• минимальный расход памяти

временнáя сложность

пространственная сложность

!

Обычно эти требования противоречивы!

14

Временнáя сложность

T – количество элементарных операций универсального исполнителя (компьютера)

!

T зависит от размера входных данных n !

Временная сложность алгоритма – функция T ( n ) .

Задача 1. Вычислить сумму первых трёх элементов массива (при n  3 ).

2 сложения + запись в память

Sum:= A[ 1 ] + A[ 2 ] + A[ 3 ]

T ( n ) = 3

Задача 2. Вычислить сумму всех элементов массива.

Sum:= 0

нц для i от 1 до n

Sum:= Sum + A[i]

кц

T ( n ) = 2 n + 1

n сложений, n + 1 операций записи

15

Временнáя сложность

Задача 3 . Отсортировать все элементы массива по возрастанию методом выбора.

нц для i от 1 до n- 1

nMin:= i;

нц для j от i+ 1 до n

если A[i] A[nMin] то nMin:= j все

кц

если nMin i то

c:= A[i]; A[i]:= A[nMin]; A[nMin]:= c

все

кц

Число сравнений:

Число перестановок:

зависит от данных

100 : ! Нужно знать размер данных! 0 10 0 " width="640"

15

Сравнение алгоритмов по сложности

?

Какой алгоритм выбрать?

при n

при n 100 :

!

Нужно знать размер данных!

0

10 0

17

Асимптотическая сложность

Асимптотическая сложность – это скорость роста количества операций при больших значениях n .

.

линейная

постоянная

сложность O ( n )  T ( n )  c  n для n  n 0

сумма элементов массива:

T ( n ) = 2  n – 1  2  n для n  1  O ( n )

квадратичная

сложность O ( n 2 )  T ( n )  c  n 2 для n  n 0

сортировка методом выбора:

для n  0  O ( n 2 )

17

Асимптотическая сложность

.

кубичная

сложность O ( n 3 )  T ( n )  c  n 3 для n  n 0

сложность O (2 n )

задачи оптимизации, полный перебор вариантов

сложность O ( n !)

Алгоритм имеет асимптотическую сложность O ( f ( n ) ) , если найдется такая постоянная c , что начиная с некоторого n = n 0 выполняется условие

T ( n )  c  f ( n )

0

, что, начиная с некоторго

19

Алгоритмы поиска

Линейный поиск

?

nX:= 0

нц для i от 1 до n

если A[i] = X то

nX:= i

выход

все

кц

Сложность?

сложность O ( n )

20

Алгоритмы поиска

Двоичный поиск

log 2 n

L:= 1 ; R:= n + 1

нц пока L - 1

c:= div (L + R, 2 )

если X A[c] то

R:= c

иначе

L:= c

все

кц

n = 2 m

?

Сколько шагов?

T ( n ) = m + 1

T ( n ) = log 2 n + 1

сложность O (log n )

основание роли не играет

?

Какой алгоритм поиска лучше?

A[j+ 1 ] то c:= A[j]; A[j]:= A[j+ 1 ]; A[j+ 1 ]:= c; все кц кц сравнений: присваиваний при перестановках: сложность O ( n 2 ) " width="640"

21

Алгоритмы сортировки

Метод «пузырька»

нц для i от 1 до n- 1

нц для j от n- 1 до i шаг -1

если A[j] A[j+ 1 ] то

c:= A[j]; A[j]:= A[j+ 1 ]; A[j+ 1 ]:= c;

все

кц

кц

сравнений:

присваиваний при перестановках:

сложность O ( n 2 )

21

Алгоритмы сортировки

Сортировка подсчётом

!

Все значения [1,MAX]!

цел C[ 1 :MAX]

нц для i от 1 до MAX

C[i]:= 0

кц

обнулить массив счётчиков

n

нц для i от 1 до n

C[A[i]]:= C[A[i]] + 1

кц

подсчитать, сколько каких чисел

заполнить массив заново

k:= 1

нц для i от 1 до MAX

нц для j от 1 до C[i]

A[k]:= i

k:= k + 1

кц

кц

сложность O ( n )

n

?

За счёт чего?

23

Алгоритмы сортировки

!

При использовании операций «сравнить» и «переставить» сложность не может быть меньше O ( n  log n ) !

O ( n  log n )

Сортировка слиянием ( Merge sort )

O ( n  log n )

Пирамидальная сортировка ( Heap sort )

Быстрая сортировка ( Quick sort )

в среднем

O ( n  log n )

в худшем случае

O ( n 2 )