Лекция 6. Анализ и синтез информационных систем. 4 страница

Тзап - время, необходимое для записи информации (или ее восстановления после чтения) в заданной ячейке.

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

1.Произвольный (непосредственный)

2. Прямой

3. Последовательный

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

Память современных ЭВМ представляет собой сложную иерархическую систему, состоящую из ЗУ, имеющих различные технические характеристики. Число уровней иерархии памяти зависит от характеристик ЭВМ. Разница между памятью с последовательным способом доступа (ПОСД) и произвольным способом доступа (ПРД) может быть рассмотрена с разных позиций: ввода, обработки и вывода информации.

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

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

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

Различают 5 групп методов:

1. Последовательный вывод, то есть равномерный вывод всех информационных единиц массива или его определенной части

2. Последовательный поиск нескольких информационных единиц то есть выбор заранее неизвестного количества информационных единиц путем проверки всех информационных единиц во всем массиве или ограниченной части массива

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

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

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

МЕТОДЫ ПОИСКА

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

2. Последовательный поиск. Массив упорядочен по типу используемого поискового термина. Если данные о размещении записей отсутствуют или же массив хранится в ЗУ с последовательной выборкой, то требуется сопоставление каждой записи К1, К2...Кл, пока не будут найдены нужные записи. Если будет найдена запись, значение сортировочного ключа которой превосходит его значение для термина запроса, извлечение записи не производится и поиск прекращается.

3. Быстрый последовательный поиск. Является улучшенным последовательным поиском. Имеется таблица записей К1, К2,..Кп, снабженных соответственно ключами К1,К2..Кп. Алгоритм предназначен для поиска с данным ключом К. Предполагается, что в конце файла стоит фиктивная запись Кп+1

4. Последовательный поиск в упорядоченной таблице. Имеется таблица записей К. 1, К2,..Кп, причем ключи удовлетворяют неравенству К1<К2<..Кп. Алгоритм предназначается для поиска данного ключа К. В целях удобства и увеличения скорости работы предполагается, что в конце таблицы расположена запись Кп+1, ключ которой Кп+1 =оо >К

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

6. Однородный двоичный поиск. Алгоритм служит для отыскания аргумента К в таблице записей К.1, К2,.,Кп, ключи которых расположены в возрастающем порядке К1<К2<.Кп.

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

Содержание лабораторной работы

Используя цифровой массив ключей, реализовать один из методов поиска в

1. 2. 1. 2.

Содержание отчета

Описать метод, рассматриваемый в заданном варианте. Листинг программы.

Контрольный пример

Используемый метод поиска информации - 1. Зададим массив ключей: 10121415 17 22 26 28 32 41 57 61 65 69 72 76, а также поисковый признак - один из элементов массива {например 41), Затем последовательно осуществляем сравнение ключа массива с поисковым признаком. Как только будет найден нужный элемент в массиве ключей, поиск завершается. Контрольные вопросы.

1.Назовите основные характеристики памяти.

2. Чем определяется быстродействие памяти?

3. Перечислите способы организации доступа к данным, изложите суть каждого из

них.

4. Какие методы поиска записей существуют?

Лабораторная работа №2. Программирование в MatLab

Первое знакомст во с MATLAB

Для запуска MATLAB Вам необходимо найти на рабочем столе ярлык этой программы и запустить его на выполнение, при этом отроется рабочие окно программы. Подсказка «»» показывает готовность системы к выполнению Ваших команд. Набрав простейшие математические выражения в естественной форме записи Вы сразу же получаете результат. Это выражение может быть записано в двух видах: <Выражение> или <Имя переменной>=<Выражение>. Во втором случае результат не только вычисляется но и присваивается указанной переменой. MATLAB не требует от пользователя специальных команд для объявления переменных, они создаются автоматически при первом указании пользователем их имени. В первом случае на самом деле результат выражения присваивается специальной служебной переменной имеющей имя ans, Вы так же можете использовать эту переменную в расчетах. Если Вы не хотите что бы MATLAB выводил результаты промежуточных выражений на экран, то Вам необходимо поставить в конце выражения символ «;».

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

Типы данных MATLAB Массивы

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

□

Локальные и глобальные переменные

Так же как и все структурные языки программирования MATLAB различает глобальные и локальные переменные. Локальные переменные действуют только в модуле где они

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

Глобальные переменные, действуют во всех модулях

Модуль 1 Локальные переменные, действуют только в этом модуле.

Модуль 2 Локальные переменные, действуют только в этом модуле.

Модуль 3

Локальные переменные, действуют только в этом мо душе.

