Тема 1. Основные понятия и методы теории информатики и кодирования 1.Понятие информации 2.Свойства информации 3.Понятие количества информации 4.Информационные процессы 5.Информация в жизни человечества 6.Математические основы информатики 6.1. Системы счисления (см. лаб. раб.) 6.2. Алгебра высказываний (Булева алгебра) 6.3. Элементы теории графов 7.Формы представления информации 8.Предмет и структура информатики

Литература 1) Информатика. Под ред. Курносова А.П. – М.: КолосС, 2005 г. 2) Информатика: базовый курс. Под ред. Симонович – СПб.: Питер, 2002 г. 3) Информатика. Под ред. Макаровой Н.В. – М.: Финансы и статистика, 2002 г.

1. Понятие информации informatio - сведения, разъяснения, изложение. Сигнал это изменяющийся во времени физический процесс. Параметр сигнала - характеристика, которая используется для представления данных.

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

Сигналы Непрерывный по уровню и Дискретный по уровню во времени сигнал Х и непрерывный по времени Непрерывный по уровню и Дискретный по уровню и дискретный по времени сигнал Х по времени сигнал Х

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

Тела, поля Сигналы Данные Информа ция Взаимодействия Регистрация сигналов Методы Рис. Формирование информации

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

2. Свойства информации Дуализм информации характеризует ее двойственность. Полнота информации характеризует степень достаточности данных для принятия решения. Адекватность информации выражает степень ее соответствия реальному состоянию объекта. Доступность информации - это возможность получения информации при необходимости. Актуальность информации характеризует ее соответствие текущему моменту времени.

Выделяют 3 аспекта информации: Синтаксический, рассматриваются внутренние свойства сообщений Семантический, анализируется смысловое содержание сообщения Прагматический, рассматривается потребительское содержание сообщения.

3. Понятие количества информации Количеством информации называют числовую характеристику информации, отражающую ту степень неопределенности (энтропию), которая исчезает после получения информации. 1 бит (bit binary digit двоичная цифра) - это количество информации, при котором неопределенность уменьшается вдвое.

Лампа А: Лампа В: Формула Хартли (для равновероятных событий): i=log 2 N или N=2 i. где i - количество информации в битах; N - число возможных состояний. Лампа А: Лампа В: Лампа С:

Производные единицы информации: 1 байт = 8 бит - основная единица 1 Килобайт (Кб) = 1024 байт = 2 10 байт 1 Мегабайт (Мб) = 1024 Кбайт = 2 20 байт 1 Гигабайт (Гб) = 1024 Мбайт = 2 30 байт 1 Терабайт (Тб) = 1024 Гбайт = 2 40 байт 1 Петабайт (Пб) = 1024 Тбайт = 2 50 байт

4. Информационные процессы Под информационным понимается процесс, связанный с определенными операциями над информацией, в ходе которого может измениться содержание информации или форма ее представления: Сбор данных Передача данных Хранение данных Обработка данных

Деятельность человека, связанная с информационными процессами, называется информационной деятельностью.

5. Информация в жизни человечества Информационные революции: 1) изобретение письменности – 6 тыс. л. назад 2) книгопечатанье – 16 в. 3) электричество (конец 19 в.), новые средства коммуникации, ЭВМ (сер. 20 в.) 4) компьютерные сети, Интернет – формирование единого мирового информационного пространства – наше время

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

6. Математические основы информатики

6.2. Алгебра высказываний Простое высказывание Простое высказывание – это предложение, о котором можно сказать, истинно (True) оно или ложно (False). А: «дважды два равно четырем» В: «три больше пяти» А = 1 В=0 Джордж Буль ( )

Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности. А = В Сложное высказывание Сложное высказывание можно построить из простых с помощью логических операций и логических выражений, представляющих собой комбинации логических операций.

Логические операции: отрицание (НЕ), конъюнкция (И), дизъюнкция (ИЛИ), импликация (если, то), эквиваленция (тогда и только тогда, когда).

