Файл: Роман Вячеславович Шамин shamin ru, lector ru, calcs ru.pptx

Курс «Информатика» тема № 1 «Теория информации и структуры данных»

заведующий кафедрой доктор физико-математических наук

Роман Вячеславович Шамин

shamin.ru, lector.ru, calcs.ru

МИРЭА – Российский технологический университет

кафедра информатики Института комплексной безопасности и специального приборостроения

Москва, 2019 г.

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Что такое информатика?

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

Большая российская энциклопедия, 2008.

Основным объектом информатики является понятие информации.

«Информация – это сведения, независимо от формы их представления, воспринимаемые человеком или специальными устройствами как отражение фактов материального мира в процессе коммуникации». ГОСТ 7.0-99.

Свойства информации:

• полезность
• актуальность
• достоверность
• объективность
• полнота
• понятность

Носители информации:

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

В XXI веке информация играет самую главную роль в нашей цивилизации и имеет самое большое значение для развития Человечества.

«Кто владеет информацией, тот владеет миром.» Натан Ротшильд, 1815 г. после битвы при Ватерлоо.

Информатика в нашей жизни:

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

Запомните:

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

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Теория информации: единицы измерения

---

Мы будем изучать только цифровую информацию, поэтому важнейшим понятием является единица измерения информации – бит. Бит – это минимальная единица измерения информации. Бит может принимать только два значения 0 или 1. Это соответствует каком-либо физическому устройству, которое может быть только в двух положениях «0» или «1». Такие устройства легко конструируются.

Бит можно рассматривать как два варианта какого-либо высказывания, которое может быть истинным или ложным, хотя можно себе представить и вопрос, на который можно ответить «да», «нет» или «не знаю». Такая логика называется троичной логикой.

Бит – двоичное число. Игра слов: binary digit, англ. bit – это кусочек, частица.

С помощью битов формируются сообщения, при этом биты являются дискретными.

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Теория информации: единицы измерения

В современных компьютерах используют следующие единицы измерения:

1 Б (байт) = 8 бит

1 Кбайт (килобайт) = 1024 Б

1 Мбайт (мегабайт) = 1024 Кбайт

1 Гбайт (гигабайт) = 1024 Мбайт

1 Тбайт (терабайт) = 1024 Гбайт

Задача:

Сколько битов в 3 Мбайт?

Решение:

3 Мбайт = 3 * 1024 Кбайт = 3* 1024 * 1024 Б =

= 3* 1024 * 1024 * 8 бит = 25165824 бит

Цифровое сообщение – это упорядоченный конечный набор битов. Длиной сообщения мы будем называть количество бит, которое содержит данное сообщение и писать |S| = N, если сообщение S = (s1, s2, …, sN).

Сколько разных сообщений длины N? Ответ: 2N различных сообщений.

N = 1: количество = 2; N = 2: количество = 2 * (количество для

N-1) = 4; …;

количество для N = 2 * (количество N-1) = 2*2*…*2 = 2N.

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Теория информации

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Рассмотрим задачу: какое минимальное количество бит нужно для описания всех K состояний системы?

Для этого нужно найти такое минимальное N, которое будет удовлетворять уравнению K = 2N. Логарифмируя по основанию 2, получаем N = log2K. Если в этой формуле N не будет четной, то его нужно округлить (вверх!) до целого.

Формула N = log2K, где K – количество возможных состояний, а N – минимальное количество информации в битах, необходимое для описания состояний системы называется формулой Хартли.

Пример:

Сколько нужно бит, чтобы описать состояния системы из 5 состояний? Нужно:

log25 = 2,322 => N = 3 бита.

Заметим, что тремя битами можно описать и системы и из 6, 7 и 8 состояний, но не из 9 состояний. Почему? Потому что log29 = 3,17 > 3.

---

Буквы русского языка (без различия по регистру) можно описать 5-ю битами, если не различать Е и Ё, а если различать, то 6-ю битами с избытком:

log232= 5; log233 = 5,044.

Теория информации: энтропия

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Пусть теперь система может находиться в одном из K состояний с разными вероятностями. В состоянии 1 с вероятностью p1, в состоянии 2 с вероятностью p2 и т.д. в состоянии K с вероятностью pK, где pk ≥ 0. Тогда ценность знания, что система находится в состоянии pk зависит от распределения вероятностей.

Фундаментальное понятие теории информации – энтропия информации. Под энтропией понимается мера неопределенности системы. Общей энтропией по Шеннону называется число H, а частной для каждого состояния – число pilog2pi.

Прирост информации – это уменьшение энтропии.

H = – ∑ pilog2pi

сумма по всем состояниям

Если двоечник не поступил в РТУ МИРЭА, то тут мало информации, потому что «мы это и так знали», а вот если он поступил, то это «новость»!

Полагая, что двоечник не поступает с вероятностью 0,9, а поступает с вероятностью 0,1 то, общая энтропия равна: H = 0.469.

А частная энтропия для не поступления равна: -0,9 * log20,9 = 0.137,

а для поступления равна: -0,1 * log20,1 = 0,332.

Системы исчисления

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Использование битов в качестве алфавита {0, 1} наводит на мысль, что компьютерам лучше использовать двоичную систему счисления.

Натуральное число в десятичной системе счисления представимо в виде:

