1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы



страница3/18
Дата23.12.2012
Размер1.84 Mb.
ТипДокументы
1   2   3   4   5   6   7   8   9   ...   18

2.5.Отношения и их виды.

Подмножество RÍМn называется n-местным отношением на множестве М. Говорят, что а1, ..., аn находятся в отношении R, если (а1, ..., аn)ÎR. Одноместное отношение - это просто подмножество М. Такие отношения называются признаками. а обладает признаком R, если аÎR и RÍМ. Наиболее часто встречающимися и хорошо изученными являются двухместные (бинарные) отношения. Если а и b находятся в отношении R, это часто записывается как аRb. Для отношений на конечных множествах обычно используются матричный способ задания. Матрица бинарного отношения на множестве М={а1, ..., аm} - это квадратная матрица С размерности m, в которой элемент сij, стоящий на пересечении i-ой строки и j-го столбца, равен 1, если аiRaj, и 0 в противном случае.

Для любого множества М отношение Е, заданное матрицей, в которой по главной диагонали стоят единицы, а в остальных местах - нули, называется отношением равенства на М. Отношение называется обратным к отношению R (обозначается R-1), если aiRaj тогда и только тогда, когда ajR-1ai. Отношение R называется рефлексивным, если для любого аÎМ имеет место аRа. Главная диагональ его матрицы содержит только единицы. Отношение R называется антирефлексивным, если ни для какого aÎМ не выполняется аRа. Главная диагональ его матрицы содержит только нули. Отношение R называется симметричным, если для пары (а, b)ÎМ2 из аRb следует bRа. Матрица симметричного отношения симметрична относительно главной диагонали, т.е. cij=cji для любых i и j. Отношение R симметрично тогда и только тогда, когда R=R-1. Отношение R называется антисимметричным, если из аRb и bRа следует а=b. Отношение R называется транзитивным, если для любых а, b, с из аRb и bRс следует аRс. Отношение R называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Отношение R называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно. Отношение R называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

2.6.Предикаты и кванторы.

Предикатом Р(х1, ..., хn) называется функция Р: М→В, где М - произвольное множество, а В - двоичное множество {0,1}. Иначе говоря, n-местный предикат, определенный на М, - это двузначная функция от n аргументов, принимающих значения в произвольном множестве М. М называется предметной областью предиката, а х1, ..., хn - предметными переменными. Для любых М и n существует взаимно-однозначное соответствие между n-местными отношениями и n-местными предикатами на М.
Каждому n-местному отношению R соответствует предикат Р, такой, что Р(а1,...,аn)=1, если и только если (а1,...,аn)ÎR. Всякий предикат Р(a1,...,an) определяет отношение R, такое, что (а1,...,аn)ÎR, если и только если Р(а1,...,аn)=1. При этом R задает область истинности предиката Р.

Пусть Р(х) - предикат, определенный на М. Высказывание "для всех х из М Р(х) истинно" обозначается "хР(х). Знак " называется квантором общности. Высказывание "существует такой х из М, что Р(х) истинно" обозначается $хР(х). Знак $ называется квантором существования. Переход от Р(х) к "хР(х) или к $хР(х) называется связыванием переменной х. Переменная, на которую навешен квантор, называется связанной; несвязанная переменная называется свободной. Навешивать кванторы можно на любые логические выражения, которые при этом заключаются в скобки. Выражение, на которое навешивается квантор, называется областью действия квантора; все вхождения переменной х в это выражение являются связанными.

2.7.Графы и их виды. Матрицы инцидентности и смежности графа.

Граф — совокупность двух множеств V (точек) и E (линий), между элементами которых определено отношение инцидентности, причем каждый элемент еÎЕ инцидентен ровно двум элементам v, v"ÎV. Элементы множества V называются вершинами графа G, а элементы множества E - его ребрами. Если инцидентные ребру вершины рассматриваются в определенном порядке, то каждому ребру приписывается направление от первой из инцидентных вершин ко второй. Направленные ребра часто называют дугами, а содержащий их граф - ориентированным, в отличие от определенного ранее неориентированного графа. Первая по порядку вершина, инцидентная ребру ориентированного графа, называется его началом, вторая - его концом.

Множество ребер Е может быть пустым. Если же множество вершин V пусто, то пусто и Е. Такой граф называется пустым. Различные ребра могут быть инцидентны одной и той же паре вершин, в этом случае они называются кратными. Граф, содержащий кратные ребра, называется мультиграфом. Ребро может соединять некоторую вершину саму с собой. Такое ребро называется петлей. Если множества вершин и ребер графа конечны, то граф называется конечным.

Задать граф - значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть v1, v2, ..., vn - вершины графа G, а e1, e2, ..., em - его ребра. Отношение инцидентности можно определить матрицей инцидентности ïeijï, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки - ребрам. Если ребро еi инцидентно вершине vj , то eij=1, в противном случае eij=0. В матрице инцидентности ïeijï ориентированного графа G, если вершина vj - начало ребра ei, то eij=-1; если vj - конец ei , то eij=1; если ei - петля, а vj - инцидентная ей вершина, то eij=a, где a - любое число, отличное от 1, 0 и -1. В остальных случаях eij=0.

Матрицей смежности графа называется квадратная матрица ïdijï, столбцам и строкам которой соответствуют вершины графа. Для неориентированного графа dij равно количеству ребер, инцидентных i-й и j-й вершинам, для ориентированного графа этот элемент матрицы смежности равен количеству ребер с началом в i-й вершине и концом в j-й. Таким образом, матрица смежности неориентированного графа симметрична (dij = dji).

3.Алгоритмы.

