Свойства алгоритмов. 1. Понятие информации. Меры информации

ВОПРОСЫ и некоторые ОТВЕТЫ

по курсу «Информатика»

1. Понятие информации. Меры информации.

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

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

2. Информация и информатика. Связь информатики с другими науками.

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

3. Сообщения и информация. Обобщенная схема получения, передачи и обработки информации.

1) Объект описывается с помощью множества его свойств.

2) Совокупность сведений об объекте (а именно о его свойствах) будем называть сведениями.

3) Чем больше свойств объекта известно, тем более адекватно описание объекта; вместе с тем, сколько бы свойств объекта не было известно, всегда существуют неизвестные свойства. Эти неизвестные свойства обуславливают неопределенность.

4) Свойства объекта могут быть измерены, либо вычислены.

5) Совокупность известных свойств представляет собой сведения об объекте. Эти сведения могут быть переданы и рассмотрены пользователем как информация об объекте.

6) Сообщение – форма представления сведений в виде речи, графики, текста и т.п. В лучшем случае – сообщение не искажается.

7) Принимать сообщение и получить из него информацию значит уменьшить неопределенность своих знаний об объекте.

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

4. Свойства объектов и информация о них. Соотношения между объективно существующими свойствами и информацией.

5. Данные и информация. Меры объема данных и количества информации.

Основные характеристики данных: объем, доступность, ценность, оперативность.

Минимальный объем данных характеризует 1 разряд двоичной системы и называется «байт» (8 бит = 1 байт).

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

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

Оперативность – характеристика данных, определяющая, насколько быстро этими данными можно воспользоваться.

6. Адекватность информации. Синтаксическая, систематическая и прагматическая объективности информации.

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

Различают 3 формы адекватности:

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

· Семантическая форма адекватности – смысловая адекватность.

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

7. Понятие ценности, оперативности и доступности информации. Меры количества информации. См. вопрос 5.

8. Меры информации синтаксического, семантического и прагматического уровней.

9. Кодирование информации. Кодирование непрерывных и дискретных сообщений.

Свойства объекта ®

(правило для всех объектов)

Если есть возможность описать некоторые правила над множеством объектов, а правила эти позволяют ставить в соответствие свойства объектов и информацию о них, то h называют языком.

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

Непрерывные сообщения – это те сообщения, которые передаются значениями непрерывно изменяемых величин (сила тока, яркость света и т.п.) Кодирование непрерывных величин с помощью дискретных сообщений производится так:

· пусть непрерывная величина может принимать значение из области значений N;

· тогда область изменения этой непрерывной величины надо поделить на участки, которые не пересекаются;

· каждому участку присваиваем номер. Кодирование сводится к присваиванию номеру участка значения непрерывной величины в нем. Если увеличить дискретность (взять большее количество участков), неточность представления непрерывной величины уменьшится.

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

10. Знаки. Коды, как отображение знаков. Алфавит.

Знак - элемент из конечного множества попарно различных элементов, каждый из которых называется символом.

Алфавит – упорядоченный набор знаков. Если имеется алфавит, состоящий из двух знаков, и имеется слово длиной k, из всего множества сообщений можно сделать не больше, чем 2^k различных сообщений.

11. Кодирование дискретных сообщений. Цепочки знаков.

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

Слова в двоичном алфавите будем называть двоичными словами.

12. Коды постоянной и переменной длины.

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

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

Если разным знакам исходного алфавита могут ставится в соответствие слова разной длины, то такие коды называются кодами переменной длины (пример: код точки – 2 знака, код буквы Т – 1 знак и т.п.)

13. Последовательная и параллельная передача сообщений.

При последовательной передаче сообщение передается один разряд за другим.

При параллельной передаче сообщения все разряды сообщения передаются единовременно.

14. Системы счисления. Алфавит системы счисления.

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

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

15. Позиционные и непозиционные системы счисления.

Все системы счисления делятся на позиционные и непозиционные. В позиционных системах значение цифры зависит от ее положения, в непозиционных – нет.

Примером непозиционной системы счисления является римская. В ней каждый знак значит одно и то же числе вне зависимости от того, на каком месте он находится.

К позиционным системам относятся большинство используемых систем. В них количественное значение цифры зависит от ее позиции в числе. В позиционных системах основание системы равно количеству цифр (знаков в ее алфавите) и определяет, во сколько раз различаются значения цифр соседних разрядов числа.

16. Двоичная система счисления. Перевод целых десятичных чисел в двоичную систему счисления.

В двоичной системе счисления основание равно 2, а алфавит состоит из 2-х цифр: 0, 1. Следовательно, числа в развернутой форме записываются в виде суммы ряда степеней основания 2 с коэффициентами, в качестве которых выступают цифры 0 или 1.

A=a_n-12^n-1 + a_n-22^n-2 + … + a₁2¹ + a₀2⁰

