- •1. ИНФОРМАЦИЯ, ЕЁ СВОЙСТВА, ИЗМЕРЕНИЕ, ПРЕДСТАВЛЕНИЕ И КОДИРОВАНИЕ
- •1.1. Информатика – предмет и задачи
- •1.2. Информация, ее виды и свойства
- •1.3. Представление об информационном обществе
- •1.4. Кодирование информации
- •1.5. Практическое занятие № 1. Системы счисления. Перевод чисел из одной системы счисления в другую. Арифметические операции в позиционных системах счисления
- •1.6. Кодирование текстовых и символьных данных
- •1.7. Кодирование графических данных
- •1.8. Кодирование звуковой информации
- •1.9. Структуры данных
- •1.10. Файлы и файловая структура
- •1.11. Измерение и представление информации
- •1.12. Теоремы Шеннона
- •1.13. Математические основы информатики
- •1.13.1. Алгебра высказываний (алгебра логики)
- •1.13.2. Элементы теории множеств
- •2. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
- •2.1. История развития вычислительной техники
- •2.2. Классификация компьютеров по сферам применения
- •2.3. Базовая система элементов компьютерных систем
- •2.4. Функциональные узлы компьютерных систем
- •2.5. Архитектура ЭВМ
- •2.6. Совершенствование и развитие архитектуры ЭВМ
- •2.6.1. Архитектуры с фиксированным набором устройств
- •2.6.2. Открытая архитектура
- •2.6.3. Архитектура многопроцессорных вычислительных систем
- •2.7. Внутренняя структура ЭВМ
- •2.7.4. Внешние запоминающие устройства
- •2.8. Внешние устройства компьютера
- •2.8.1. Видеотерминалы
- •2.8.2. Устройства ручного ввода информации
- •2.8.3. Устройства печати
- •2.8.4. Устройства поддержки безбумажных технологий
- •2.8.5. Устройства обработки звуковой информации
- •2.8.6. Устройства для соединения компьютеров в сеть
- •3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЭВМ
- •3.1. Состав системного программного обеспечения
- •3.2. Операционные системы
- •3.3. Виды операционных систем и их базовые понятия
- •3.4. Процессы и потоки
- •3.5. Управление памятью
- •3.6 Организация ввода-вывода
- •3.7 Драйверы устройств
- •3.8 Файловые системы
- •3.9 Файловые системы Microsoft Windows
- •3.9.1. Файловая система FAT16
- •3.9.3. Файловая система NTFS
- •3.9.4. Сравнение файловых систем FAT16, FAT32 и NTFS
- •3.10 Операционная система Windows
- •3.11 Служебные программы
- •3.13 Прикладное программное обеспечение
- •3.13.1. ППО общего назначения
- •3.13.2. ППО специального назначения
- •3.17. Практическое занятие № 6. Табличный процессор Excel. Основные понятия и общие принципы работы с электронной таблицей. Создание и заполнение таблиц постоянными данными и формулами. Построение диаграмм и графиков
- •3.18. Практическое занятие № 7. Табличный процессор Excel. Сортировка и фильтрация (выборка) данных. Сводные таблицы, структурирование таблиц. Расчёты в Excel
- •4. БАЗЫ ДАННЫХ (БД) И СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ (СУБД)
- •4.1. Базы данных в структуре информационных систем
- •4.2. Классификация баз данных и виды моделей данных
- •4.3. Нормализация отношений в реляционных базах данных
- •4.4. Проектирование баз данных
- •4.5. Этапы развития СУБД. Реляционная СУБД Microsoft Access – пример системы управления базами данных
- •4.6. Практическое занятие № 8. СУБД Access 97. Создание однотабличной базы данных. Отбор данных с помощью фильтра. Формирование запросов и отчётов для однотабличной базы данных
- •5. КОМПЬЮТЕРНЫЕ СЕТИ И ОСНОВЫ ЗАЩИТЫ ИНФОРМАЦИИ
- •5.1. Назначение и классификация компьютерных сетей
- •5.2. Режимы передачи данных в компьютерных сетях
- •5.3. Типы синхронизации данных при передаче и способы передачи информации
- •5.4. Аппаратные средства, применяемые при передаче данных
- •5.5. Архитектура и протоколы компьютерных сетей
- •5.6. Локальные вычислительные сети (ЛВС) и их топологии
- •5.7. Физическая передающая среда ЛВС и методы доступа к ней
- •5.8. Примеры сетей. Глобальная сеть Интернет
- •5.9. Службы сети Интернет
- •5.10. Поиск информации в Интернет
- •5.10.1. Поисковые машины
- •5.12. Основы и методы защиты информации
- •5.13. Политика безопасности в компьютерных сетях
- •5.14. Способы и средства нарушения конфиденциальности информации
- •5.15. Основы противодействия нарушению конфиденциальности информации
- •5.16. Криптографические методы защиты данных
- •5.17. Компьютерные вирусы и меры защиты информации от них
- •6. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ. МОДЕЛИ И ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ
- •6.1. Алгоритм и его свойства
- •6.1.2. Графическое представление алгоритмов
- •6.2. Принципы разработки алгоритмов и программ для решения прикладных задач
- •6.2.1. Процедурное программирование
- •6.2.3. Функциональное программирование
- •6.2.4. Логическое программирование
- •6.2.5. Объектно-ориентированное программирование (ООП)
- •6.3. Методы и искусство программирования
- •6.4. Обзор языков программирования
- •6.5. Понятие о метаязыках описания языков программирования
- •6.6. Моделирование как метод решения прикладных задач
- •6.7. Основные понятия математического моделирования
- •6.8. Информационное моделирование
- •6.9. Практическое занятие № 11. Вычисления в среде Mathcad
- •6.10. Практическое занятие № 12. Вычисления в среде Matlab
- •СПИСОК ЛИТЕРАТУРЫ
- •ОГЛАВЛЕНИЕ
Продолжение таблицы 1.12
Но- |
Бук- |
Код |
ni |
Pi |
ni Pi |
Pi log2 Pi |
мер |
ва |
|
|
|
|
|
16 |
ь |
11100 |
5 |
0.0294 |
0.1470 |
-0.1496 |
17 |
й |
11101 |
5 |
0.0294 |
0.1470 |
-0.1496 |
18 |
о |
11110 |
5 |
0.0294 |
0.1470 |
-0.1496 |
19 |
з |
11111 |
5 |
0.0294 |
0.1470 |
-0.1496 |
|
|
|
|
å Pi = 1 |
åni Pi = 4.00 |
- åPi log2 Pi = |
|
|
|
|
i |
i |
i |
|
|
|
|
|
|
= 3.9844 |
~
Математическое ожидание количества символов из алфавита B при кодировании равно nср = åni Pi = 4 . Этому среднему числу символов соответствует максимальная
i |
|
|
|
|
|
энтропия Hmax = nср log2 q = 4×log2 2 = 4 . |
Для обеспечения передачи информации, |
||||
содержащейся |
в |
сообщении, |
должно |
выполняться |
условие |
Hmax = nср log2 q ³ H = -åPi log2 Pi . В этом случае закодированное сообщение имеет
i
избыточность. Коэффициент избыточности определяется следующим образом:
Kи = (Hmax - H ) = (nср - nmin ), (1.12.1)
nср
nmin = H log2 q . В нашем случае Kи = 0.0039 , т. е. код практически не имеет избыточности.
Видно, что среднее число двоичных символов стремится к энтропии сообщения.
Вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Оказывается, что даже при наличии помех в канале связи всегда можно найти такую систему кодирования, при которой сообщение будет передано с заданной достоверностью. Основная идея всех таких кодов такова: для исправления возможных ошибок вместе с основным сообщением нужно передавать какую-то дополнительную информацию. Для реализации контроля возможных ошибок используются так называемые самокорректирующие коды, а по каналу связи вместе с n символами основного сообщения передаются ещё k дополнительных символов, обеспечивающих избыточность кодирования и позволяющих противодействовать помехам.
1.13.Математические основы информатики
1.13.1.Алгебра высказываний (алгебра логики). Учение о высказываниях – алгебра высказываний или алгебра логики является простейшей логической теорией. Она рассматривает конечные конфигурации символов и взаимоотношения между ними.
Высказывание – это всякое повествовательное предложение, утверждающее что-либо
очем-либо, при этом непременно истинное или ложное. Логическими значениями высказываний являются “истина” и “ложь”, обозначаемые 1 и 0. Высказывания, представляющие собой одно утверждение, называются простыми или элементарными, высказывания, получающиеся из элементарных с помощью грамматических связок “не”, “и”, “или”, “если… , то…”, называются сложными. Эти названия не носят абсолютного характера, высказывания, которые в одной ситуации можно считать простыми, в другой ситуации будут сложными. В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, житейское содержание игнорируется. Каждое высказывание может быть либо истинным, либо ложным, ни одно высказывание не может быть одновременно истинным и ложным. Элементарные высказывания обозначаются
31
строчными буквами латинского алфавита: а, b, с. Из высказываний с помощью логических связок образуются новые высказывания. Рассмотрим наиболее употребительные логические связки.
Отрицанием высказывания x называется новое высказывание, которое является истинным, если высказывание x ложно, и ложным, если x – истинно. Обозначается x , читается “не x ” или “неверно, что x ”. Все логические значения высказывания x можно описать с помощью табл. 1.13. Если x – высказывание, то x - противоположное высказывание. Тогда можно образовать х , которое называется двойным отрицанием
высказывания. Логические значения х , очевидно, совпадают со значениями x . Эта операция одноместная – в том смысле, что из одного данного простого высказывания x строится
новое высказывание x .
Логическое умножение (конъюнкция). Конъюнкцией двух высказываний x и y
называется новое высказывание z , которое истинно только когда оба высказывания x и y истинны, и ложно, когда хотя бы одно из x и y ложно. Обозначается x & y или x y , читается “ x и y ”. Таблица истинности конъюнкции дана в табл. 1.14. Из определения
операции конъюнкции видно, что союз “и” в алгебре логики употребляется в том же смысле, что и в повседневной речи. Однако в алгебре логики этой связкой можно связывать любые, сколь угодно далекие по смыслу высказывания. Конъюнкцию часто называют логическим умножением.
Таблица 1.13 |
Таблица 1.14 |
x |
|
|
|
|
x |
||
1 |
|
0 |
|
0 |
|
1 |
x |
y |
x y |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
Логическое сложение (дизъюнкция). Дизъюнкцией двух высказываний x и y
называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x и y истинно, и ложным, если они оба ложны. Обозначается x y , читается
“ x или y ”. Логические значения дизъюнкции описываются в табл.1.15.
Таблица 1.15 Таблица 1.16
x |
y |
x y |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
x |
y |
x → y |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Импликация или логическое следование. Импликацией двух высказываний x и y
называется новое высказывание, которое считается ложным, когда x истинно, а y ложно, и истинным во всех остальных случаях. Обозначается x → y , читается “если x , то y ” или “из x следует y ”. Высказывание x называется условием или посылкой, высказывание y
следствием или заключением. Таблица истинности этой операции приведена в табл. 1.16. Из таблицы истинности видно, что если условие x - истинно, и истинна импликация x → y , то
верно, и заключение y . Это классическое правило вывода, постоянно используется в
математике, при переходе от одних высказываний к другим, с помощью доказываемых теорем, которые, как правило, имеют форму импликаций.
32
В случае импликации несоответствие между обычным пониманием истинности сложного высказывания и идеализированной точкой зрения алгебры высказываний еще заметнее, чем для других логических операций. Здесь истинность импликации в некоторой ситуации означает лишь, что если в этой ситуации истинна посылка, то истинно и заключение.
Эквиваленция (эквивалентность, логическая эквивалентность). Эквиваленцией двух высказываний x и y называется новое высказывание, которое истинно, когда оба
высказывания x и y либо одновременно истинны, либо одновременно ложны, и ложно во всех остальных случаях. Обозначается x ↔ y , читается “для того, чтобы x , необходимо и достаточно, чтобы y ” или “ x тогда и только тогда, когда y ”. Эквивалентность играет значительную роль в математических доказательствах. Известно, что большое число теорем
Таблица 1.17
x |
y |
x ↔ y |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
формулируется в форме необходимых и достаточных условий. Это так называемые теоремы существования. Логические значения операции эквиваленции описываются в табл. 1.17.
С помощью логических операций над высказываниями можно строить различные новые, более сложные высказывания. Всякое сложное высказывание, которое может быть получено из элементарных высказываний с помощью логических связок, называется формулой алгебры логики. Формулы алгебры логики обозначаются большими буквами латинского алфавита А, В, С,… Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний. Равносильность обозначается знаком “ ≡ ”.
Для любых формул A, B, C справедливы следующие равносильности.
I.Основные равносильности:
1.A Ù A º A,ü
ý- законы идемпотентности конъюнкции и дизъюнкции,
2.A Ú A º A,þ
3.A 1 ≡ A, 1 - истина,
4.A 1 ≡ 1,
5.A 0 ≡ 0, 0 - ложь,
6.A 0 ≡ A,
7. A Ù |
A |
º 0 - закон противоречия, |
(1.13.1) |
8.A Ú A º 1 - закон исключенного третьего,
9.A º A - закон снятия двойного отрицания, 10. A Ù (B Ú A) º A - первый закон поглощения,
11.A Ú (B Ù A) º A - второй закон поглощения,
12.A º (A Ù B)Ú (A Ù B) - первая формула расщепления,
13.A º (A Ú B)Ù (A Ú B) - вторая формула расщепления. Все эти соотношения легко проверяются по таблицам истинности.
33
II.Равносильности, выражающие одни логические операции через другие:
1. A ↔ B ≡ (A → B) (B → A) ≡ (A B) ( |
|
|
|
)≡ ( |
|
B) ( |
|
A) - |
основная |
|||||||||||||||||
A |
B |
A |
B |
|||||||||||||||||||||||
формула доказательств теорем существования, |
|
|||||||||||||||||||||||||
2. A → B ≡ |
|
|
B ≡ |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
(A |
|
|
|
), |
|
|||||||||||||||||||
A |
B |
|
||||||||||||||||||||||||
3. A B ≡ |
|
|
→ B ≡ |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
, |
|
|
|||||||||||||||
|
A |
A |
B |
|
||||||||||||||||||||||
4. A B ≡ |
|
|
|
|
|
|
|
|
||||||||||||||||||
(A → |
|
)≡ |
|
|
|
, |
(1.13.2) |
|||||||||||||||||||
B |
A |
B |
5.A B ≡ A B - первый закон де Моргана ,
6.A B ≡ A B - второй закон де Моргана,
7.A B ≡ A B,
8.A B ≡ A B.
Именно из равносильностей этой группы формул следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание.
III. Равносильности, выражающие основные законы алгебры логики:
1.A B ≡ B A - коммутативный закон конъюнкции,
2.A B ≡ B A - коммутативный закон дизъюнкции,
3. A (B C) ≡ (A B) C - ассоциативность конъюнкции, |
(1.13.3) |
||||
4. A (B C) ≡ (A B) C - ассоциативность дизъюнкции, |
|
|
|||
5. A (B C) ≡ (A B) (A C) - |
дистрибутивность |
конъюнкции |
относительно |
||
дизъюнкции, |
|
|
|
|
|
6. A (B C) ≡ (A B) (A C) - |
дистрибутивность |
дизъюнкции |
относительно |
||
конъюнкции. |
|
|
|
|
|
Формула A |
называется тождественно истинной |
или тавтологией, если она |
|||
принимает значение |
1 при всех значениях входящих в |
нее |
переменных. |
Формула A |
называется тождественно ложной или противоречивой, если она равна 0 при всех значениях входящих в нее переменных.
Формула алгебры логики является функцией входящих в нее элементарных высказываний, ее аргументы принимают два значения 0 и 1, при этом значение формулы может быть равно 0 или 1.
Функцией алгебры логики n переменных (или функцией Буля) называется функция n
логических переменных, то есть функцией алгебры логики |
f (x1 , x2 ,..., xn ) от n переменных |
||||||
x1, x2 ,..., xn называется функция, |
принимающая значения 0, 1, аргументы которой также |
||||||
принимают значения 0,1. |
|
|
|
|
|
||
Функция f (x1 , x2 ,..., xn ) задается своей истинностной таблицей 1.18. |
|||||||
|
|
|
|
|
|
Таблица 1.18 |
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
… |
xn−1 |
xn |
f (x1 , x2 ,..., xn ) |
|
|
0 |
0 |
… |
0 |
0 |
f (0,0,...,0,0) |
|
|
1 |
0 |
… |
0 |
0 |
f (1,0,...,0,0) |
|
|
… |
… |
… |
… |
… |
… |
|
|
1 |
1 |
1 |
1 |
0 |
f (1,1,...,1,0) |
|
|
1 |
1 |
1 |
1 |
1 |
f (1,1,...,1,1) |
|
Огастес Морган (де Морган)(1806 – 1875) – шотландский математик и логик.
34