Скорость переработки и передачи данных

Темы

1. Основные процессы преобразования информации. История и направление развития ИС. Метеорология (1. ветер и восход; 2. градусники, барометры… 3. программами прогнозирование), кардиология (1. пульс; 2. кардиограф; 3. томограф, УЗИ), температура тела (1. рука – жар; 2. термометр; 4. томограф).

2. Классификация ИС.

3. База данных. Файловая организация данных. Табличная организация базы данных.

4. Модель процесса переработки графической информации на примере программы PAINT.

• Работа с файлами (создать, сохранить, формат рисунка (способы кодировки графических образов: точечная – BMP, площадями, в виде дерева, примитивы – овал, точка, линия, прямоугольник…), печать, свойства графического образа – BMP, JPG (рисунки) , GIF (чертежи));
• Палитра цвета фона и кисти. Выбор не стандартного цвета с помощью кода RGB;
• Графические примитивы (линия, кривая, прямоугольник, овал, заливка, напыление). Установка параметров графических примитивов:
• Вырезка и копирование.
• Работа с образом. Масштабирование. Оформление рабочего места.

5. Элементы матлогики. Формулы. Эквивалентные преобразования. Таблица истинности. Теоретико-множественное представление. Контактные схемы.

6. Скорость передачи данных.

7. Транспортная сеть. Кратчайший путь. Определение максимального потока.

8. Задача определения точки минимально удаленной от остальных.

9. Определение минимального покрытия.

10. Структурный подход. Представление информационной системы в виде автомата. Определение автомата. Классификация (преобразующий автомат – автомат с выходом, распознающий автомат – автомат без выхода. Моделирование автомата. Минимизация автомата.

11. Информационно-обучающая система. Структура системы. Клиент серверная система. Язык HTML. Структура системы – тестирующей системы.

База данных

Дан фрагмент программы на языке Delphi с файловым представлением базы данных абитуриентов. Эту базу данных можно представить в виде 3-х таблиц:

1. таблица фамилий имен и отчеств с выбранной специальностью,

2. таблица адресов,

3. таблица оценок.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

BD:file of

record

Fio:record family,name,surname:string[25] end;

adress:record index:integer; adres:string end;

EGE:array[1..4] of integer;

end;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

// форма по заполнению данных об абитуриентах

var i:integer;

begin

for i:=1 to 32 do

stringgrid1.Cells[0,i]:=inttostr(i);

stringgrid1.Cells[1,0]:='Фамилия';

stringgrid1.Cells[2,0]:='имя';

stringgrid1.Cells[3,0]:='отчество';

stringgrid1.Cells[4,0]:='специальность';

stringgrid1.Cells[5,0]:='адрес';

stringgrid1.Cells[6,0]:='ЕГЭ мат';

stringgrid1.Cells[7,0]:='ЕГЭ физ';

stringgrid1.Cells[8,0]:='ЕГЭ инф';

stringgrid1.Cells[9,0]:='ЕГЭ рус';

end;

end.

Таблица фамилий имен и отчеств Таблица выбор специальности

ID	фамилия	имя	отчество		ID	Код спец.
	Иванов	Иван	Иванович
	Алиев	Ирек	Азатович
	Галиева	Алсу	Нуровна

Таблица адресов Таблица оценок ЕГЭ

ID	адрес		ID	математика	физика	информатика	русский
	…
	…

Кодировка цвета

Кодировка рисунка BMP:

X*Y*T – размер кода, где X-ширина, Y-высота, T-глубина или возможность цветовой гаммы RGB. Обычно 3 байта – 60 000 000 цветов.

Площадями

1) Если черный квадрат Малевича, то дается только один цвет на весь рисунок.

2) Изображение символа «Y»

Кодировка идет с левого верхнего угла по часовой стрелке

Кодировка примитивами

Тип примитива

атрибуты

1 – Точка

Х-координата

У-координат

цвет

радиус

2 – Линия

Х1

У1

Х2

У2

Цвет

Тощина

Тип линии

3 – Эллипс

Х

У

R1

R2

Цвет окр

Толщина окр.

Тип линии

4 – Овал

Х

У

R1

R2

Цвет

Цвет окр

Толщина окр.

Тип линии

5 – Прямоугольник

Х1

У1

Х2

У2

Цвет

Толщина пр.

Тип линии

6 – Окрашенный прямоугольник

Х1

У1

Х2

У2

Цвет

Цвет площади

Толщина пр.

Тип линии

И т.д.

ff0000

Скорость переработки и передачи данных

Скорость переработки информации зависит от метода решения, структуры данных и скорости компьютера.

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

Возможна локальная оптимизация, которая использует специфику конкретных операций.

Рассмотрим следующие случаи

1) a:=b+c ó 2) a=b+a ó 3) a+=b ó 4) a+=1 5) ó a++

При реализации 1-го случая необходимо значения b и c достать из памяти, выполнить операцию и разместить в а. Что потребует выполнение 4-х действий. Во втором случае нужно выполнить те же 4 действия, но при выполнении этого оператора на ассемблере есть команды, когда один из операндов может находиться в памяти и это соответствует случаю 3. соответственно по числу операторов ассемблера их будет 3. В 4-м случае переменная представлена в виде константы 1, что тоже может быть реализован командой автоувеличения в ассемблере, которая работает быстрее чем сложение двух чисел. Поэтому последний вариант реализуется в 2 раза быстрее, чем 1-й. Так при записи программы можно подсказать транслятору, какой эффективный вариант решения этого фрагмента нужно записать.

Другой пример.

а:=2*a ó a:=a+a ó a+=a

из приведенной таблицы видно, что второй и третий вариант выполняют эту задачу быстрей.

Если надо вычислить а¹²⁸, можно написать следующий фрагмент программы

Фрагмент программы	b:=1; for i:=1 to 128 do b:=b*a	b:=a; for i:=2 to 128 do b:=b*a	for i:=1 to 7 do a:=a*a	for (i=1;i<8;i++) {a*=a}
Потребность времени	100%	127/128=99%	7/128=5,5%	0.9*7/128=5%

Элементы теории автоматов

Опеределение

Автомат – это кортеж <S,X,Y,d,λ,s₀,F>, где

S – множество состояний;

X – алфавит входного языка;

Y – алфавит выходного языка;

d – функция перехода из состояния в состояние, зависящего от текущего состояния и входного символа;

λ – функция вывода, зависящего от текущего состояния и входного символа, для автомата с выходом;

s₀ – начальное состояние автомата;

F – финальное множество состояний для распознающего автомата.

Минимизация автомата

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

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

Автоматы упрощаются так:

1. Удаление недостижимых состояний

2. Удаление непродуктивных состояний

3. Выявление эквивалентных состояний

Определение. Состояние qÎQ называется недостижимым, если под воздействием любого слова xÎS* автомат не переходит в состояние q

Рис. 1: q₄ - недостижимо

Определение. Состояние называется непродуктивным состояние qÎQ, для которого не существует xÎS* (q₀,x) вывод (q_n, x') нет вывода до финального состояния.

Рис. 2: q₄ – непродуктивное состояние

Определение. Слово x различает состояния q₁, q₂ из Q, если одно из этих состояний финальное, а другое не является финальным.

Определение. Состояние q₁,q₂ из Q называются различными (неэквивалентны), если существует слово (цепочка) x, которое различает эти 2 состояния (из одного состояния достижимо заключительное состояние, а из другого — нет).