Перевод чисел из одной системы счисления в другую осуществляется следующим образом:

· число записывается в исходной системе счисления;

· затем делится на основание требуемой системы;

· остаток от деления записывается в младший разряд результата;

· частное от деления снова делится на основание и т.д.

Когда частное становится меньше основания новой системы, оно записывается в старший разряд исходного числа.

17. Двоичная система счисления. Перевод двоичных чисел в четверичную, восьмеричную и шестнадцатеричную системы счисления.

Для перевода двоичного числа в системы счисления с основанием – степенью 2 пользуются тем, что для записи всех цифр новой системы используются все комбинации 0 и 1 целого числа разрядов двоичной системы. Для четверичной – 2 разряда, для восьмеричной – 3, для шестнадцатеричной – 4.

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

101 001₂ = 1*2²+0*2¹+1*2⁰ 0*2²+0*2¹+1*2⁰ = 51₈

Для упрощения преобразований можно заранее пользоваться готовыми таблицами преобразований.

18. Системы счисления. Восьмеричная система счисления. Перевод целых десятичных чисел в восьмеричную систему счисления. См. вопрос 16.

19. Системы счисления. Шестнадцатеричная система счисления. Перевод целых шестнадцатеричных чисел в восьмеричную и двоичную системы счисления. См в. 16 и 17.

20. Системы счисления. Перевод чисел из одной системы счисления в другую. Метод деления на основание. См. вопрос 16.

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

Перевод десятичной дроби в систему с другим основанием осуществляется следующим образом:

· переводят целую часть по известным правилам (вопрос 16);

· дробную часть умножают на основание новой системы;

· целую часть результата записывают первой цифрой после запятой;

· оставшуюся дробную часть снова умножают на основание и т.д.

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

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

23. Системы счисления. Операция сложения в позиционной системе счисления.

24. Системы счисления. Операция умножения в позиционной системе счисления.

25. Числовые коды в системах передачи, хранения и преобразования информации.

26. Представление числовой информации в ЭВМ. Числа с фиксированной и плавающей запятой (точкой).

В ЭВМ числовая информация записывается в двоичной системе счисления. Существует 2 формы представления числе, используемых в ЭВМ: целые числа и числа с плавающей точкой.

Для хранения целых положительных числе используется 1 ячейка памяти (8 бит), для хранения целых чисел – 16 бит, для хранения больших целых чисел – 32 бита. С учетом выделения 1 разряда для знака для хранения больших целых чисел используется 31 разряд. Т.о., максимальное двоичное число в ЭВМ равно 1*2³⁰+1*2²⁹+…+1*2⁰.

Числа с плавающей запятой записываются в виде:

A = m*qⁿ,

где m – мантисса числа, q – основание системы счисления, n – порядок числа.

В числах с плавающей запятой арифметические операции производятся отдельно над мантиссой и порядком.

В ЭВМ числа одинарной точности занимают 32 бита, а числа двойной точности – 64 разряда. В случае чисел двойной точности для хранения порядка отводится 11 бит (из них 1 бит для знака порядка)и для хранения мантиссы числа – 53 бита (из них 1 бит для знака мантиссы).

Максимальное значение порядка числа составит 1024₁₀.

27. Представление числовой информации в ЭВМ. Прямой, обратный и дополнительный коды. ХЗ (должно было быть на семинарах, но «так сказать в общем …»

28. Представление числовой информации в ЭВМ. Смешанный код. Аналогично.

29. Погрешности представления числовой информации в ЭВМ. Аналогично.

30. Представление графической информации в ЭВМ. Кодировка ACSII.

Для кодировки одного символа используется 1 байт памяти. Т.о. возможно закодировать 256 (2⁸) символов. Кодирование заключается в том, что каждому символу в соответствие ставится уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111.

Таблица, в которую записаны значения кодов для определенных символов алфавитов, носит название стандарта ACSII.

31. Представление графической информации в ЭВМ. Различные виды символьных кодировок.

32. Представление графической информации в ЭВМ. Кодировка цвета.

Графическая информация на экране монитора представляется в виде растрового изображения, которое формируется из определенного количества строк, содержащих определенное количество точек (пикселей).

Цвет каждого пикселя (для цветного изображения) складывается из трех основных цветов RGB. Для записи яркости каждого цвета при 24-битной глубине цвета (True Color) используется 1 байт (0…255 значений).

33. Логические операции. Высказывания. Сложные высказывания.

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

Сложное высказывание – это высказывание, которое образуется путем объединения простых высказываний. Объединение этих высказываний осуществляется с помощью логических союзов: И, ИЛИ, НЕ, Следствие.

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

Функции, которые характеризуют логические союзы, называются логическими функциями.

34. Аксиомы алгебры логики.

35. Основные законы алгебры логики.

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

1) Закон тождества: А = А (если в сложном высказывании несколько раз используется одно и то же простое высказывание, то оно везде имеет одинаковое значение).

