Принципы организации баз данных 5 страница

Rem Вычисление количества сообщенийclsInput “Введите длину сообщения в битах”; nx=exp(n*log(2))print “Количество сообщений равно ”; int(x)end

 

Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).

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

Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.

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

Пример. Определим функцию фрагмента алгоритма вида на тесте n=2

dim x(n)x(1)=4: x(2)=9 k=1s=x(1)for i:=1 to n if s<x(i) then s=x(i) k=i endifnext i…

Если выписать трассировочную таблицу вида

i	S	x(i)	k	s<x(i)	i<=n
				Нет	Да
				Да	Да
	—	—	—	—	Нет

то функция алгоритма становится более понятной – эта функция состоит в нахождении индекса максимального элемента ряда.

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

Основные формы использования алгоритмов – автономное, библиотечное, пакетное.

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

 

Рис. 9.1. Структура алгоритмического обеспечения

 

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

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

10 Лекция: Исполнители алгоритмов - человек и автомат

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

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

Наиболее используемые типы исполнителя алгоритмов – человек или автомат (компьютер).

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

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

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

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

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

В непосредственную (сенсорную) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память (память сознания). Далее она пересылается в долговременную память с привлечением подсознания ("укладывается на полочки" с соответствующими названиями "Формы поведения", "Объекты и образы", "Правила и процедуры обнаружения и идентификации объектов", "Правила выборки и организации информации", "Жизненный опыт", "Бытовые навыки и умения", "Профессиональные навыки и умения" и др.).

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

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

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

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

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

- X = {1, 3, Г, Ø} – входное множество,

- Y = { В, С, О } – выходное множество,

- S = { s ₀, s ₁, s ₂, s ₃} – множество состояний,

- 1 – входной сигнал "опустить 1 коп.",

- 3 – входной сигнал "опустить 3 коп.",

- Г – входной сигнал "опустить гнутую монету",

- Ø– входной сигнал "монета не опущена",

- В – выходной сигнал "выдача воды газированной без сиропа",

- С – выходной сигнал "выдача газированной воды с сиропом",

- О – выходной сигнал "отказ выдать воду",

- s ₀ – первое состояние – "начальное состояние",

- s ₁ – второе состояние – "обработка 1 коп.",

- s ₂ – третье состояние – "обработка 3 коп.",

- s ₃ – четвертое состояние – "состояние неисправности".

Функционирование конечного автомата происходит в дискретные моменты времени t = 0, 1, 2,..., T. Изменение состояния автомата , то есть переход из текущего состояния в новое состояние , может быть осуществлено либо до выдачи выходного сигнала , либо – после выдачи этого сигнала.

 

Рис. 1. Граф автомата для продажи газированной воды

 

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

Законы функционирования автомата Мили:

.

Законы функционирования автомата Мура:

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

Пример. Пример конкретного автомата Мура приведен выше (автомат для газировки). Приведем абстрактный пример автомата Мили: Х = {х₁, х₂}, У = {у₁, у₂, у₃}, S = {s₀, s₁, s₂, s₃, s₄, s₅}, функции перехода и выхода f зададим таблицами соответствий:

 

– функция перехода
s(t – 1)	S1	s1	s2	s3	s3	s4	s5
x(t)	Х1	х2	x1	x2	x1	x2	х2	x1
s(t)	S2	s3	s4	s2	s4	s3	s5	s5
f – функция выхода
s(t – 1)	S1	s1	s2	s2	s3	s3	s4	s5
x(t)	X1	x2	x1	x2	x1	х2	х2	х1
y(t)	У2	у3	y1	y1	y3	у2	у3	y2

 

Компьютер можно рассматривать как совокупность взаимодействующих конечных автоматов. Рассмотрим такую структуру подробнее.

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

Пример. Запишем числа 13₁₀, в формате целых чисел в восьмиразрядную ячейку памяти запишется в виде (старший бит будет содержать бит знака числа, например, 1 – если число отрицательно и 0 – если число положительно). Учитывая, что 13₁₀ = 1101₂, получаем представление вида:

 

 

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

Пример. Если десятичное число равно 5,25, то есть в двоичной форме – 101,01, то оно записывается в нормализованной форме: 0,10101 с порядком, равным в двоичном виде 101.

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

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

Пример. Для компьютера с памятью 512 мегабайт основной памяти может быть характерна регистровая память в 64 мегабайта.

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

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

Джон фон Нейман предложил ряд принципов, которые легли в основу фон Неймановской или классической архитектуры компьютера:

1. память состоит из однородных ячеек памяти с адресами;

2. программа состоит из последовательных команд;

3. хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде;

4. команды выполняются последовательно, данные извлекаются в соответствии с командами;

5. процессор – один и имеет централизованное управление и доступ к памяти.

Структура ЭВМ фон Неймановской архитектуры приведена на рис. 2.

Рис. 2. Структура ЭВМ фон Неймановской архитектуры

 