отрицанияА Операцией отрицания А называют высказывание Ā (¬ А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. АĀ 01 10

Конъюнкция Конъюнкция (логическое умножение) двух высказываний А и В - это новое высказывание С, которое истинно только тогда, когда истинны оба высказывания. С = А В С = А & В С = А * В АВ А В

Дизъюнкция Дизъюнкция (логическое сложение) двух высказываний А и В - это новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. С = A V В С = А + В АВ AVBAVB

Импликация двух высказываний А (посылка) и В (заключение) - это новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно. С=А В АВАВ

Эквиваленция двух высказываний А и В - это новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности. С = А В АВ А В

С = ((ĀvB) B)vA. Порядок выполнения операций в булевских функциях: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

1. А В = Ā В 2. A B = (A B) (B A) = (Ā B) (A B) = (A B) (Ā B) 3.A = A - закон двойного отрицания 4. A B = B A - коммутативный закон для конъюнкции 5. A B = B A - коммутативный закон для дизъюнкции 6. (A B) C = A (B C) - ассоциативный закон для конъюнкции Зависимости между логическими операциями

7. (A B) C = A (B C) - ассоциативный закон для дизъюнкции 8. A (B C) = (A B) (A C) - дистрибутивные законы 9. A (B C) = (A B) (A C) 10. A A = A - закон идемпотенции для конъюнкции 11. A A = A - закон идемпотенции для дизъюнкции

12. A B = Ā B - законы де Моргана 13. A B = Ā B 14. A 1 = A - закон единицы для конъюнкции 15. A 0 = 0 - закон нуля для конъюнкции 16. A 1 = 1 - закон единицы для дизъюнкции 17. A 0 = A - закон нуля для дизъюнкции Зависимости между логическими операциями

18. A (A A) = A - законы поглощения 19. A (A A) = A 20. A Ā = 1 - закон исключения третьего 21. A Ā = 0 - закон противоречия 22. A (Ā B) = A B 23. A (Ā B) = A B

Дизъюнктивная нормальная форма (ДНФ) имеет вид A1 A2... An, где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний. Например: В = (Ā1 А2) (А3 A4) (А5 А6)

Конъюнктивная нормальная форма (КНФ) имеет вид А1 А2... An, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний. Например: В = (Ā1 А2 Ā3) (А4 А5) А6.

Логические основы устройства компьютера 1 х1 х2 y & х1 х2 yх1y Элемент «логическое ИЛИ» Элемент «логическое И» Элемент «логическое НЕ»

Для построения современных ЭВМ обычно применяются системы интегральных элементов И-НЕ (штрих Шеффера), ИЛИ-НЕ (стрелка Пирса), И-ИЛИ-НЕ.

Триггер - функциональное устройство, которое может по команде принять или выдать один двоичный бит, а, главное, сохранять его сколь угодно долго.

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

Сумматор - устройство, реализующее арифметическую операцию сложения двух целых чисел.

6.3. Элементы теории графов Граф задается парой множеств: множеством вершин Е и множеством ребер U. Ребро u U есть пара (е i, е j ), где e i, е j Е, указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро u U инцидентно вершинам e i, е j.

Если порядок ребер не имеет значения, т.е. u = (е i, е j ) = (е j, е i ), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро u = (е i, е j ) называется ориентированным ребром или дугой. Вершина е i - называется началом дуги, е j конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом.

Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Две вершины e i, е j Е называются смежными, если они соединены ребром.

Число ребер, инцидентных данной вершине е i, называется локальной степенью этой вершины (е i ). Число ребер r графа G(E,U) определяется выражением где n - количество вершин в графе.

Пусть множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Число ребер в графе определяется по значению локальных степеней для каждой вершины: (1) = 3; (2) = 2; (3) = 3; (4) = 2; (5) = 2; r = ( ) / 2 =

Маршрутом графа G называется последовательность ребер S = (u 1, u 2... u n ), в которой каждые два соседних ребра имеют общую вершину, т.е. u 1 =(е 1, е 2 ); u 2 =(е 2, е 3 );... u n = (e n, e i+1 ). Две вершины e i и е j называются связанными, если существует маршрут из e i в е j.

Простой цепью, или простым путем, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S = (1, 2, 3, 5, 4, 1):

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

7. Формы представления информации кодированием Процесс преобразования информации из одной формы представления в другую называется кодированием. Для ЭВМ используют двоичное кодирование (binary encoding), основанное на двоичной системе счисления.

Формула объема кодируемой информации N=2 m где N количество независимых кодируемых значений; m разрядность двоичного кодирования.

8 бит (8 разрядов двоичного кода) позволяют закодировать целые числа от 0 до 255: = = = бит позволяют закодировать целые числа от 0 до , 24 бита более 16,5 миллионов различных значений. Кодирование целых чисел

Кодирование действительных чисел Нормализация - приведение действительного числа X к виду X = ± m 10 ±р где m- мантисса (должна быть меньше 1, а первая значащая цифра отличной от нуля), р - характеристика (порядок) числа; Например: = 0,

Кодирование текстовой информации Каждому символу алфавита ставят в соответствие определенный двоичный код. ASCII (American Standard Code for Information Interchange, 1981 г) – 8-разрядный код; включает основную часть (128 символов) и национальную (128 символов). UNICODE (1991 г) – 16-разрядное кодирование.

Кодирование графической информации Растровые изображения – однослойная сетка точек, называемых пикселами (pixel – picture element). Код каждого пиксела содержит информацию о его цвете. Векторное изображение - совокупность ряда графических элементов (линий, прямоугольников, эллипсов, фрагментов текста).

Модель RGB. Любой цвет получается сложением основных цветов - красного (Red), зеленого (Green), синего (Blue). Применяется в мониторах, телевизорах. Модель CMYK. Цвет получается вычитанием из основных + дополняющие цвета: Cyan(голубой), Magenta (пурпурный), Yellow (желтый) и Black (черный). Применяется в полиграфии.

Оцифровка цвета N = 2 m N -количество различных цветов, m - количество бит, необходимых для их кодировки. 4 бит позволяет закодировать 2 4 = 16 различных цветов, 8 бит = 256 различных цветов, 16 бит (High Color) - уже цветов. 24 бита (True Color) различных цветов и оттенков (по 8 бит на каждый из трех основных цветов).

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

Устройство, выполняющее дискретизацию называют аналого- цифровым преобразователем (АЦП). Цифро-аналоговый преобразователь (ЦАП) выполняет обратное действие - воспроизводит закодированный звук. АЦП ЦАП Рис. Процесс дискретизации

Модели представления дополняются процедурами сжатия, т.е. плотной упаковкой информации: сжатие с изменением структуры данных (без потерь) – для хранения текстов, чисел, программ; сжатие с частичной потерей данных – для хранения графики и звука.

8. Предмет и структура информатики Информатика (Computer Science) изучает информационные процессы и разрабатывает технологии этих процессов. Информатика это наука, изучающая: методы реализации информационных процессов средствами вычислительной техники (СВТ); состав, структуру, общие принципы функционирования СВТ; принципы управления СВТ.

Структура информатики Информационные процессы Аппаратное обеспечение (АО) Программное обеспечение (ПО) Теория кодирования,Логика,Теория алгоритмов, Теория информации,Электроника,Логика, Теория графов,Автоматика,Теория графов, Теория множеств,КибернетикаТеория игр, Логика и др.и др.Лингвистика и др. Кодирование данных,Синтез цифровых устройств, Вспомогательные программы, Форматы данных,Архитектура СВТ,Интерфейсы, Сжатие данных,Аппараты и приборы вычислительных систем; Системы программирования, Структуры данных и др. Аппараты и приборы компьютерных сетей Прикладные программные продукты

Предмет Предмет информатики составляют следующие понятия: аппаратное обеспечение средств вычислительной техники (СВТ); программное обеспечение СВТ; средства взаимодействия аппаратного и программного обеспечения; средства взаимодействия человека с аппаратными и программными средствами. Основной задачей Основной задачей информатики является систематизация приемов и методов работы с аппаратными и программными средствами ВТ.

Этапы развития информатики 1) технический период («железный век», аппаратная фаза) г 2) программный период («бронзовый век», программная фаза) г 3) информационный период («серебряный век», информационная фаза) г 4) гуманитарный период («золотой век») с 1990 г.

1)Технический период ( г) Это период с момента появления первых ЭВМ и до окончательного утверждения современных представлений о составе, принципах функционирования и структурах ЭВМ.

2) Программный период ( г) Выработалась современная классификация программных средств, их структур и взаимосвязей, сложились языки программирования, разработаны компиляторы и принципы процедурной обработки, операционные системы, языки управления заданиями.

3) Информационный период ( г) В центре внимания исследователей и разработчиков оказываются структуры данных, языки описания (ЯОД) и манипулирования (ЯМД) данными, непроцедурные подходы к построению систем обработки информации, базы данных, автоматизированные ИС.

4) Гуманитарный период (с 1990 г) Связан с резким возрастанием круга пользователей ИС и повышением роли интерфейсных, коммуникационных и навигационных возможностей соответствующих систем.