Файл: Роман Вячеславович Шамин shamin ru, lector ru, calcs ru.pptx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 198
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Курс «Информатика» тема № 1 «Теория информации и структуры данных»
заведующий кафедрой доктор физико-математических наук
Роман Вячеславович Шамин
shamin.ru, lector.ru, calcs.ru
МИРЭА – Российский технологический университеткафедра информатики Института комплексной безопасности и специального приборостроенияМосква, 2019 г.Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ruЧто такое информатика?Информатика – это наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность ее использования для принятия решений. Большая российская энциклопедия, 2008.Основным объектом информатики является понятие информации. «Информация – это сведения, независимо от формы их представления, воспринимаемые человеком или специальными устройствами как отражение фактов материального мира в процессе коммуникации». ГОСТ 7.0-99.Свойства информации:- полезность
- актуальность
- достоверность
- объективность
- полнота
- понятность
Мы будем изучать только цифровую информацию, поэтому важнейшим понятием является единица измерения информации – бит. Бит – это минимальная единица измерения информации. Бит может принимать только два значения 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 ост. 11710 = 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)