Арифметико-логическое устройство (АЛУ) выполняет арифметические, логические операции.

Пример. Команды АЛУ – просты: "сравнить два числа", "переслать число", "взять дизъюнкцию" и др.

Устройство управления (УУ) организует работу ЭВМ, в частности это устройство извлекает очередную команду из памяти, расшифровывает команду, выбирает из памяти операнды к расшифрованной команде и передает их АЛУ для выполнения расшифрованной операции, а после выполнения пересылает результат для хранения в память. При этом УУ реагирует на нормальный или аварийный ход выполнения операции.

Совокупность АЛУ и УУ, информационно-управляющих линий называется процессором компьютера (его структура приведена на рис. 3; жирная линия – информационное взаимодействие, другая – управляющее).

Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода.

Пример. Устройствами ввода являются, например, клавиатура, мышь. Устройствами вывода — дисплей, принтер, плоттер.

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

 

Рис. 3. Структура процессора

 

Ядро персонального компьютера – системная (материнская плата), на которой размещаются: микропроцессор, микропроцессорная память, интерфейсная система микропроцессора для сопряжения и связи с другими устройствами, генератор тактовых импульсов, контроллеры устройств (схем), интегрированных в материнскую плату, микросхемы ОЗУ и ПЗУ и др.

Другими важными устройствами персонального компьютера являются:

1. дисковод гибких магнитных дисков; дисковод жестких магнитных дисков;

2. CD(DVD)-ROM (устройство только для чтения CD и DVD компакт-дисков) или CD(DVD)-RW (чтение и перезапись);

3. монитор (дисплей);

4. видеокарта (видеоадаптер) для обеспечения связи системного блока и монитора;

5. клавиатура;

6. принтер;

7. сканер;

8. плоттер (графопостроитель);

9. дигитайзер (кодирующий планшет);

10. манипулятор-мышь или манимулятор-трекбол;

11. звуковая карта (адаптер);

12. звуковые колонки;

13. модем и другие устройства.

 

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

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

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

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

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

 

При работе на компьютере необходимо следовать определенным и простым санитарно-гигиеническим правилам, так как компьютер имеет вредно влияющие на здоровье человека факторы: излучения (инфракрасное, рентгеновское, электромагнитное); вибрация и шум; электростатические поля; ультразвук строчной частоты монитора и др.

Необходимо соблюдать простые санитарно-гигиенические и эргономические правила работы на компьютере, в компьютерном зале:

- работа с компьютером не более 4-х часов подряд с 10-минутными перерывами после каждого часа интенсивной работы или после 2-х часов менее интенсивной работы;

- расстояние от глаз до поверхности экрана – не менее 0,6 м;

- перемещаемость клавиатуры относительно экрана в пределах 0,5-1,0 м;

- преимущественно желтый, зеленый, серый или светло-голубой фон дисплея;

- температура воздуха в помещении – 15-25 градусов по Цельсию;

- относительная влажность помещения – 45-75%;

- наличие свободной площади рабочего стола не менее 0,3x1,0 м;

- размер экрана по диагонали – не меньше 17 дюймов;

- разрешение экрана – не менее 800x600;

- частота обновления кадра – не менее 70 Гц;

- размер зерна экрана (расстояние между точками на экране) – не более 0,26;

- частота кадров (мерцание экрана) – не менее 75 Гц;

- стандарты безопасности, например MPR -II.

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

11 Лекция: Программное и техническое обеспечение

Рассматриваются основные понятия о вычислительной системе – совокупности программного и технического обеспечения, их структура.

Любой компьютер состоит из технического обеспечения (hardware) и функционирует, решает задачи с помощью программного обеспечения (software).

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

Приведем эту структуру.

1. Базовое программное обеспечение (ПО).

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

1.1.1. Операционные системы (ОС) – программы ОС (отладчики, загрузчики и т.д.).

1.1.2. Программы обеспечения связи с устройствами (драйверы), и их тестирования.

1.2. Инструментальное ПО – программы для массовой разработки других программ.

1.2.1. Трансляторы с языков программирования.

1.2.2. Интерфейсные системы – программы обеспечения дружественного интерфейса.

1.2.3. Проблемно-ориентированные инструментальные системы (САПР, АСУ, АРМ и др.).

2. Прикладное ПО – программы обеспечения решения прикладных задач пользователя.

2.1. Автономные программы (программы, не связываемые с другими из прикладного ПО).

2.2. Библиотеки программ (программы, организованные по принципу библиотек книг).

2.3. Пакеты прикладных программ, ППП (проблемно-ориентированные прикладные системы).

2.4. Интегрированные пакеты прикладных программ – системы, состоящие из связываемых ППП.

3. Специальное (уникальное) ПО - программы, используемые для решения уникальных проблем.

Структура технического обеспечения приведена ниже и также является условной и классифицирует техническое обеспечение только по назначению.

Приведем эту структуру (некоторые блоки могут интегрироваться в другие, например, видеопамять – в блок микропроцессора).