Для указания что переменная является глобальной необходимо указать перед ее именем описание global. Например global А.

Для того чтобы узнать какие переменные есть в Вашем распоряжении Вам необходимо вызвать команду who, по которой будет выдан список всех локальных переменных. Команда who global, выводит список всех глобальных переменных созданных Вами за время этого сеанса работы с MATLAB.

Прост ейшие дейст вия над мат рицами

Присвоение значений матрице

Простейшей операций с матрицей является ее создание. Для создания столбца Вам необходимо указать его имя, знак равенства и в квадратных скобках через запятую или через пробел перечислить значения элементов. Например: А=[1 2 3 4 5]. В случае если Вам необходимо создать строку чисел, то в качестве разделителя выступает символ точка с запятой, например: В=[1; 3; 5; 7]. Для создания квадратной или прямоутольной матрицы Вам понадобится чередовать оба этих способа, например: С=[ 123;456;789].

Создание матриц специального вида

Для генерации векторов пользователю предоставляется следующая команда: <Имя вектора>=<Начальное значение>:<Шаг>:<Конечное значение>. Например: Х=6: 0. 2: 26. В математике часто встречаются матрицы специального вида. Ниже приведен ряд из

них:

Единичная матрица, рис. З.а. В единичной матрице все элементы равны нулю, кроме элементов стоящих на главной диагонали. Для создания единичной матрицы Вам необходимо подать команду <Имя матрицы>=еуе(<Размер>). Матрица является квадратной.

Матрица со всеми единицами, рис. З.б. Эта матрица содержит единицы во всех ячейках. Для создания матрицы Вам необходимо указать <Имя матрицы>=опей(<Кол-во строк>, <Кол-во столбцов>). Например: A=ones(6, 3).

Нулевая матрица, рис. З.в. Эта матрица содержит во всех своих ячейках одни нули. Для создания Вам необходимо выполнить следующую команду: <Имя матрицы>=2егоз(<Кол-во строк>, <Кол-во столбцов>). Например: A=zeros(6, 3).

Случайная матрица. Все значения этой матрицы получаются с генератора случайных чисел. Для создания такой матрицы Вам необходимо дать следующую команду: <Имя матрицы>=гагк1(<Кол-во строк>, <Кол-во столбцов>). Например: A=rand(6, 3).

Доступ к ячейкам матрицы

Для доступа к ячейкам матрицы Вам необходимо указать имя матрицы, номер строки и номер столбца. Нумерация строк и столбцов ведется с единицы. Номера пишутся в круглых скобках. Общий формат записи <Имя массива>(<Номер строки>, <Номер столбца>). Например А{1,2).

Простейшие действия над матрицами

Умножение матрицы на скаляр. В математики для всех матриц определена операция умножения матрицы на скаляр (число). Все значения матрицы в этом случае умножаются на это число.

Сложение, вычитание скаляра из матрицы. Кроме операции умножения матрицы на скаляр для матрицы и скаляра определены операции сложение и вычитания. Действия так же выполняются с каждой ячейкой матрицы отдельно. Пример:

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

Присвоение матрице математического выражения

Организация всех переменных системы MATLAB как матрицы вызывает следующие ограничения применения их в выражениях. На пример: t=l:5

t= 1 2 3 4 5 y=cos(t)

у=1 0.5 -0.4-1 -0.6 0.2

z=y/t z=-0.08

Результат - получается одно число, а ожидали функцию z(t)=cos(t)/t.

Для организации поэлементного деления одного массива на другой, в MATLAB предусмотрена специальная операция - «./» - поэлементное деление. Результат этого выражения будет друтой: z=y./ t

z= 0.5403 -0.2081 -0.3300 -0.1634 0.0567. Графические средст ва предст авления результ ат ов

Вывод одного графика

MATLAB предоставляет следующие функции для работы с графикой: plot(<MaccHB>) - построение графика значений из массива X от номера отсчета. plot(<MaccnB точек по оси Х>,<Массив точек по оси У>) - построение графика значений из массива У от значений из массива X.

При вызове команды создается окно с указанным графиком.

Вывод нескольких графиков

Для вывода нескольких графиков на одном окне Вам необходимо указать их последовательно, например: t=-10:0.1:10; xl=sin(t); x2=cos(t) J t; plot(t,xl,t,x2)

Графический метод решения уравнений

Вывод на экран сразу нескольких графиков предоставляет простейший способ найти приблизительное значение решения.

На данном графике представлены графики функций y=sin(t)/t и (х/5)²+у²=1. Как не трудно заметить данные функции имеют три точки пересечения.

Поиск решения уравнения