2) Закон двойственного отрицания: А= не(не(А)).

3) Коммутативность: АÙВ = ВÙА, АÚВ = ВÚА.

4) Ассоциативность: (АÙВ)ÙС = АÙ(ВÙС), (АÚВ)ÚС = АÚ(ВÚС).

5) Дистрибутивность: (АÙВ)Ú(АÙС) = АÙ(ВÚС); (АÚВ)Ù(АÚС) = АÚ(ВÙС).

6) Закон исключения констант: АÙне(А) = 0; АÚне(А) = 1.

7) Законы Моргана: не(АÚВ) = не(А)Ùне(В); не(АÙВ) = не(А)Úне(В).

36. Логические операции И, ИЛИ, НЕ. Таблицы истинности.

Наиболее распространенными являются логические союзы И (Ù), ИЛИ (Ú), НЕ. Их значения для всех различных значений их аргументов записаны в таблицах истинности.

А	В	не(А)	АÙВ	АÚВ

Логическую операцию И называют еще логическим сложением, а логическую операцию ИЛИ – логическим умножением.

37. Функции алгебры логики. Табличное задание логической функции одной переменной.

Любое составное высказывание можно рассматривать как логическую функцию F(A, B, C, D, …), аргументами которой являются логические переменные A, B, C, D, … (простые высказывания). Сама функция и аргументы могут принимать только 2 различных значения «истина» и «ложь». Логическая функция имеет только 2 различных значения аргумента. Можно определить, какое количество различных функций может существовать: 2¹ = 2.

Таблица истинности для функций одной переменно выглядит так:

А	F1	F2

Здесь F₁ – функция эквивалентности, F₂ – функция отрицания.

38. Функции алгебры логики. Табличное задание логической функции двух переменных.

Т.к. каждая логическая функция 2-х аргументов имеет 4 возможных набора значений аргументов, число таких функция составляет 2⁴ = 16.

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

Здесь принимаем функцию отрицания как функция 2-х аргументов, один из которых равен 0. Заметим, что F₂ – логическое умножение, F₈ – логическое сложение, F₁₃ – логическое отрицание А, F₁₁ – логическое отрицание В.

39. Нормальная форма представления логической функции. Минтермы и макстермы.

40. Формы представления логической функции. СДНФ логической функции.

41. Формы представления логической функции. СКНФ логической функции.

42. Логический синтез переключательных схем. Функция проводимости.

1)		повторитель
2)		генератор «0»
3)		генератор «1»
4)		если х=1 – ток идет
5)		если х=1 – ток не идет

Пусть x, y, z, t – 4 переключателя. Задача: должен быть замкнут x и один из 3-х других переключателей. G = x*(y + z + t) – проводимость.

Реализация: .

Задача: ток должен протекать, когда замкнуты любые 4 переключателя x, y, z, t, v.

Реализация: (один из 5-ти разомкнут).

43. Техническая реализация логической операции. Логические элементы.

Базовые логические элементы реализуют 3 основные логические операции:

1)		операция И
2)		операция ИЛИ
3)		операция НЕ

На входы логических элементов последовательно подаются 4 пары сигналов (для И и ИЛИ). На выходе в зависимости от пары исходных сигналов (аргументов той или иной функции) выдается сигнал, несущий результирующее значение логической функции.

44. Синтез вычислительных схем. Однозарядный сумматор на логических элементах.

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

1) Схема полусумматора.

Пусть A, B – слагаемые, P – перенос, S – сумма.

A	B	P	S

Функция P реализуется элементом как AÙB. Функция S реализуется более сложно:
S = (AÚB)ÙНЕ(AÙB). Проверяется с помощью таблицы истинности.

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

Полный одноразрядный сумматор имеет 3 входа: А, В, Р₀ – перенос из младшего разряда, и два выхода – сумма S и перенос P.

Тогда таблица сложения имеет вид?

А	В	Р0	Р	S

P = (AÙB)Ú(AÙP₀)Ú(BÙP₀); S = (AÚBÚP₀)ÙНЕ(P).

45. Понятие алгоритма. Свойства алгоритма.

Алгоритм – некоторый конечный набор правил или команд (указанный), позволяющий исполнителю решать любую конкретную задачу из некоторого класса объектов. Алгоритмы могут быть записаны в виде некоторых символов, либо в виде записи алгоритмическим языком программирования.

Свойства алгоритмов

1) массовость (конкретный алгоритм применим к большому числу исходных данных);

2) детерминированность (однозначность определения алгоритма);

3) результативность (результат получается за конечное число циклов, на каждом шаге можно получить промежуточный результат).

46. Алгоритмы. Описание алгоритмов. Блок-схемы алгоритмов.

См. вопрос 45.