- •Введение
- •1.Понятие экономической информационной системы (эис)
- •1.1. Понятие системы
- •1.2. Понятие эис. Назначение эис
- •1.3.Классификация эис
- •1.4. Основные принципы и методы построения эис
- •1.4.1. Принципы построения и функционирования эис.
- •1.4.2.Структурный и объектно-ориентированный подходы к проектированию.
- •1.4.3.Понятие жц эис.
- •2.Теоретические основы работы с информацией
- •2.1. Понятие информации
- •2.2. Измерение количества информации
- •Задания на дом
- •2.3.Кодирование информации
- •2.3.1.Оптимальное основание кода
- •2.3.2.Запись натурального числа в двоичной системе
- •2.3.3.Код Грэя
- •2.3.4.Оптимальное кодирование
- •2.3.5.Помехозащищенное кодирование
- •2.4.Методы организации данных в памяти эвм
- •2.4.1.Типы данных, структуры данных и абстрактные типы данных
- •2.4.2.Время выполнения программ
- •2.4.3.Списки
- •2.4.4.Реализация списков
- •Реализация списков посредством массивов
- •Реализация списков с помощью указателей
- •Реализация списков с помощью курсоров
- •2.4.5.Стеки
- •2.4.6.Реализация стеков
- •2.4.7.Очереди
- •2.4.8.Реализация очередей
- •2.4.9.Графы и деревья
- •2.4.10.Некоторые сд для хранения графов и деревьев
- •3.Особенности работы с экономической информацией
- •3.1.Классификация и кодирование экономической информации.
- •3.2.Единая система классификации и кодирования
- •3.3.Штриховое кодирование
- •Алгоритм расчета контрольного разряда ean
- •4.Модели данных
- •4.1.Атрибуты, составные единицы информации, показатели, документы
- •4.2.Операции над сеи
- •4.3.Реляционная модель данных
- •4.3.1. Отношения, как основа реляционной модели данных
- •4.3.2. Операции над отношениями
- •Операции объединения, пересечения и разности отношений
- •Операция декартова произведения отношений
- •Отношение «список программистов» и результат выполнения проекции
- •Операция натурального соединения отношений
- •4.3.3. Нормализация отношений
- •4.3.4. Функциональные зависимости
- •4.3.5. Нормальные формы
- •Результат первого шага приведения к 2нф отношения преподаватель_предмет (отношение преподаватель в 2нф)
- •Результат первого и второго шагов приведения к 2нф отношения преподаватель_предмет (все отношения в 2нф)
- •4.3.8. Пример проектирования реляционной бд
- •5.Модели знаний
- •5.1. Классификация знаний
- •5.2. Продукционная модель представления знаний
- •5.3.Представление знаний в виде семантической сети
- •5.4. Фреймовая модель представления знаний
- •5.5. Логическая (предикатная) модель представления знаний
- •6.Моделирование предметных областей в экономике
- •6.1.Понятие модели предметной области
- •6.2.Структурная модель предметной области
- •6.2.1.Функциональная методология idef0
- •6.2.2. Функциональная методика потоков данных
- •6.3.Объектная модель предметной области
- •6.4. Сравнение методик моделирования предметной области
- •7.Алгоритмы, наиболее часто использующиеся при обработке информации в эис
- •7.1.Алгоритмы поиска
- •7.1.1.Поиск элемента в неупорядоченном массиве
- •7.1.2.Поиск элемента в упорядоченном массиве.
- •7.1.3.Фонетический поиск
- •7.2.Алгоритмы сортировки
- •7.2.1.Сортировка методом пузырька.
- •7.2.2.Сортировка вставками
- •7.2.3.Сортировка выбором
- •7.2.4.Пирамидальная сортировка
- •7.2.5.Быстрая сортировка.
- •7.2.6.Сортировка слиянием
- •7.3.Поиск на графах
- •7.3.1.Поиск в глубину
- •7.3.2.Поиск в ширину
- •7.4.Топологическая сортировка графа
- •7.5.Сетевое планирование
- •7.5.1.Алгоритм расчета наиболее ранних сроков наступления событий
- •7.5.2.Алгоритм расчета наиболее поздних сроков наступления событий
- •7.5.3.Алгоритм расчета резервов времени.
- •Литература Рекомендуемая основная литература
- •Рекомендуемая дополнительная литература
- •Приложение 1.Форматы штрих-кодов
- •Приложение 2. Коды некоторых стран
7.1.3.Фонетический поиск
Под фонетическим поиском понимается поиск по нечеткому значению ключа, если в качестве ключа используется фамилия, так как она воспринимается на слух. Наибольшее распространение при организации фонетического поиска получил метод "Soundex" [4]. Метод создает для фамилии ключ, причём похожим фамилиям или неверным написаньям одной фамилии будет соответствовать один ключ. Поэтому, если оператор городской справки, кассир в банке, авиадиспетчер или кто-либо другой наберёт вашу фамилию неверно, доступ к вашей записи в базе данных все равно будет получен, так как поиск ведётся по ключам.
Первоначально метод "Soundex" развит Маргарет К. Оуделли и Робертом К. Расселом [см.U.S.Patents 1261167 (1918), 1435663 (1922)]. Метод "Soundex" заключеется в следующем:
1.Оставить первую букву фамилии; все буквы а,е,h,i,о,u,w,у, стоящие на других местах, вычеркнуть.
2.Оставшимся буквам (кроме первой) присвоить следующие значения:
b, f, p, v= 1;
l= 4;
c, g, j, k, q, s, x, z= 2;
m, n=5;
d, t=3;
r= 0.
3.Если в исходной фамилии рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы.
4.Дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму "буква, цифра, цифра, цифра".
Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz имеют коды соответственно Е460, G200, H416, K530, L300, L222.
Разумеется, такая система собирает вместе не только родственные, но и достаточно различные фамилии. Приведенные выше шесть кодов могли быть получены из фамилий Ellery, Ghosh, Heilbronn, Kant, Ladd и Lissajous. С другой стороны, такие родственные имена, как Rogers и Rodgers, Sinclair и St.Clair или Tchebysheff и Chebyshev, имеют разную кодировку. Но, вообще говоря, система "Soundex" намного увеличивает вероятность обнаружить имя под одной из его масок [4-6].
Несмотря на свою простоту, метод "Soundex" дает достаточно хорошие результаты фонетического поиска. Функции, реализующие данный метод встречаются во многих СУБД и других инструментальных средствах. Однако сам метод и большинство инструментальных средств являются англоязычными. Для фонетического поиска русских фамилий требуется модифицировать метод "Soundex" или разработать метод аналогичный по функциональным возможностям.
7.2.Алгоритмы сортировки
Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному отношению линейного порядка. Различают внутреннюю и внешнюю сортировки. Если речь идет о внутренней сортировке, то предполагается, что все данные помещаются в оперативную память компьютера. Если речь идет о внешней сортировке, то объем данных слишком большой, чтобы все они поместились в оперативную память. Все это приводит к разнообразным методам сортировки.
Большая часть данного раздела посвящена рассмотрению алгоритмов внутренней сортировки. В качестве объекта сортировки рассматривается массивов, т.е. сортируемые данные размещаются в оперативной памяти, организованной линейно. В разделе рассматриваются следующие алгоритмы внутренней сортировки:
сортировка методом пузырька;
сортировка вставки;
сортировка выбором;
пирамидальная сортировка;
быстрая сортировка.
Методы внутренней сортировки хорошо иллюстрируют как одну и ту же задачу можно решить с помощью различных алгоритмов с различной степенью эффективности.
Из методов внешней сортировки в данном разделе рассмотрен только метод сортировки слиянием, позволяющий объединить несколько отсортированных файлов в один.
Временная сложность алгоритмов приводится без доказательства.