Графическим методом можно лишь примерно оценить решение. Для более точного нахождения решения в пакете MatLAB необходимо воспользоваться функцией fsolve(ypaBHeHHe, начальное значение). Позже мы познакомимся как с помощью данной функции решать системы уравнений. В простейшем случае решаемое уравнение можно указать можно указать в одинарных кавычках, например: 'x*x-abs(x)\ Но данная функция имеет три решения, представленных на рис. 1.2.

4 3.5 3 2.5 2 1.5 1

0.5 0

-2 -1 0 1 2 Рис. 1.2. Графики функций

Решение, которое найдет в этом случае функция fsoive будет определяться начальным значением откуда она начнет итерационную процедуру поиска решения. Например: fsolve('x*x-abs(x)\-2), ans = -1.0000;

fsolve('x*x-abs{xy,0.6), ans = 1.0000;

fsolve('x*x-abs{xy,0.4), ans = 7.9062e-008.

Функция fsoive продолжает итерационную процедуру до тех пор пока она не найдет решение с заданной точностью. По этому в нашем примере мы и получили 7.9062е-008 а не 0.

В случае более сложных функций их удобнее представить в виде М файла. Тогда в качестве первого параметра функции fsoive подставляется в одинарных кавычках имя этого файла.

Трехмерные графики

Для построения трехмерных графиков во первых понадобится создать сетку координат на плоскости. Выполняет это функция [X,Y]=meshgrid(x,y), где х и у - одномерные массивы, а X и Y - полученные в результате двухмерные массивы. Если массивы х и у одинаковые, то достаточно указать [X,Y]=meshgrid(x). Например: [X,Y]=meshgrid([-2:0.1:2]).

После этого описывается сама функция, например Z=X.*exp(-X.^A2-Y.^A2). Напоминаю что операции «.^Л» и «.*» означают поэлементные а не матричные действия.

После этого подается команда на вывод трехмерного графика: plot3(X,Y,Z). Результат исполнения для данного примера приведен на рис. 1.3.

Элемент ы программирования в пакет е MATLAB

Программирование в системе MatLAB очень близко к обычному программированию. Программа создается в любом текстовом редакторе. Файл должен иметь расширение *.М. Для того чтобы Вы могли вызвать его из любого места он должен размещаться в одном из каталогов перечисленных в конфигурационном файле MATLABRC.M. К строкам matiabpath =[...'путь',...,'путь']; необходимо по аналогии добавить путь до своего рабочего каталога.

Для вызова М файла необходимо набрать его имя в командной строке MatLAB, и если необходимо его аргументы.

Важным элементом облегчающим программирование являются комментарии. Строка комментария начинается в MatLAB символом '% '.

Проверка условия

Оператор проверки условия позволяет организовать разветвление исполнения программы. Внешний вид оператора представлен на рис. 1.4.

Рис. 1.4. Блок-схема условного оператора: редуцированная и полная формы

Формат записи оператора, редуцированная форма: if условие

операторы end

полная форма: if условие

операторы else

операторы end

Обращаю Ваше внимание что в отличие от современных языков программирования не используются такое понятие как составной оператор. Блок условного оператора обязательно заканчивается служебным словом end. Пример: d=b^A2-4*a*c; ifd<0

error(' коней нет') else

xl=(-b+sqrt(d))/(2*a) x2=(-b-sqrt(d))/(2*a) end

Использованная в данном фрагменте программы функция error выводит на экран сообщение об ошибке.

Ввод с клавиатуры

x=input('cTpoKa подсказки') x=input('cTpoKa подсказки', 's')

Функция input выводит на экран строку подсказки и ждет ввода переменной. Функция x=input('cTpoKa подсказки', 's') возвращает введенную пользователем строку. При вводе переменных допустимо пользоваться стандартными функциями.

Задание на практ ику

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

Дополнительное условие - в каждом операторе If можно работать только с одной геометрической фигурой.

Блок-схема программа и листинг на языке Си приведен на рис. 1.5.

^include < stdio.h> void main(void)

С

float x, у;

prmtf("\nвведите:"); scanf("%r',<ftx); scanf("%f",<fty); iffy^x+i))

if(x*x+y*y<r^Ar)

jf((xl<x)&&(x<x2) && (y2<y)&&(y<yl))

printf("\n №4");

else

г if(y>yl)

printffta №7");

L else

printf("Vn №8");

- else

if((xl<x)&&(x<x2)&& (y2< у) &&(y<y 1)) prmtf("\n№5");

else

printf("ln№6");

else

Не нашли, что искали? Воспользуйтесь поиском: