Обработка информации.
Кодирование, сортировка, вычисление
5. Кодирование текстовой информации Двоичное кодирование текстовой информации в компьютере. Информация, выраженная с помощью естественных и формальных языков в письменной форме, обычно называется текстовой информацией. Для представления текстовой информации (прописные и строчные буквы русского и латинского алфавитов, цифры, знаки и математические символы) достаточно 256 различных знаков. По формуле можно вычислить, какое количество информации необходимо, чтобы закодировать каждый знак: N = 2i => 256 = 2i => 28 = 2i => I = 8 битов.
Для обработки текстовой информации на компьютере необходимо представить ее в двоичной знаковой системе. Для кодирования каждого знака требуется количество информации, равное 8 битам, т. е. длина двоичного кода знака составляет восемь двоичных знаков. Каждому знаку необходимо поставить в соответствие уникальный двоичный код из интервала от 00000000 до 11111111 (в десятичном коде от 0 до 255)
6. Графическая информация на экране монитора представляется в виде растрового изображения, которое формируется из определенного количества строк, которые, в свою очередь, содержат определенное количество точек. Они называются ПИКСЕЛЯМИ. Пиксели бывают только трех цветов - зеленого, синего и красного.
Другие цвета образовываются при помощи смешения цветов. Из трех цветов можно получить восемь комбинаций.
7. Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков. Система счисления:
даёт представления множества чисел (целых и/или вещественных);
даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
отражает алгебраическую и арифметическую структуру чисел.
Позиционная систе́ма счисле́ния (позиционная нумерация) — система счисления, в которой значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда). В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.
Перевод чисел в десятичную систему счисления
Перевод числа из двоичной системы в десятичную. Возьмем любое двоичное число, например 10,112. Запишем его в развернутой форме и произведем вычисления:
10,112 = 1 × 21 + 0 × 20 + 1 × 2-1 + 1 × 2-2 = 1 × 2 + 0 × 1 + 1 × 1/2 + 1 × 1/4 = 2,7510.
Перевод чисел из восьмеричной системы в десятичную.
Возьмем любое восьмеричное число, например 67,58. Запишем его в развернутой форме и произведем вычисления:
67,58 = 6 × 81 + 7 × 80 + 5 × 8-1 = 6 × 8 + 7 × 1 + 5 × 1/8 = 55,62510.
Перевод чисел из шестнадцатеричной системы в десятичную. Возьмем любое шестнадцатеричное число, например 19F16. Запишем его в развернутой форме (при этом необходимо помнить, что шестнадцатеричная цифра F соответствует десятичному числу 15) и произведем вычисления:
19F16 = 1 × 162 + 9 × 161 + F × 160 = 1 × 256 + 9 × 16 + 15 × 1 = 41510.
9. Система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения в последовательности цифр, изображающих число.
Число единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если количество таких цифр равно P, то система счисления называется P-ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления.
Запись произвольного числа x в P-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена. Арифметика действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые соответствуют данному основанию P системы счисления.
10. Отрицательные числа
рассмотрим тип byte, в котором любое число занимает восемь бит. Из записи в двоичной системе счисления равенства (- 1) + 1 = 0 легко найти, xxxxxxxx числа - 1: xxxxxxxx + 00000001 = 00000000
на месте символов xxxxxxxx должно быть расположено число 11111111. Правильным результатом при этом, конечно, следовало бы считать 100000000, а не 00000000, но ведь мы имеем дело с типом byte и, так как результат обязан разместиться в байте, единица <<исчезает>>.
Итак, число - 1 должно кодироваться как 11111111. Дальнейшее уже совсем просто: для получения - 2 нужно - 1 уменьшить на единицу, что даст 11111110; число - 3 представляется как 11111101 и т.д.
Отрицательные числа всегда имеют в своем двоичном представлении единицу в самом старшем разряде, который поэтому называют знаковым, а абсолютная величина кодируемого числа получается как двоичное дополнение остальных бит (нули нужно заменить на единицы и наоборот), увеличенное на один.
Легко видеть, что при этом самым маленьким отрицательным числом, которое принадлежит типу byte, является число - 128 (двоичное представление 10000000), а самым большим -- число 127 (представление 01111111). Все представимыe числа (а их 256) в данном случае могут быть получены как пересечение двух множеств: множества Z всех целых чисел и отрезка [ - 128; 127 ].
Интересным является следующее наблюдение: если число 01111111 увеличить на единицу, то получится 10000000, что означает следующее:
127 + 1 = - 128!!!
Итак, множество элементов типа byte можно представлять себе в виде свернутого в кольцо отрезка
[ - 128; 127 ].
То, что для элементов множества, являющегося машинным аналогом Z, нарушено фундаментальное свойство целых чисел X + 1 > X, способно привести к различным невероятным на первый взгляд результатам, однако гораздо более странные вещи происходят при работе с вещественными числами.
11. Представление чисел в формате с фиксированной запятой. Целые числа в компьютере хранятся в памяти в формате с фиксированной запятой. В этом случае каждому разряду ячейки памяти соответствует всегда один и тот же разряд числа, а "запятая" "находится" справа после младшего разряда, то есть вне разрядной сетки. Максимальное значение целого неотрицательного числа достигается в случае, когда во всех ячейках хранятся единицы. Для n-разрядного представления оно будет равно 2n - 1.
Для хранения целых чисел со знаком отводится две ячейки памяти (16 битов). Представление в компьютере положительных чисел с использованием формата "знак-величина" называется прямым кодом числа. Для представления отрицательных чисел используется дополнительный код. Дополнительный код позволяет заменить арифметическую операцию вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его быстродействие.
12. Логические данные
Теоретической базой для логической обработки данных является формальная логика. Существует несколько систем логики. Одна из наиболее известных – это исчисление высказываний. Высказывание – это любое утверждение, о котором можно сказать, что оно либо истинно, либо ложно.
Исчисление высказываний представляет собой совокупность правил, используемых для определения истинности или ложности некоторой комбинации высказываний.
Исчисление высказываний очень гармонично сочетается с принципами работы компьютера и основными методами его программирования. Все аппаратные компоненты компьютера построены на логических микросхемах. Система представления информации в компьютере на самом нижнем уровне основана на понятии бита. Бит, имея всего два состояния (0 (ложно) и 1 (истинно)), естественным образом вписывается в исчисление высказываний.
Согласно теории, над высказываниями (над битами) могут выполняться следующие логические операции.
Отрицание (логическое НЕ) – логическая операция над одним операндом, результатом которой является величина, обратная значению исходного операнда.
Эта операция однозначно характеризуется следующей таблицей истинности
13. Законы логики
Законы логики отражают наиболее важные закономерности логического мышления, В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений в соответствие с законами логики.
Закон тождества. Всякое высказывание тождественно самому себе: А = А
Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А — истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: A & A = 0
Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: A v A = 1
Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание: A = A
14. Логические элементы — устройства, предназначенные для обработки информации в цифровой форме (последовательности сигналов высокого — «1» и низкого — «0» уровней в двоичной логике, последовательность «0», «1» и «2» в троичной логике, последовательности «0», «1», «2», «3», «4», «5», «6», «7», «8» и «9» вдесятичной логике). Физически логические элементы могут быть выполнены механическими, электромеханическими (на электромагнитных реле), электронными (на диодах и транзисторах), пневматическими, гидравлическими, оптическими и др.
С развитием электротехники от механических логических элементов перешли к электромеханическим логическим элементам (на электромагнитных реле), а затем к электронным логическим элементам на электронных лампах, позже — на транзисторах. После доказательства в 1946 г. теоремы Джона фон Неймана об экономичности показательных позиционных систем счисления стало известно о преимуществах двоичной и троичной систем счисления по сравнению с десятичной системой счисления. От десятичных логических элементов перешли к двоичным логическим элементам. Двоичность и троичность позволяет значительно сократить количество операций и элементов, выполняющих эту обработку, по сравнению с десятичными логическими элементами.
Логические элементы выполняют логическую функцию (операцию) над входными сигналами (операндами, данными).
Всего возможно логических функций и соответствующих им логических элементов, где — основание системы счисления, — число входов (аргументов), — число выходов, то есть бесконечное число логических элементов. Поэтому в данной статье рассматриваются только простейшие и важнейшие логические элементы.
Всего возможны двоичных двухвходовых логических элементов и двоичных трёхвходовых логических элементов (Булева функция).
Кроме 16 двоичных двухвходовых логических элементов и 256 трёхвходовых двоичных логических элементов возможны 19 683 двухвходовых троичных логических элемента и 7 625 597 484 987 трёхвходовых троичных логических элементов (троичные функции).
15. Массив — упорядоченный набор данных, для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа.
Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными, с двумя — двумерными и т. д. Одномерный массив нестрого соответствует вектору в математике, двумерный — матрице. Чаще всего применяются массивы с одним или двумя индексами, реже — с тремя, ещё большее количество индексов встречается крайне редко.
Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.
Формально дерево определяется как конечное множество одного или более узлов со следующими свойствами:
существует один корень дерева
остальные узлы (за исключением корня) распределены среди непересекающихся множеств, и каждое из множеств является деревом; деревья называются поддеревьями данного корня
Связный список - базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
16. Имена внешних носителей информации
Диски, на которых хранится информация в компьютере, имеют свои имена – каждый диск назван буквой латинского алфавита, а затем ставится двоеточие. Так, для дискет всегда отводятся буквы A: и B:. Логические диски винчестера именуются, начиная с буквы C:. После всех имен логических дисков следуют имена дисководов для компакт-дисков. Например, установлены: дисковод для дискет, винчестер, разбитый на 3 логических диска и дисковод для компакт-дисков. Определить буквы всех носителей информации. A: – дисковод для дискет;
C:, D:, E: – логические диски винчестера;
F: – дисковод для компакт-дисков.
17. Этапы развития ЭВМ
Первая страница в истории создания вычислительных машин связана с именем французского философа, писателя, математика и физика Блеза Паскаля. В 1641-42 году он сконструировал механический вычислитель, который позволил складывать и вычитать числа.
В 1673 году немецкий ученый Готфрид Лейбниц построил первую счетную машину, способную выполнять все четыре действия арифметики. Она послужила прототипом арифмометров. На протяжении 19 века было создано много конструкций арифмометров, повысились их надежность и точность вычислений. Они получили очень широкое распространение.
Существенный вклад в совершенствование счетных машин внесли ученые и конструкторы России: Якобсон, Слободский, Штоффель, Куммер, Чебышев. В 1878 году русский учёный П. Чебышев предложил счётную машину, выполнявшую сложение и вычитание многозначных чисел.
Петербургский инженер Однер изобрел арифмометр с зубчаткой, имеющей переменное число зубьев. Его конструкция оказалась настолько совершенна, (прибор позволял довольно быстро выполнять все четыре арифметических действия) что арифмометры этого типа выпускались с 1873 года в течение почти ста лет. И только в 30-е годы XX столетия в нашей стране был разработан более совершенный арифмометр – “Феликс”. Эти счётные устройства использовались несколько десятилетий.
В начале 19 века (1823 – 1834) английский математик Чарльз Беббидж сформулировал основные положения, которые должны лежать в основе конструкции вычислительной машины принципиально нового типа. Задуманный проект машины содержал все основные устройства вычислительных машин: память, арифметическое устройство, устройство управления, устройства ввода-вывода. Реализовать проект этой машины не удалось из-за низкого уровня развития машиностроения. Однако вычислительные программы для этой машины были созданы дочерью Джоржа Байрона Адой Лавлейс, которая по праву считается первой программисткой.
Только через 100 лет в 40-х годах 20 века удалось создать программируемую счетную машину на основе электромеханического реле. Эти машины не успели даже начать выпускать серийно, как появились первые ЭВМ на основе радиоламп.
Первая ЭВМ "Эниак" была создана в США в 1946 г. В группу создателей входил выдающийся ученый 20 века Джон фон Нейман, который и предложил основные принципы построения ЭВМ: переход к двоичной системе счисления для представления информации и принцип хранимой программы. Программу вычислений предлагалось помещать в запоминающем устройстве ЭВМ, что обеспечивало бы автоматический режим выполнения команд и, как следствие, увеличение быстродействия ЭВМ.
Одновременно над проектами ЭВМ работали в Англии и России, где первая ЭВМ, получившая название МЭСМ (малая электронная счетная машина) была разработана в 1950 году, а первая большая ЭВМ - БЭСМ в 1952г. С этого момента началось бурное развитие вычислительной техники. Можно выделить пять этапов в развитии электронных вычислительных машин.
40-50 годы 20 века - первые ЭВМ в США и СССР;
50-60 годы 20 века - первые языки программирования;
60-70 годы 20 века - первые АСУ, САПР, ЕС ЭВМ;
70-80 годы 20 века - первые персональные компьютеры;
80-90 годы 20 века - массовое применение персональных компьютеров.
18. Архитектура вычислительной машины — концептуальная структура вычислительной машины, определяющая проведение обработки информации и включающая методы преобразования информации в данные и принципы взаимодействия технических средств и программного обеспечения.
Принципы работы вычислительной системы Всякая вычислительная система создается для решения некоторого множества вычислительных или информационных задач, которые в совокупности называются задачами обработки данных. Для успешного решения любой задачи в вычислительной системе необходимо иметь:
программу, реализующую алгоритм решения задачи;
аппаратные средства ВС для ввода программы, выполнения программы, получения дополнительной информации и вывода результатов;
дополнительные программные средства, необходимые для решения прикладной задачи
Существует три вида систем обработки данных (СОД
системы реального времени (СРВ), в которых требования к скорости обработки информации очень высокие из-за необходимости решения задач в темпе реального времени (примером являются системы навигации и управления летательными аппаратами);
системы оперативной обработки (СОО),в которых планирование заданий на обработку данных осуществляетсяисходя из требования минимальности времени выполнения каждого полученного задания. Примером такого вида систем является система обработки данных для персонала боевых расчетов пунктов управления;
системы пакетной обработки (СПО), в которых основным требованием является минимизация простоя оборудования при решении поставленных задач.
19. Персональный компьютер (ПК) предназначен для хранения и переработки информации. Информация может представлять собой текст, таблицы, рисунки, фотографии, звукозаписи и т. п. Информация хранится и обрабатывается в цифровом виде. Единица измерения информации - байт. Один байт (1б) соответствует примерно одному символу текста. Для удобства введены также более крупные единицы измерения информации: килобайт (Кб), мегабайт (Мб), гигабайт (Гб).
Современный ПК включает в себя следующие элементы:
системный блок;
монитор;
клавиатура;
мышь;
принтер;
сканер.
Кроме перечисленных, в состав ПК могут входить модем или факс-модем, плоттер, устройства воспроизведения и записи звука и некоторые другие устройства.
Системный блок
В системном блоке размещаются основные устройства ПК, осуществляющие переработку и хранение информации. Непосредственно переработку информации производит процессор, размещенный на материнской плате системного блока. Основная характеристика процессора - его быстродействие, иначе называемое «тактовая частота». Кроме того, на материнской плате системного блока расположено оперативное запоминающее устройство (ОЗУ), или оперативная память1. ОЗУ хранит информацию, в данный момент перерабатываемую процессором. Необходимо отметить, что информация в оперативной памяти хранится только при включенном ПК. После выключения ПК вся информация из ОЗУ пропадает. Основная характеристика ОЗУ - объем хранимой информации. Постоянное хранение информации производится на жестком диске2, который также называют «винчестер». Основная характеристика жесткого диска - объем хранимой информации. Современные офисные ПК оснащены жестким диском объемом 3...7 Гб.
Монитор
Монитор служит для отображения информации. Подавляющее число современных мониторов цветные. Большинство мониторов оснащено электронно-лучевой трубкой и работает по принципу телевизора. Монитор имеет собственную кнопку включения и выключения, а также кнопки или регуляторы для настройки яркости, контрастности и размера изображения. Современные офисные ПК имеют мониторы с размером экрана по диагонали 15" (38 см) или 17" (43 см).
Клавиатура
Клавиатура предназначена для ввода информации и управления ПК.
Мышь
Мышь предназначена для перемещения курсора по экрану и управления различными объектами. В настоящее время чаще всего встречаются двухкнопочные мыши.
Принтеры и сканеры.
Слот расшире́ния — щелевой разъём, обычно в компьютере, соединённый с системной шиной и предназначенный для установки дополнительных модулей (карт расширения), расширяющих конфигурацию устройства.
20. Запоминающее устройство — носитель информации, предназначенный для записи и хранения данных. В основе работы запоминающего устройства может лежать любой физический эффект, обеспечивающий приведение системы к двум или более устойчивым состояниям. Важнейшими характеристиками ЗУ являются информационная емкость и быстродействие.
Классификация ЗУ
Запоминающие устройства можно классифицировать всевозможными способами, например по назначению, адресации, характеру хранения информации, физическим принципам работы, технологии изготовления и т.д. По назначению ЗУ разделяют на кратковременные и долговременные.
ЗУ предназначенные для кратковременного хранения информации называются оперативным запоминающим устройством. Долговременные, или, как их еще называют, постоянные запоминающие устройства (ПЗУ или ROM), предназначены для длительного хранения информации. Информация, записанная в таком ЗУ при отключении питания, сохраняется достаточно длительное время
21. УСТРОЙСТВА ВВОДА ДАННЫХ
Клавиатура, компьютерная мышь