Презентация на тему по информатике Обработка информации (10 класс углубленный уровень И.Г. Семакин)

производимых над информацией (в виде данных, идей, гипотез, теорий)

для получения какого-либо результата (достижения цели).

!

Информационные процессы

или формы представления информации.
!

решается некоторая информационная задача.
Алгоритм обработки информации для исполнителя
Исходная информация
Результат

обработки

Исполнитель – человек или компьютер, который осуществляет обработку информации
Алгоритм – последовательность действий, которую нужно выполнить, чтобы достичь нужного результата

преобразовании в некоторую форму, удобную для хранения, передачи, обработки

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

!

изобретате-ля и художника Сэмюэля Морзе, – самый известный пример

нерав-номерного кода, в котором цифры и буквы алфавита представляют-ся последовательностями длин-ных («тире») и коротких («точек») сигналов.
Сигналы отделяются друг от друга паузами — отсутствием сигналов.
Фактически, пауза является третьим знаком в азбуке Морзе, а сам код — троичным.

одна единица.
2. Тире – три единицы.
3. Пауза между частями

одного знака – одна единица.
4. Пауза между знаками – три единицы.
5. Пауза между словами – семь единиц.

Расшифруйте слово, закодированное с помощью азбуки Морзе, представленное на «временно́й» шкале следующим образом:

?

три кольца с цифрами от 0 до 9. Сколько

различных комбинаций можно на нем закодировать?

Правило умножения
Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n · m способами.

Решение:

0 1 2 3 4 5 6 7 8 9

0 1 2 3 4 5 6 7 8 9

0 1 2 3 4 5 6 7 8 9

однозначного декодирования записанного с их помощью сообщения.
Пре́фиксный код

— код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова.

!

Определите, является ли код, состоящий из заданной последовательности слов, префиксным:

?

а) 0, 10, 11

б) 0, 10, 11, 100

префиксный код

не префиксный код

10

по работам в области теории информации.
Для того чтобы сообщение,

записанное с помощью неравномерного кода, однозначно декодировалось, достаточно, чтобы никакое кодовое слово не было началом другого (более длинного) кодового слова.

Обратное условие Фано также является достаточным условием однозначного декодирования неравномер-ного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.

Для возможности однозначного декодирования достаточно выполнения одного из условий Фано —прямого или обратного.

представлены в таблице:



Какое сообщение (какой набор букв) закодировано с

помощью этих кодов двоичной строкой: 0110100011000.

Решение:

Заметим, что код буквы B (01) является началом кода бук-вы E (011); а код буквы D (10) - началом кода буквы C (100).
Прямое условие Фано для заданных кодов не выполняется. Следовательно, декодирование с начала (слева направо) данной строки может на каком-то шаге привести к неоднозначности.

Для имеющихся кодов выполняется обратное условие Фано: никакой код не является окончанием другого кода. Следовательно, имеющуюся двоичную строку можно декодировать однозначно, если начать её декодирование с конца (справа налево).

0 1 1 0 1 0 0 0 1 1 0 0 0

0 0 0

А

0 1 1

Е

1 0 0

С

1 0

D

0 1

B

Ответ: BDCEA

центральным элементом последова-тельности, номер которого находится как [N/2] +

1; если значения искомого элемента и центрального совпадают, то поиск завершается, в противном случае поиск продолжается в одной из двух частей последовательности
длительность поиска (L): N = 2L, где N — размер набора данных

неструктурированный набор данных
поиск завершается, когда найден искомый элемент или когда просмотрены все элементы набора данных, но искомого элемента в нем нет
длительность поиска (L): L = N/2, где N — размер набора данных; если искомый элемент окажется последним или его не окажется вообще, то длительность поиска равна N

Поиск информации

МЕТОД ПОСЛЕДОВАТЕЛЬНОГО ПЕРЕБОРА

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

Важнейшая задача обработки информации — поиск инфор-мации. Алгоритм поиска зависит от способа организации информации.

кроссовку. В магазине осталось только девять коробок с обувью

той же модели и того же размера. Помогите продавцу найти пару для этой кроссовки.

складов, пронуме-рованных от 1 до 9. Плотник не может

вспомнить, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров. Помогите плотнику найти первый из незаполненных складов за меньшее число ходов.

Сформулируйте правило оптимального поиска.
Решите задачу с 31 складом.

ПОВТОР

или формы представления информации.
Существует два различных типа обработки

информации: 1) обработка, связанная с получением нового содержания, новой информации; 2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.

Кодирование — обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Код — система (список) условных обозначений (кодовых слов), используемых для представления информации.

длины, обладающий тем свойством, что никакое его кодовое слово

не может быть началом другого (более длинного) кодового слова. Сообщение, закодированное с помощью префиксного кода, может быть однозначно декодировано.

Задача поиска информации состоит в том, чтобы в некотором хранилище информации найти информацию, удовлетворяющую определенным условиям поиска.
Для осуществления поиска в неструктурированном наборе данных применяется метод последовательного перебора.
Поиск информации в упорядоченном наборе данных может быть осуществлён методом половинного деления.

каждый из которых может светиться красным, желтым, синим или

зеленым цветом. Сколько различных сигналов можно передать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?

Решение:

1

2

3

4

5

Существует по 4 варианта выбора цвета первого и второго элементов. По правилу умножения цвета для пары (1, 2) можно выбрать 4 · 4 = 42 = 16 способами.
Цвета для тройки элементов (1, 2, 3) можно выбрать 16 · 4 = 43 = 64 способами и т. д.
Цвета для шести элементов (1, 2, 3, 4, 5, 6) можно выбрать 46 = 4096 способами.

6

Ответ: 4096 способов

закодировать два символа.
Рассмотрим последовательности, содержащие два знака из двухсимвольного

алфавита. Их может быть 2 · 2 = 22 = 4.

Рассмотрим последовательности, содержащие три знака из двухсимвольного алфавита. Их может быть 4 · 2 = 23 = 8.

Последовательностей из четырёх знаков, при-надлежащих двухсимвольному алфавиту, может быть 8 · 2 = 24 = 16.

Число различных последовательностей, содержащих не более четырех знаков двухсимвольного алфавита, будет равно 30 = 2 + 4 + 8 + 16.

Вопросы и задания

2

4

8

16

Решение:

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

Итого: 30

Ответ: 30 различных символов

букв А, Б, В и Г, решили использовать неравномерный

двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Для букв А, Б и В использовали такие кодовые слова:
А – 0, Б – 10, В – 110.
Каким кодовым словом может быть закодирована буква Г?
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

деревом.
Для решения задачи воспользуемся бинарным деревом.
Отметим вершины, соответствующие используемым

кодовым словам: А – 0, Б – 10, В – 110:

Комбинациям префиксного кода должны соответствовать листья бинарного дерева, поэтому:

Тогда для кодирования буквы Г можно использовать код 111.

Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен однозначно декодироваться, а общая длина кодовых слов должна быть минимальной.

?

Б

В

Г

А