Элементы статистики, комбинаторики и теории вероятностей в изучении информатики

Все перспективные государственные образовательные документы последних лет содержат вероятностно-статистическую линию в курсе информатики 5-9 классов.

Информация – это …
Информация – одно из базовых понятий в науке (как материя, энергия), поэтому нет более четкого определения:
невозможно выразить через более простые понятия
объясняется только на примерах или в сравнении с другими понятиями
Н. Винер, «Кибернетика, или Управление и связь в животном и машине»
«Информация есть информация, а не материя и не энергия».

Статистика

Математика
Информатика (7 класс)

Статистические характеристики
Средним арифметическим ряда чисел называется частное от деления суммы этих чисел на число слагаемых.
Размахом ряда чисел называется разность между наибольшим и наименьшим из этих чисел.

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

Задача
В таблице показано число деталей, изготовленных за смену рабочими одной бригады. Для представленного в таблице ряда чисел найти среднее арифметическое, размах и моду. Какой смысл каждого из этих показателей?

Наглядное представление статистической информации
Столбчатая диаграмма используется тогда, когда хотят проиллюстрировать распределение данных, полученных в результате статистических исследований.

В таблице записаны результаты ежедневного измерения на метеостанции в полдень температуры воздуха ( в градусах Цельсия) в течение первой декады марта. Найти среднюю температуру в полдень в эту декаду. Составить таблицу отклонений от средней температуры воздуха в полдень в каждый день из дней декады.
Задача

Решение

Динамику изменения статистических данных во времени иллюстрируют с помощью полигона (графика)

Обработка результатов исследований (опросов)
Проект «Школьная форма – «ЗА» и «ПРОТИВ»

Комбинаторика

Математика
Информатика

КОМБИНАТОРИКА
– раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.

если на каждом шаге известно количество возможных вариантов выбора, то для вычисления общего количества вариантов нужно все эти числа перемножить;
например, в двузначном числе мы можем выбрать первую цифру 9 способами (она не может быть нулем), а вторую – 10 способами, поэтому всего есть 9·10=90 двузначных чисел

если мы разбили все нужные нам комбинации на несколько групп (не имеющих общих элементов!) и подсчитали количество вариантов в каждой группе, то для вычисления общего количества вариантов нужно все эти числа сложить;
например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 9·10=90 трехзначных чисел, оканчивающихся на 2, поэтому 90+90=180 трехзначных чисел оканчиваются на 2 или на 5

если в предыдущем случае группы имеют общие элементы, их количество нужно вычесть из полученной суммы;
например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 10·10=100 трехзначных чисел, начинающихся на 5; в обе группы входят числа, которые начинаются и заканчиваются на 5, их всего 10 штук, поэтому количество чисел, которые начинаются или заканчиваются на 5, равно 90+100-10=180.

если есть n различных элементов, число их различных перестановок равно факториалу числа n, то есть произведению всех натуральных чисел от 1 до n:
n! = 1·2·3·…·(n-1)·n
например, три объекта (А, Б и В) можно переставить 6 способами (3!=1·2·3=6):
(А, Б, В), (А, В, Б), (Б, А, В), (Б, В, А), (В, А, Б) и (В, Б, А)
.

если нужно выбрать m элементов из n (где n≥m) и две комбинации, состоящие из одних и тех же элементов, расположенных в разном порядке, считаются различными, число таких комбинаций (они называются размещениями) равно
например, в соревновании пяти спортсменов призовые места (первые три) могут распределиться 60 способами, поскольку
.

если нужно выбрать m элементов из n (где n≥m) и порядок их расположения не играет роли, число таких комбинаций (они называются сочетаниями) равно
например, выбрать двух дежурных из пяти человек можно 10 способами, поскольку
.

Сколько существует различных четырехзначных чисел, в записи которых используются только четные цифры?
125 2) 250 3) 500 4) 625
Решение:
1) первой цифрой может быть любая четная цифра, кроме нуля (иначе число не будет четырехзначным) – это 2, 4, 6 или 8, всего 4 варианта
2) предположим, что первая цифра выбрана; независимо от нее на втором месте может стоять любая из четных цифр – 0, 2, 4, 6 или 8, всего 5 вариантов:
Задача

