10u-1_Информация

§ 1. Информатика и информация
Информация и информационные процессы

Информатика
Informatik (нем.)
1957, К. Штейнбух:
Английский язык:
computer science
компьютер + наука = наука о компьютерах
informatique = information + automatique
информатика информация автоматика
1962, Ф. Дрейфус:

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

Информация
informatiо – разъяснение, сведения
Латинский язык:
отражает реальный мир
нематериальна
это содержание, которое человек с помощью сознания «выделяет» из окружающей среды
характеризует разнообразие
уменьшает неопределённость знания
Н. Винер: «Информация есть информация, а не материя и не энергия».

Получение информации
зрительная
(визуальная, 80-90 % информации)
звуковая (аудиальная)
вкусовая
обонятельная (запахи)
тактильная (осязание)

Формы представления информации
текстовая
числовая 1 2 4 8 16 32 64 128 256 512 1024
графическая
звуковая
мультимедийная
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.

Информация и знания
Знания — представления человека о природе, обществе, самом себе («модель мира»).
Доля известной информации, %
сведения не новы
ничего непонятно
Ю.А. Шрейдер

Знания
Декларативные — факты, законы, принципы. «Я знаю, что …»
Волга впадает в Каспийское море.
Процедурные — алгоритмы решения задач. «Я знаю, как …»

Данные и информация
Данные — это информация, закодированная в некоторой форме.
данные
знания
информация
знания
знания

Свойства (идеальной) информации
объективность
(независимость от чьего-либо мнения);
понятность для получателя;
полезность
(позволяет получателю решать свои задачи);
достоверность
(получена из надёжного источника);
актуальность
(значимость в данный момент);
полнота
(достаточность для принятия решения).

§ 2. Что можно делать с информацией?
Информация и информационные процессы

Информационные процессы
Материальный носитель — это объект или среда, которые могут содержать информацию.
Информационные процессы — это изменение свойств носителя (= изменение информации).
передача информации
(перенос на другой носитель)
обработка информации
(изменение содержания)
Хранение информации?
(нет изменений носителя ⇒ не процесс)

Передача информации
Сигнал — это изменение свойств носителя, которое используется для передачи информации.
Сообщение — это последовательность сигналов (оболочка для информации).
Для борьбы помехами – избыточность.
«Влг впдт в Кспск мр».
«Борис, Инна, Тимур».
101100100
К
Д
источник
информации
приемник
информации
сигналы
К — кодирующее устройство, Д – декодирующее
канал связи
помехи

Обработка информации
создание новой информации
кодирование – изменение формы, запись в некоторой знаковой системе (в виде кода), шифрование
поиск
структурирование – выделение важных элементов в сообщениях и установление связей между ними
сортировка – расстановка элементов списка в заданном порядке

Хранение информации

§ 3. Структура информации
Информация и информационные процессы

Примеры
«Для того, чтобы добраться до села Васино, нужно сначала долететь на самолете до Ивановска. Затем на электричке доехать до Ореховска. Там на пароме переправиться через реку Слоновую в поселок Ольховка, и оттуда ехать в Васино на попутной машине».
Вариант 1
Вариант 2
Как ехать в Васино?
1) На самолете до Ивановска.
2) На электричке до Ореховска.
3) На пароме через р. Слоновую в пос. Ольховка.
4) На попутной машине до с. Васино.

Примеры
Вариант 3
Вариант 4

Структурирование
Структурирование — это выделение важных элементов в информационных сообщениях и установление связей между ними.
Цель — облегчение восприятия и поиска информации.

Множество
перечисление элементов
Вася, Петя, Коля
1, 17, 22, 55
по характерному признаку
множество натуральных чисел
множество драконов с тремя хвостами
процессор
память
устройства ввода
устройства вывода
маркированный список

Линейный список
надеть носки
надеть ботинки
выйти из дома
нумерованный список

Таблица
объект
объект
свойства
свойства

Таблица
объект
объект

Иерархия (дерево)
узел
дуга

Деревья
«Сыновья» А: B, C.
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G.
«Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).

Деревья
Поддерево – это часть дерева, которая тоже представляет собой дерево.
левое поддерево
правое поддерево
Высота дерева – это число уровней (здесь = 3).

Деревья – классификации
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
…
многоуровневый список

Иерархия – файловая система

Деревья и арифметические выражения
(a+3)*5-2*b
(-(*(+(a,3),5),*(2,b)))
(корень(левое,правое))
- * + a 3 5 * 2 b
Префиксная форма – операция перед данными.

Префиксная форма – вычисление с конца
- * + a 3 5 * 2 b
- * + a 3 5 (2*b)
- * (a+3) 5 (2*b)
- (a+3)*5 (2*b)
(a+3)*5 – (2*b)
Идём с конца, встретили знак операции – выполнили её.

Постфиксная форма (левое-правое-корень)
(a+3)*5-2*b
a 3 + 5 * 2 b * -
(a+3) 5 * 2 b * -
(a+3)*5 2 b * -
(a+3)*5 (2*b) -
(a+3)*5 - (2*b)

Задачи
Запишите выражения, соответствующие показанным деревьям, в «нормальной» (инфиксной), в префиксной и в постфиксной форме.
а)
б)
в)

Задачи
Запишите выражения в префиксной и постфиксной формах.
(a+b)*(c+2*d)
(2*a-3*d)*c+2*b
(a+b+2*c)*d
3*a-(2*b+c)*d
а)
б)
в)
г)

Задачи
Вычислите выражения, записанные в постфиксной форме.
12 6 + 7 3 - 1 - * 12 +
12 10 – 5 7 + * 7 – 2 *
5 6 7 8 9 + - + -
5 4 3 2 1 - - - -
а)
б)
в)
г)

Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное».

Графы

Матрица и список смежности
петля
Матрица смежности
Список смежности
( A (B, C), B (A, C, D), C (A, B, С, D), D (B, C) )

Постройте матрицу смежности

Постройте матрицу смежности

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Связность графа

Дерево – это граф?
дерево
ABC ABDC
BCD CCC…

Взвешенные графы
12
8
2
5
4
6
Весовая матрица:
вес ребра

Постройте весовую матрицу

Постройте весовую матрицу

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Кратчайший путь (перебор)
A
B
С
E
С
D
С
D
E
D
2
4
6
2
4
6
1
3
1
3
9
7
5
8
4
1
3
7
дерево возможных путей
Определите кратчайший путь между пунктами A и D.

Кратчайший путь
Определите кратчайший путь между пунктами A и E.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра называю дугами.

Нарисуйте орграф

Нарисуйте орграф

Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Количество путей из А в К

Количество путей из А в К

Количество путей из А в К

Количество путей из А в К

Количество путей из А в Л не через В
А
Б
В
Г
Д
Е
Ж
И
К
Л
Сколько существует различных путей из города А в город Л, не проходящих через B?

Количество путей из А в Л через Д
А
Б
В
Г
Д
Е
Ж
И
К
Л
Сколько существует различных путей из города А в город Л, проходящих через Д?

Количество путей из А в Л через Д
Сколько существует различных путей из города А в город Л, проходящих через Д?
А
Б
В
Г
Д
Е
Ж
И
К
Л

Установить соответствие
степени
вершин
Ответ: 20
Определить длину дороги между В и Е.

Установить соответствие
степени
вершин
Ответ: 46
Определить длину дороги между A и Д.

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[e-mail]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[e-mail]