x = aN…a2a1a0, где каждое an – это цифра 0..9. При этом число равно

x = a0100 + a1101 + … + aN10N.

В двоичной системе счисления число имеет вид: x = aN…a2a1a0, где каждое an – это цифра 0 или 1.

При этом число равно

x = a020 + a121 + … + aN2N.

В k-ичной системе счисления число имеет вид: x = aN…a2a1a0, где каждое an – это цифра от 0 до k-1. А число равно x = a0k0 + a1k1 + … + aNkN. Если k > 10, то в качестве цифр используются заглавные буквы латинского языка, например в шестнадцатеричной системе счисления цифры: 0, 1, …, 9, A, B, C, D, E, F.

Если число x записано в k-ичной системе счисления, то пишут xk. Наиболее распространены в информатике кроме десятичной системы счисления еще двоичная и шестнадцатеричная.

Системы исчисления

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Как перевести число из одной системы счисления в другую?

---

Чтобы любое число в k-ичной системе исчисления перевести в десятичную систему нужно воспользоваться формулой: x = a0k0 + a1k1 + … + aNkN.

Чтобы число X из десятичной системы перевести в k-ичную, нужно:

Разделить X на k: пусть X1 – это целая часть отношения, а a0 – остаток от деления. Если X1 не равно нулю, то делим X1 на k, обозначаем через X2 целую часть, через a1 – остаток. Повторяем эту процедуру до тех пор пока целая часть от деления не станет равной нулю.

В результате X = aNa(N-1)…a1a0 – это представление числа X в k-ичной системе счисления.

17 в двоичную систему:

17 / 2 = 8 ост. 1; 8 / 2 = 4 ост. 0;

4 / 2 = 2 ост. 0; 2 / 2 = 1 ост. 0;

1 / 2 = 0 ост. 1

1710 = 100012

Перевести 234 в шестнадцатеричную систему:

234 / 16 = 14 ост. A; 14 / 16 = 0 ост. E;

23410 = EA16.

Заметим, что при записи остатка мы пишем его в шестнадцатеричной записи: 1010=A16, 1410=E16.

10102 = 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20 = 1 * 8 + 0 * 4 + 1 * 2 + 0 * 1 = 1010.

Представление чисел в компьютере

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

В компьютере могут быть представлены числа только с конечным числом цифр после запятой. В этом случае любое число может быть представлено в виде a,b, где a – это целое число, а b – целое положительное число. Например: -648,512, где a = -648, b = 512.

Более того, такое число может быть представлено в виде a,b*10p, где a – целое, b – целое положительное, p – целое. Нормализованной называется запись, когда

1 ≤ |a| < 10.

Например: -648,512 в нормализованной записи

-6,48512*102.

Число a,b в этой записи называется мантиссой, а p – порядком.

Во многих языках программирования пишут

a,b*10p = a.bEp, используя точку.

Например: -6,48512*102 = -6,48512E2.

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

Число ε > 0 называется машинным эпсилон, если a + ε = a, где равенство понимается как сравнение чисел на компьютере. Значение ε зависит от точности представления чисел.

Данные

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

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

Данные – это форма представление информации, доступная для обработки.

Формат представления данных – это последовательность бит (байт).

Физически данные хранятся в виде файлов или потоков данных на физических носителях информации.

Поток данных – это абстракция для доступа к данным из файлов

---

, периферийных устройств и т.д.

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

Строительным элементом данных является переменная. Переменная – это именованная область памяти определенного типа. Тип переменной определяет и формат хранения данных.

Переменные

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Переменная – это понятие языка программирования. В языках программирования каждая переменная иметь уникальное имя, которое, как правило, содержит буквы, цифры и подчеркивания, при этом имя переменной не может начинаться с цифры. Большинство языков программирования различают большие и малые буквы.

Вот примеры имен переменных:

Abc, ABC, _abc, a20, abc_20.

Неправильно: 20abc, _20.

Каждая переменная должна иметь определенный тип данных. В некоторых языка программирования (C++, Java, C#) каждая переменная перед использованием объявляется и получает фиксированный тип данных, который потом не может быть изменен. Такие языки называются строго типизированными. В других языках (Python, PHP, JavaScript) тип данных не фиксирован и меняется в зависимости от контекста.

Простейшие типы данных:

• целочисленный (int)
• вещественный (double, real, float)
• строковый (string)
• логический (bool, boolean)

Массивы

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

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

Массив – структура данных, хранящая набор однотипных переменных, доступных по индексу.

Как правило, массивы индексируются, начиная с нуля. Т.е. первый элемент массива имеет индекс = 0.

Каждый массив имеет определенный размер (количество элементов). Размер массива определяется либо в момент объявления или инициализации.

Массив – это тоже переменная с именем, например, A.

Доступ к первому элементу A[0], а к последнему A[Count – 1], если Count – это количество элементов в массиве.

Массивы могут быть многомерными, когда каждый элемент индексируется не одним индексом, а несколькими. Например, двумерный массив A[i, j], а трехмерный A[i, j, k], где i, j, k – это индексы массива.

Списки

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Основная проблема массивов состоит в том, что массив имеет фиксированный размер. А как быть, если мы заранее не знаем количества элементов?

Для этого необходимо использовать списки.

Список – структура данных, состоящая из узлов,

---