3.1.Понятие алгоритма и его свойства. Классы алгоритмических задач.

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

  • результативность — алгоритм должен давать конкретное конструктивное решение, а не указывать на возможность решения вообще;

  • достоверность — алгоритм должен соответствовать сущности задачи и формировать верные, не допускающие неоднозначного толкования решения;

  • реалистичность — возможность реализации алгоритма при заданных ограничениях: временных, программных, аппаратных;

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

  • детерминированность (определенность) — алгоритм должен содержать набор точных и понятных указаний, не допускающих неоднозначного толкования;

  • дискретность — допустимость расчленения алгоритма на отдельные этапы с возможностью последовательной их реализации на машине;

  • экономичность — алгоритм должен обеспечивать необходимую и достаточную точность решения задачи.

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

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

3.2.Проблема алгоритмической разрешимости.

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

В теории алгоритмов к алгоритмически неразрешимой относится «проблема остановки»: можно ли по описанию алгоритма и входным данным установить, завершится ли выполнение алгоритма результативной остановкой? Эта проблема имеет ясную программистскую интерпретацию. Часто ошибки разработки приводят к зацикливанию, т.е. ситуации, когда цикл не завершается и не происходит завершения работы программы и остановки. Неразрешимость проблемы остановки означает, что нельзя создать общий, т.е. пригодный для любой программы алгоритм отладки. Неразрешимой является и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который для любых двух алгоритмов (программ) выяснял бы, всегда ли они приводят к одному и тому же результату или нет.

Важность доказательства алгоритмической неразрешимости в том, что если оно получено, то имеет смысл закона-запрета, позволяющего не тратить усилия на поиск решения. Однако алгоритмическая неразрешимость какой-либо задачи в общей постановке не исключает возможности того, что разрешимы какие-то частные её случаи. Справедливо и обратное утверждение: решение частного случая задачи еще не дает повода считать возможным её решение в самом общем случае, т.е. не свидетельствует о её общей алгоритмической разрешимости.

3.3.Понятие сложности алгоритма.

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

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

Задача считается трудноразрешимой, если для неё не удается построить полиномиального алгоритма. В общем случае эффективно исполняемыми можно считать полиномиальные алгоритмы с функциями сложности n, n2 или n3. Например, при решении задачи поиска нужного данного из n имеющихся в худшем варианте сложность равна n. Задача ранжирования, т.е. расстановки в заданном порядке n однотипных данных приводит к полиному 2-й степени. Сложность задачи вычисления определителя системы n линейных уравнений с n неизвестными характеризуется полиномом 3-й степени. Повышение быстродействия элементов компьютера уменьшает время исполнения алгоритма, но не уменьшает степень полинома сложности.

4.Представление данных и программ в ЭВМ. Принципы работы компьютера.

4.1.Системы счисления и их виды.

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

Кp = xn-1*pn-1 +xn-2*pn-2 + ... + x1*p1 + x0*p0 + x-1*p-1 + x-2*p-2 + xmp-m...

или в общем виде , где xi Î {0, 1, ..., p-1} и i – целые числа.

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

Достаточно широкое распространение с появлением компьютеров получили восьмеричная и шестнадцатеричная системы счисления, поскольку представление восьмеричных чисел в двоичной системе счисления тождественно совпадает с их представлением в двоично-восьмеричной системе счисления. Это правило выполняется и для шестнадцатеричной системы счисления. Так как базис восьмеричной системы составляют числа от 0 до 7, то для изображения любой базисной цифры достаточно трех двоичных символов. Базис шестнадцатеричной системы составляет набор xi Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} поэтому для изображения любой базисной цифры достаточно четырех двоичных символов.

Для записи одного и того же значения в различных системах счисления требуется разное число позиций или разрядов. Если длина разрядной сетки задана, то это ограничивает максимальное по абсолютному значению число, которое может быть записано. Пусть длина разрядной сетки равна положительному числу N. Тогда Кpmax=pN-1 , где p - основание системы счисления.
1   2   3   4   5   6   7   8   9   ...   18

Похожие:

1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРеферат на тему: "логистические информационные системы. Иерархия использования логистической информационной системы. Функции логистической информационной системы. Поток информации в предпринимательстве."
Основные направления информационно-технического обеспечения логистических систем
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРазработка автоматизированной информационной системы «кафедра» с помощью современных средств web-программирования
Рассматривается разработка автоматизированной информационной системы «Кафедра» и средства ее реализации
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconБазы данных и информационные системы
...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconЭкзаменационные вопросы по информатике Направление подготовки «Адаптивная физическая культура»
Основные понятия информатики: информационная среда, информационные технологии, информационные системы, базы данных, интеллектуальные...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРабочая программа для студентов направления 230400. 62 «Информационные системы и технологии»
...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconДисциплина «Интеллектуальные информационные системы», пиэ, 4 курс, 1 семестр вопросы на зачет
Понятие интеллектуальной информационной системы (иис), особенности и основные свойства иис
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconИнформационные системы
Информационная система (ИС) – это комплекс, состоящий из информационной базы (хранилища информации) и процедур, позволяющих накапливать,...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРазработка автоматизированной системы эксергетического анализа сложных химико-технологических систем
Поэтому необходимость разработки автоматизированной системы расчета и оптимизации эксергетического баланса хтс произвольной структуры...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconЛекция 1) гис как специализированная информационная система. Структура информационных систем, представление о модели данных. Последовательность действий при создании информационной системы
Модели данных для пространственной информации. Геокодирование, общее понятие. Геокодирование как процесс перевода пространственной...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconТемы, вопросы для изучения
Понятия: системы; фаза; гомогенные и гетерогенные системы; процессы и их классификация; параметры и функции состояния системы
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org