Файл: Технологии программирования (Сбор и передача данных).pdf

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

Цели компьютерного моделирования могут быть различными, но чаще всего это получение данных, которые могут быть использованы для подготовки и принятия решений экономического, социального, организационного или технического характера. Положено начало использованию компьютера даже при концептуальном моделировании, где он используется, например, при построении систем искусственного интеллекта. Таким образом, мы видим, что понятие «компьютерное моделирование» значительно шире традиционного понятия «моделирование на ЭВМ» и нуждается в уточнении, учитывающем сегодняшние реалии. [23]

Начнем с термина «компьютерная модель». В настоящее время под компьютерной моделью чаще всего понимают:

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

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

Компьютерное моделирование — метод решения задачи анализа или синтеза сложной системы на основе использования ее компьютерной модели.

Суть компьютерного моделирования заключена в получении количественных и качественных результатов по имеющейся модели. Качественные выводы, получаемые по результатам анализа, позволяют обнаружить неизвестные ранее свойства сложной системы: ее структуру, динамику развития, устойчивость, целостность и др. Количественные выводы в основном носят характер прогноза некоторых будущих или объяснения прошлых значений переменных, характеризующих систему. [23]

2.2 Работа с данными

Две основные операции по работе с данными это фильтрация и сортировка.

Фильтрация - отсеивание «лишних» данных, в которых нет необходимости для принятия решений; при этом должен уменьшаться уровень «шума», а достоверность и адекватность данных должны возрастать; [15]

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

Сортировка - упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации; [15]

Сортировка бывает внешней (файлы) и внутренней (массивы).

Существует несколько алгоритмов внутренней сортировки данных:

- сортировка обменная (пузырьком) (англ. Bubble sort ) — сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку;

- сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — сложность алгоритма: O(n2);

- сортировка вставками (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда;

- гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2);

- блочная сортировка (Корзинная сортировка, Bucket sort) — сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить";

- сортировка подсчётом (Counting sort) — сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта);

- сортировка слиянием (Merge sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки;

- сортировка с помощью двоичного дерева (англ. Tree sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; [4]

- сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка;

- сортировка Шелла (Shell sort) — сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками;

- сортировка расчёской (Comb sort) — сложность алгоритма: O(nlog n);

- пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка;

- плавная сортировка (Smoothsort) — сложность алгоритма: O(n log n);

- быстрая сортировка (Quicksort) — сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай;

- поразрядная сортировка (Цифровая сортировка) — сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

- Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. [4]

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

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

Несмотря на то, что сортировка слиянием может быть применена для обработки оперативных структур с прямым доступом, все же методы такой сортировки разрабатывались специально для магнитных лент. Поэтому последовательная сортировка обычно называется внешней сортировкой. [7]

2.3 Преобразование данных

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

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

Программное преобразование данных связано с изменением формы представления данных.

Самое распространённое преобразование - это перевод из одной системы счисления в другую. К примеру: число 21 в десятичной системе счисления это 10101 в двоичной системе счисления, 25 в восьмеричной системе счисления и 15 в шестнадцатеричной.

При работе программ часто возникает необходимость преобразовывать данные из одного формата к другому (из символьного в числовой и наоборот). К примеру, если программе необходимо найти в тексте число и произвести с ним вычисление, то возникнет необходимость преобразования данных, так как в символьном и числовом виде это число будет закодировано по разному. Так число 34 в символьном виде кодируется как: 0011001100110100 (тройка и четверка, стоящие рядом) в соответствии с таблицей кодировки ASCII, в числовом виде – 00100010. Как можно заметить изменились не только вид данных, но их размер. Для хранения данного числа достаточно 1 байта, а вот для хранения его как символа нужно уже 2 байта.

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

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

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

2.4 Архивация данных

Архивация данных – организация хранения данных в удобной и легкодоступной форме; служит для снижения экономических затрат по хранению данных и повышает общую надежность информационного процесса в целом; [15]

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

- имя файла;

- дата и время его создания;

- исходный объем файла (т.е. до архивации);

- коэффициент сжатия (в %);

- объем файла в заархивированном виде (т.е. после сжатия).

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

Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 50-70%, меньше сжимаются файлы исполняемых программ и загрузочных модулей – 20-30%. Почти не сжимаются архивные файлы. Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на их степень сжатия. [6]

Существует несколько алгоритмов сжатия.

Алгоритм RLE – один из простейших методов сжатия данных, кодирование с переменной длиной он заключается в поиске последовательностей из одинаковых единиц информации. Каждой такой последовательности сопоставляется сам набор, и число содержащихся в нем одинаковых наборов бит (счетчик). Например, AAA BB 1111 DD EE FF GGGGG – 20 байт на входе. После кодировки: A3 B2 14 D2 E2 F2 G5 – 14 байт на выходе. Коэффициент сжатия составляет 70%. [5]

Достоинства алгоритма RLE в том, что он быстрый и простой в реализации.

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

Алгоритм KWE – в его основу положено кодирование лексических единиц (слов) группами байтов фиксированной длины.

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

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