3) аналогично находим, что последние две цифры также могут быть выбраны 5-ю способами каждая, независимо друг от друга и от других цифр (первой и второй):
4) общее количество комбинаций равно произведению
4 · 5 · 5 · 5 = 500
5) таким образом, правильный ответ – 3.

Сколько существует различных четырехзначных чисел, в записи которых ровно две девятки, стоящие рядом?
212 2) 225 3) 243 4) 280
Решение:
возможны три случая: 99∙∙, ∙99∙ и ∙∙99, где жирная точка обозначает некоторую цифру, не равную 9
2) для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить
3) в варианте 99∙∙ две последних цифры могут быть любыми, кроме девятки (по 9 вариантов выбора):
Ещё пример задания

поэтому всего получаем 1·1·9·9 = 81 вариант
4) в варианте ∙99∙ первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):
поэтому всего получаем 8·1·1·9 = 72 варианта
5) в варианте ∙∙99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):

поэтому всего получаем 8 · 9 · 1 · 1 = 72 варианта
6) общее количество вариантов равно сумме
81 + 72 + 72 = 225
7) таким образом, правильный ответ – 2.

Виктор хочет купить пять разных книг, но денег у него хватает только на три (любые) книги. Сколькими способами Виктор может выбрать три книги из пяти?
1) 10 2) 20 3) 30 4) 60
Решение (вариант 2, формулы комбинаторики):
нам нужно выбрать 3 объекта из 5, причем порядок выбора здесь не важен – нам нужны разные сочетания
2) зная формулу для вычисления количества сочетаний, сразу находим (при m = 3 и n = 5)
3) таким образом, правильный ответ – 1.
Еще пример задания:

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

Математика
Информатика (9 класс)

Информатика (11 класс, профильный курс)

ТЕОРИЯ ВЕРОЯТНОСТЕЙ
– это раздел математики, изучающий закономерности, основанные на взаимодействии большого числа случайных явлений (статистические закономерности).
Вероятность - отношение числа случаев благоприятствующих событию А, к числу всех возможных случаев называют вероятностью события А.

Вероятность события – число от 0 до 1, показывающее, как часто случается это событие в большой серии одинаковых опытов.
p = 0 событие никогда не происходит
(нет неопределенности)
p = 0,5 событие происходит в половине случаев (есть неопределенность)
p = 1 событие происходит всегда
(нет неопределенности)
Полная система событий: одно из N событий обязательно произойдет (и только одно!).
Вероятностный подход
pi – вероятность выбора i-ого варианта (i=1,…,N)

Количество информации в сообщении о некотором событии зависит от вероятности этого события.
Сообщение о том, что произошло одно событие из двух равновероятных, несёт 1 бит информации.

I – количество информации в битах
N – количество равновероятных событий
бит
Формула Хартли (1928)
Пример:
В аэропорту стоит 6 самолетов, из них один летит в Москву. Сколько информации в сообщении «В Москву летит второй самолет»?
бит

Вероятностный подход
Вычисление вероятности
Задача. В пруду живут 100 рыб, из них 20 карасей, 30 пескарей, а остальные – окуни. Какова вероятность поймать карася (пескаря, окуня), если все рыбы одинаково голодны?
Формула:
число «нужных» событий
общее число событий
Решение:
караси
пескари
окуни

Вероятностный подход
Как посчитать информацию, если варианты не равновероятны?
Идея: если случается менее вероятное событие, мы получаем больше информации.
Если произошло событие i, мы получаем информацию
Клод Шеннон (1916 —2001)
американский математик и электротехник, один из создателей математической теории информации и криптографии.

Вероятностный подход
Задача 1. В пруду живут 100 рыб, из них 20 карасей, 30 пескарей, а остальные – окуни. Сколько информации несет сообщение о том, что рыбак поймал карася (пескаря, окуня), если все рыбы одинаково голодны?
Формула:
Решение:
карась
пескарь
окунь

Вероятностный подход
Задача 2. Посчитать, чему равна информация в сообщении «Сейчас идет снег» зимой и летом.
Решение:
Событие 1 – идет снег, событие 2 – снег не идет.

Формула Шеннона (1948)
Неопределенность (энтропия системы)
Система двух событий:
Средняя информация (неопределенность) максимальна, когда все события равновероятны.
p1
p2= 1 – p 1
Информация = снятая неопределенность!