- •Информатика Учебное пособие
- •Содержание
- •Предисловие
- •Тема 1. Введение
- •1.1. Цель и задачи курса «Информатика»
- •1.2. Объекты и составные части информатики
- •1.3. Информатика как единство науки и технологии
- •Контрольные вопросы
- •Тема 2. Основные понятия информатики
- •2.1. Место информатики в системе наук
- •2.2. Основные понятия курса «Информатика»
- •Предмет информатики составляют следующие понятия:
- •Информация классифицируется по видам. (рис. 2.4.)
- •Тема 3. Основы дискретной математики.
- •3.2. Основы логики
- •Элементарные булевые функции
- •Из них выделим функцию "отрицание X" (обозначается -X). Эта функция представлена в таблице
- •3.3. Графы и деревья
- •А) граф g; б) остов графа g; в) другой остов графа g
- •Тема 4. Основные понятия архитектуры эвм
- •Для представления числовых данных в эвм используются естественная и нормальная формы записи чисел.
- •4.2. Системы счисления. Правила перевода чисел из одной системы счисления в другую
- •3. Арифметические операции
- •4.3. Логические элементы компьютера
- •В качестве важных последовательностных схем, выполняемых на одной ис, можно отметить счетчики, сдвиговые регистры, элементы памяти и др.
- •Структурная схема базовой модели мп фирмы Intel представлена на рисунке 4.15.
- •4.5. Организация памяти компьютера
- •Используется два основных типа оперативной памяти:
- •Контрольные вопросы
- •Тема 5. Алгоритмическое решение задач, анализ алгоритмической сложности.
- •5.1. Стратегия решения задач.
- •5.2. Алгоритмы (свойства, реализация алгоритмов)
- •5.3. Структуры данных
- •5.4. Основные вычислительные алгоритмы.
- •5.5. Анализ алгоритмов
- •1. Сравнительные оценки алгоритмов
- •2. Система обозначений в анализе алгоритмов
- •3. Классификация алгоритмов по виду функции трудоёмкости
- •4. Асимптотический анализ алгоритмов
- •Контрольные вопросы
- •Тема 6. Знакомство с языками программирования.
- •6.1. Обзор языков программирования
- •6.2. Основные конструкции программирования
- •Внутри программы значение свойств можно изменять как угодно часто.
- •Константы.
- •На практике наибольшее распространение получили язык функционального программирования lisp и два его диалекта: язык Common lisp и язык Scheme.
- •Наиболее распространенным языком логического программирования является язык Prolog (Пролог).
- •Контрольные вопросы
- •Тема 7. Основы операционных систем
- •7.1. Основные концепции операционных систем
- •7.4. Файловые системы
- •7.6. Обзор современного прикладного программного обеспечения
- •Контрольные вопросы
- •Тема 8. Сети и телекоммуникации
- •Компоненты сети
- •По программной совместимости эвм: однородные (гомогенные) и неоднородные (гетерогенные);
- •8.3. Системы телекоммуникаций
- •Типы телекоммуникационных систем
- •Системы телевещания
- •Системы подвижной связи
- •Сети сотовой подвижной связи
- •Сети транкинговой связи
- •Сети персонального радиовызова
- •Сети мобильной спутниковой связи
- •Волоконно-оптические сети
- •Контрольные вопросы:
- •Тема 9. Сеть Internet
- •9.1. Теоретические основы Internet
- •9.2. Основные понятия (сайт, сокет, сервер, клиент). Web как пример архитектуры «клиент-сервер»
- •9.3. Службы Internet
- •Контрольные вопросы:
- •Тема 10. Графическое программное обеспечение
- •10.1. Иерархия графического программного обеспечения. Графические коммуникации. Графические системы.
- •10.2. Системы растровой и векторной графики
- •Описание объекта является простым и занимает мало памяти;
- •10.3. Графические редакторы
- •Контрольные вопросы
- •Тема 11. Основы защиты информации
- •11.1. Информационная безопасность и ее составляющие
- •11.2. Угрозы безопасности информации и их классификация
- •11.3. Сетевая безопасность
- •11.4. Антивирусные программы
- •Контрольные вопросы
А) граф g; б) остов графа g; в) другой остов графа g
Понятие дерева как математического объекта было впервые предложено Кирхгофом в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей.
Ориентированное дерево (называемое также древовидностью) определяется аналогичным образом.
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины х1), равна единице, а полустепень захода вершины х1 (называемой корнем этого дерева) равна нулю.
На рисунке 3.8 показан граф, который является ориентированным деревом с корнем в вершине х1. Из приведенного определения следует, что ориентированное дерево с п вершинами имеет n-1 дуг и связно. Также очевидно, что не всякий ориентированный граф содержит основное ориентированное дерево. Это подтверждает граф, изображенный на рисунке 3.9.
Рисунок 3.9. Ориентированное дерево
Рисунок 3.10. Граф без ориентированного основного графа
Следует отметить, что неориентированное дерево можно преобразовать в ориентированное: надо взять его произвольную вершину в качестве корня и ребрам приписать такую ориентацию, чтобы каждая вершина соединялась с корнем (только одной) простой цепью.
Обратно, если Т= (X, В) - ориентированное дерево, то Т = (X, В), где В — множество дуг дерева Т без учета их ориентации, является неориентированным деревом.
«Генеалогическое дерево», в котором вершины соответствуют лицам мужского пола, а дуги ориентированы от родителей к детям, представляет собой хорошо известный пример ориентированного дерева. Корень в этом дереве соответствует «основателю» рода (лицу, родившемуся раньше остальных).
Контрольные вопросы
Что называется множеством?
Назовите виды множества.
Из чего состоит множества?
Охарактеризуйте основные операции над множествами.
В каком году был создан аппарат алгебры логики и кем?
Что является основным понятием булевой алгебры и дайте его определение?
Из чего состоит аппарат булевой алгебры, как формальной математической системы?
Охарактеризуйте основные базовые операции булевой алгебры.
Какие таблицы истинности Вы знаете?
Дайте характеристику аксиомам алгебры логики.
Что называется булевой функцией?
Чем может быть представлена булевая функция?
Приведите формулы логики булевых функций.
Дать понятие «графу».
Назовите виды графов и дайте их определения.
Как определяется число ребер графа?
Дайте определения понятиям: «маршрут», «компонента связности», «путь», «цикл», «эйлеровый цикл», «гамильтовый цикл».
Как задается граф?
Что называется деревом?
Какие бывают деревья? Покажите их графически.
Тема 4. Основные понятия архитектуры эвм
4.1. Представление данных в компьютере
Вопросы представления информации в ЭВМ любого типа и класса включают два основных аспекта: используемая базовая система счисления (с.с.) и собственно представление числовой и алфавитно-цифровой информации.
Исходя из современных микроэлектронных технологий и неймановского принципа адресации к памяти показано, что цифровые элементы на основе двоичной с.с. оптимальны для обеспечения максимальной производительности ЭВМ. Поэтому наиболее распространенными с.с. являются системы с 2к-основанием (к=1, 2, 4), это же относится и к разрядности ЭВМ, кратной двум.
Для оценки количества информации и упорядочения процесса ее обработки используются структурные единицы информации. За единицу информации принимается один бит. Бит определяет количество информации, посредством которой выделяется одно из двух альтернативных состояний. В одном бите с помощью цифр 0 и 1 может быть представлен один двоичный разряд числа или одна логическая переменная, принимающая соответственно значения ложь или истина. Последовательность битов, имеющая определенный смысл, называется полем.
Рис. 4.1. Структурные единицы информации
Поле длиной 8 бит называется байтом. Байт, как правило, является минимальной (неделимой) единицей информации, с которой оперирует ЭВМ. Все остальные единицы информации являются его производными (рис. 4.1).
Вычислительная машина оперирует с двумя видами информации: управляющей информацией и числовыми данными. Управляющая информация (программа работы машины) состоит из последовательности команд ЭВМ, с помощью которых производится обработка числовых данных.
Основной структурной единицей информации, обрабатываемой ЭВМ, является машинное слово. В современных ЭВМ длина машинного слова обычно составляет от 2 до 4 байт. Как правило, в одном машинном слове может быть представлено либо одно число, либо одна команда. Однако допускаются переменные форматы представления числовой и управляющей информации.
Байт 0 |
Байт 1 |
Байт 2 |
Байт 3 |
Байт 4 |
Байт 5 |
Байт 6 |
Байт 7 |
Полуслово |
Полуслово |
Полуслово |
Полуслово | ||||
Слово |
Слово | ||||||
Двойное слово |
Рис. 4.2. Форматы единиц информации, обрабатываемых в ЭВМ
Для обеспечения требуемой точности вычислений и экономии памяти большинство ЭВМ могут оперировать также с двойным словом, с полусловом или с одним байтом информации (рис. 4.2).
Последовательность полей, байтов или слов, имеющих одинаковый смысл, образуют массив. Группа массивов может объединяться в сегмент. Количество информации в больших массивах оценивается с помощью производных единиц, кратных количеству байтов в степени числа два (1К байт=1024 байт=210 байт; 1М байт= 1048576 байт = =220 байт).