Теория информации и структуры данных. Роман Вячеславович Шамин shamin ru, lector ru, calcs ru
 Скачать 2.74 Mb.
|
Курс «Информатика» тема № 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) тип данных не фиксирован и меняется в зависимости от контекста. Простейшие типы данных:
Массивы Лекции по информатике, Р.В. Шамин: 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 Основная проблема массивов состоит в том, что массив имеет фиксированный размер. А как быть, если мы заранее не знаем количества элементов? Для этого необходимо использовать списки. Список – структура данных, состоящая из узлов, хранящих как данные, так и ссылку на следующий элемент. При добавлении нового элемента ссылка последнего элемента заменяется на ссылку на новый элемент, а новый элемент получает ссылку на Null. Таким образом, количество элементов ограничивается только памятью. Современные языки имеют встроенные списки, когда добавление нового элемента делается автоматически: List.append(X) – добавление X к списку List в Python. Очередь Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru Часто нам нужно организовать очередь, когда мы сохраняем и имеем доступ к элементам не по индексу, а по принципу «первый вошел, первый вышел» FIFO – «first in, first out». Важной особенностью очереди является то, что новые данные вставляются только в конец очереди, а извлекать можно только первый элемент очереди. Размер очереди может быть фиксированным или динамическим как в случае списков. Стек Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru Стек представляет собой структуру данных, в которой принцип: «последний вошел, первый вышел» LIFO – «last in, first out». Стек – это очень эффективное средство организации данных, которая применяется в рекурсивных обходах дерева, организации вызовов подпрограмм и др. Обычно стек поддерживает три операции:
Стек можно сравнить со стопкой книг или магазином с патронами Хеш-таблица или словарь Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru Классический массив представляет собой набор элементов, доступ к которым осуществляется с помощью индекса – целого числа 0, 1, … А почему бы не сделать массив, доступ к элементам которого будет не с помощью чисел, а произвольного ключа-имени? Такой массив называется хеш-таблицей или словарем. Хеш-таблица позволяет эффективно организовать доступ по принципу «ключ – значение». Например, для описания студентов можно использовать следующую структуру Students: [key=“фамилия имя отчество”, data = “адрес”] Например: адрес Лобанова Андрея Николаевича можно найти по запросу: Students[“Лобанов Андрей Николаевич”] Заключение Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru В этой лекции Вы познакомились со следующими понятиями:
Подготовка к тесту Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru Вопрос № 1: «Что такое информация и какими она может обладать свойствами?» Вопрос № 2: «Сколько бит в 5 гигабайтах?» Вопрос № 3: «Какой смысл имеет энтропия информации?» Вопрос № 4: «Чему равно F516?» «Записать в двоичной системе счисления число 21» Вопрос № 5: «Записать в нормализованной форме число 120,34. Указать мантиссу и порядок» Подготовка к тесту Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru Вопрос № 6: «Что такое данные и чем они отличаются от информации?» Вопрос № 7: «Какого типа данных могут быть переменные?» Вопрос № 8: «Что такое массив?» Вопрос № 9: «Чем список отличается от массива? от хеш-таблицы?» Вопрос № 10: «В чем разница между стеком и очередью?» Удачи на экзамене! |