Курс лекции по Информатике (стр. 6 из 11)
Информационные структуры.
Вcя информация, с которойимеют дело современные ЭВМ, представлена в структурированном виде. В ней можно выделить элементы данных - слова, записи, байты, которые связаны между собой посредством структурных отношений. При разработке сложных программных комплексов, имеющих жесткие требования к занимаемому объему памяти и быстродействию, одной из важнейших задач является задача выбора структуры и форматов баз данных программ. Для этого необходимо, с одной стороны, хорошо понимать структурные отношения, существующие между обрабатываемыми данными, а с другой стороны, свободно владеть известными методами машинного представления информационных структур.
При выборе конкретной информационной структуры обычно исходят из обеспечения удобства выполнения различных операций с элементами структур. Однако за это приходится расплачиваться дополнительным объемом памяти, требуемым для хранения информации о структурных связях. Поэтому наряду со структурой мы будем рассматривать основные операции, которые выполняются с элементами структуры.
Будем также различать логическую и физическую организации информационных структур. Логическая организация содержит собственно описание информационной структуры, а физическая - описание машинной формы представления.
Линейные списки. Наиболее простым типом информационных структур являются линейные списки. Линейный список - это множество, состоящее из n³ 0 узлов X(1), X(2), ..., X(n), которое обладает свойствами:
1) если n>0, то узел X(1) является первым;
2) если 1<k<n, то узлу X(k) предшествует узел X(k-1) и за ним следует X(k+1);
3) узел X(n) является последним.
Будем считать, что каждый узел содержит некоторое, одинаковое для всех узлов, число полей.
Операции, которые можно выполнять о линейным списком:
1? получить доступ к k-му узлу списка;
2? включить новый узел непосредственно перед k-м узлом;
3? исключить k-й узел;
4? объединить два (или более) линейных списка в один;
5? разбить линейный список на два (или более) списка;
6? сделать копию линейного списка;
7? определить количество узлов в списке;
8? выполнить сортировку узлов в возрастающем порядке по некоторым полям в узлах;
9? найти в списке узел c заданным значением в некотором поле.
Общего метода представления, эффективного для реализации всех вышеперечисленных операций, не существует. Поэтому в зависимости от класса операций выбирают свой способ представления.
Часто встречаются линейные списки, в которых включение, исключение или доступ к значениям почти всегда производится в первом или последнем узлах. К таким спискам относятся стек, очередь и дек.
Стек - это линейный список, в котором все включения и исключения делаются на одном конце списка (рис. а).
Очередь - это линейный список, в котором все включения производятся на одном конце, а исключения на другом (рис . б).
Дек (deque: doubleendedqueue- очередь с двумя концами) - это линейки список, в котором все включения и исключения делаются на обоих концах списка (рис. в).
Стек называют еще списком типа LIFO("lastinfirstout" - "последним вошел - первым вышел"), а очередь - списком типа FIFO ("firstinfirstout" - "первым вошел - первым вышел"). Стеки имеют большое приложение для синтаксического анализа, поэтому они будут рассматриваться более подробно.
Рис. Линейные списки: а – стек; б – очередь; в – дек.
Простейший способ хранения списка в памяти – размещение элементов в последовательных ячейках один за другим. Такой способ называется последовательным распределением. Если LOC(Y(j)) - адрес j-го элемента описка, то при последовательном распределении: LOC(Y(j)) = Lo+c×j, где Lo - адрес начала описка, c - длина узла. Последовательное распределение очень удобно при работе со стеком.
Более гибкой по сравнению с последовательным распределением является схема, в которой каждый узел содержит связь со следующим узлом списка. Такое распределение называется связанным. FIRST – указатель на первый узел списка.
Рис. Связанное распределение
Очевидно, что связанное распределение требует больше памяти по сравнению с последовательным. Однако облегчается выполнение многих операций, например, для включения элемента необходимо лишь изменить две связи (рис.), в то время как включение в линейный список с последовательным распределением требует передвижения в памяти элементов списка.
Рис. Включение элемента 1* в связное распределение (X – означает пустую связь).
Лекция 9
Человеко-машинный интерфейс
Персональный компьютер представляет собой набор ресурсов, которые можно разделить на две группы:
· аппаратное обеспечение
· программное обеспечение
К аппаратному обеспечению относится материальная часть ПК, например, процессор, видеоадаптер, сетевая карта, клавиатура и т.д. Эту часть ресурсов компьютера можно, грубо говоря, потрогать руками. Посредством ее осуществляется ряд достаточно сложных алгоритмов преобразования электрических импульсов и электромагнитных полей, перемещения механических частей и т.д. Но, насколько бы сложными и универсальными не были данные алгоритмы, они статичны по своей природе, так как не являются основной целью ПК, а являются лишь средством, хотя и немаловажным, на котором основывается вторая группа ресурсов – программное обеспечение.
Программное обеспечение – это динамическая часть ресурсов персонального компьютера. К программному обеспечению относятся все программные ресурсы, реализующие алгоритмы использования аппаратного обеспечения.
В программном обеспечении прослеживается четкая иерархия по отношению к аппаратным ресурсам. Различают программы нижнего и высокого уровней.
Основной программой низкого уровня является базовая система ввода/вывода (BIOS), посредством которой осуществляется загрузка программного обеспечения более высокого уровня. Вообще говоря, к программам нижнего уровня относится любая программа, напрямую использующая аппаратное обеспечение.
Программное обеспечение высокого уровня в своей деятельности основывается на программах нижнего уровня. Таким образом, персональный компьютер представляет собой обширную иерархию программного обеспечения плавно переходящую в сложную техническую систему аппаратного обеспечения.
Со времени появления первых ПК программное обеспечение претерпело множество принципиальных изменений и на сегодняшний день представляет собой самостоятельный информационный ресурс, имеющий свою значимость и цену.
Выбор операционной системы (ОС) является важным этапом, оказывающим влияние на эффективность работы всех компонентов программного обеспечения. В настоящее время известно несколько операционных систем, отражающих как развитие технических средств, так и стремление разработчиков улучшить функциональные и эксплуатационные характеристики, повысить степень комфортности ОС по отношению к пользователю. Более поздние версии одной и той же операционной системы иногда представляют пользователю принципиально различные возможности. По мере развития операционных систем для ПК определились их основные функции: автоматический запуск системы с первоначальным самотестированием аппаратных и программных средств; обеспечение диалога с пользователем в максимально доступной форме; обеспечение эффективного управления вычислительными ресурсами.
В состав любой современной ОС для ПК входят элементы, которые обеспечивают управление процессом выполнения операций, диспетчеризацию очередей, планирование и обработку прерываний, уровни приоритетов; организацию разделов памяти, сегментирование, динамическое и оверлейное размещение модулей, планирование перекачки памяти и т.д.; управление внешними устройствами, обработку запросов ввода-вывода, выделение памяти, буферизацию, блокирование данных; управление вычислительными процессами, их синхронизацию, связывание и взаимное исключение; управление данными, включая совместное использование наборов данных, их защиту, различные методы доступа, ведение журналов.
Перечисленные функции реализуются системными программами, составляющими ядро операционной системы. Окружением ядра операционной системы являются утилиты, редакторы, компиляторы и другие программные средства, составляющие обслуживающую часть ОС. Ядро ОС обеспечивает базовые функции для окружающего программного обеспечения и допускает расширение обслуживающей части ОС, например, поддержку СУБД, графических интерфейсов, средств сетевой обработки и т.д. Ядро операционной системы постоянно находится в оперативной памяти. Остальное программное обеспечение располагается на внешних носителях.
Операционная система MS-DOS
Операционная система MS-DOS корпорации Microsoft была разработана специально для IBM PC и выпускается с 1981 года. Ее характеризует предельная простота и минимальные требования к аппаратным ресурсам ПК: даже последние версии 6.х системы нормально функционируют, если компьютер оснащен оперативной памятью больше 128 Кб, монохромным текстовым дисплеем и любым процессором Intel 80x86.
Операционная система MS-DOS состоит из следующих компонентов: базовая система ввода-вывода (BIOS); блок начальной загрузки (Boot Record); модуль расширения базовой системы ввода-вывода (IO.SYS); модуль обработки прерываний (MSDOS.SYS); командный процессор (COMMAND.COM); утилиты (внешние команды).