1. Базовое техническое обеспечение (ТО).

1.1. Микропроцессор.

1.2. Постоянная ("вшитая") память – ПЗУ.

1.3. Оперативная ("адресуемая пользователем") память – ОЗУ.

1.4. Регистровая память (аппаратная кэш-память).

1.5. Видеопамять (часто интегрируется в блоке микропроцессора).

1.6. Блок питания (энергетический блок).

2. Периферийное ТО (программы обеспечения решения прикладных задач пользователя).

2.1. Устройства ввода (клавиатура, мышь, трекбол, сканер, дигитайзер, джойстик и др.).

2.2. Устройства вывода (дисплей, принтер, плоттер и др.).

2.3. Устройства (накопители) внешней памяти (дискета, СD, оптический накопитель и др.).

2.4. Устройства согласования других устройств и сетевые (модем и др.).

3. Специализированное ТО (устройства, используемые для решения уникальных проблем).

Охарактеризуем программное обеспечение (ПО) компьютера (компьютерной системы, сети).

Наиболее сложный и важный элемент ПО – это ОС.

ОС – совокупность программ, которые обеспечивают нормальную работу всех основных устройств компьютера, всех программ и данных, используемых на компьютере при решении задач.

ОС состоит из двух основных частей – управляющие программы и обрабатывающие программы и включает в себя следующие основные программы:

1. диспетчер – управляющая программа для координации работы различных устройств ЭВМ, планирования использования и распределения машинного времени, аппаратуры между программами, пересылка программ из ВЗУ в ОЗУ и наоборот, распределение данных в памяти, ввод программ в выделенные участки ОЗУ, управление выполнением задачи, принятие решений в аварийных ситуациях, обнаружение и классификация ошибок и др.;

2. супервизор – управляющая программа для контроля координации используемых ресурсов и последовательности действий процессора;

3. отладчик – обрабатывающая программа для отладки программы;

4. редактор связей – программа для формирования непосредственно выполняемой в памяти программы на машинном языке.

Основными функциями ОС являются:

1. выполнение очередного по приоритету задания и отслеживание очередности;

2. управление распределением данных в памяти и извлечением их из памяти;

3. управление устройствами, их актуализация по мере необходимости (по требованиям программ);

4. восстановление работоспособности при сбоях;

5. управление работой арифметико-логического командного устройства процессора.

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

Файл – именованный структурированный набор однотипных последовательностей данных, обычно хранимый на внешнем носителе и копируемый для работы с ним по мере надобности в ОЗУ. Файловая система должна обеспечивать выполнение основных операций над файлами: создание, модификация (в том числе расширение и сжатие), уничтожение, чтение (запись), перемещение файла. Файловая система ведет справочник файлов, где регистрируются файлы активные, используемые в данном задании в данный момент.

ОС бывают различного типа:

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

- многозадачные мультипрограммной обработки, загружающие в ОЗУ последовательность (пакет) независимых задач, а затем решающие эти задачи по очереди, выделяя каждой из них ресурсы компьютера (память, процессор, внешнее устройство) на некоторый промежуток времени, например, на 0,1 с (за такой небольшой промежуток времени компьютер с быстродействием 1 млн операций в секунду и очередностью в 10 программ, в каждой программе произведет около 100000 операций);

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

Пример. ОС Linux – многопользовательская сетевая ОС с оконным графическим интерфейсом для персональных компьютеров и рабочих станций. Это открытая система (Open Code System) – исходные тексты распространяются с лицензией на свободное копирование, модификацию и установку для неограниченного числа пользователей. Разработана система Линусом Торвалдсом (Linus Torvalds) из университета Хельсинки и модифицируется всеми пользователями и др. Основные возможности ОС Linux:

- возможность бесплатного и легального получения и использования исходных кодов ОС;

- высокое быстродействие, надежность, устойчивость, защищенность от вирусов;

- эффективная поддержка многопользовательского режима, многозадачности, интерактивности;

- интегрируемость компьютера с ОС Linux в различные сети и Интернет;

- возможность выполнения загрузочных файлов ОС Unix, DOS и Windows;

- богатый набор инструментальных средств для разработки прикладных программ;

- богатая, полная и открытая документация и исходные тексты всех компонент;

- использование компьютера на полную мощность, "превращение" его в аналог сервера;

- защита памяти процесса, экономная загрузка и динамически изменяемая память;

- поддержка национальных алфавитов и соглашений, расширяемость и др.

- Программное базовое обеспечение системы Linux:

- системы программирования (C++, Pascal, Perl, ADA, Modula, Prolog, Java, Python и другие);

- динамические библиотеки программ;

- сетевое обеспечение на базе протоколов TCP/IP;

- поддержка электронной мультимедийной почты;

- поддержка основных типов СУБД;

- графическая сетевая оконная система;

- издательская система T_EX, текстовый процессор L_yX, основанный на T_EX;

- многие другие сотни программ и пакетов.

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