Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Информационные системы и технологии”,Стр 1 из 4Следующая ⇒
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВО “Воронежский государственный УНИВЕРСИТЕТ ИНЖЕНЕРНЫХ технологиЙ”
Ю.В. БУГАЕВ, И.Ю. ШУРУПОВА, О.В. АВСЕЕВА, Л.А. КОРОБОВА ТЕОретИЧЕСКИЕ ОСНОВЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ЛАБОРАТОРНЫЙ ПРАКТИКУМ Для студентов, обучающихся по направлению Информационные системы и технологии”, Очной формы обучения ВОРОНЕЖ УДК 681.3.06; 51(075) ББК Т-
Научный редактор доцент Л.А. КОРОБОВА
Рекомендуется к размещению в ЭОС и ЭБ ВГУИТ
Бугаев, Ю.В. Т- Теоретические основы информационных технологий. Лабораторный практикум [Электронный ресурс]: учеб. пособие / Ю. В. Бугаев, И. Ю. Шурупова, О. В. Авсеева, Л. А. Коробова; Воронеж. гос. ун-т инж. технол. – Воронеж: ВГУИТ, 2016. – 80 с. – [ЭИ]
ISBN Учебное пособие разработано в соответствии с требованиями ФГОС ВО подготовки бакалавров направления 09.03.02 – “Информационные системы и технологии”. В пособии изложена методика выполнения лабораторных работ базовой части блока Б1, приведены варианты заданий.
УДК 519.6; 683.1 Без объявл. ББК ОК2(03) - 2007
ISBN © Бугаев Ю. В., Шурупова И. Ю., Авсеева О. В., Коробова Л. А. 2016 © ФГБОУ ВО “Воронеж. гос. ун-т инж. технол.”, 2016
Оригинал-макет данного издания является собственностью Воронежской государственной технологической академии, его репродуцирование (воспроизведение) любым способом без согласия академии запрещается. ПРЕДИСЛОВИЕ
Процесс изучения дисциплины направлен на формирование компетенции: - способностью использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОПК-2).
В результате освоения дисциплины студент должен: Знать - основные понятия и методы теоретической информатики; - способы представления дискретных структур в информационных системах; Уметь - применять математический аппарат для построения моделей описания и решения прикладных задач; Владеть - навыками моделирования прикладных задач методами теоретической информатики; - навыками построения алгоритмов решения прикладных задач.
Лабораторная работа №1 ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Цель работы: изучение операций над множествами и их свойств, методов доказательства утверждений теории множеств. Теоретические сведения Множеством называется совокупность некоторых объектов, объединенных общим признаком. Для множеств вводятся следующие отношения. Множество А нестрого включено в множество В (обозначается АÍ В) если для любого элемента хÎ А, следует что хÎ B. Нестрогое включение не исключает совпадения множеств. Множество А строго включено в множество В (обозначается АÌ В) если: 1) АÍ В; 2) существует yÎ B, такой, что yÏ A. Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А, т.е. (АÍ В и ВÍ А) Û (А = В). Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому детально разберёмся в методах доказательства этих фактов. 1. Доказательство нестрогого включения АÍ В. Для этого нужно доказать, что любой элемент x, принадлежащий множеству А одновременно является элементом множества В, т.е. (" x Î А) Þ (x Î В). 2. Доказательство строгого включения АÌ В состоит из двух частей: 1) АÍ В; 2) $ y: y Î B и y Ï A. 3. Доказательство равенства А = В сводится к доказательству двух включений А Í В и В Í А. Дадим определения операций над множествами, используя способ задания множества характеристическим свойством или формулой теории множеств. 1. Дополнение : . 2. Пересечение : . 3. Объединение : . 4. Разность : . 5. Симметрическая разность : . В доказательствах будем также использовать следующие краткие обозначения, для того чтобы расписать принадлежность элемента множеству, построенному с помощью операций над множествами. Û Û Фигурная скобка и запятая здесь, как и прежде, обозначает выполнение обоих свойств. Û Квадратная скобка означает выполнение хотя бы одного из свойств. Таким образом, доказательство в дальнейшем распадается на два случая, для которых рассуждения проводятся отдельно, каждое в своей строке. Û Û Распишем также, что означает, что элемент не принадлежит множеству, построенному с помощью операций над множествами. Û Û Û Û Если из условия следует свойство о принадлежности элемента одному множества (например ) и ничего не известно относительно другого (B), которое участвует в формуле доказываемого утверждения, то необходимо рассмотреть оба случая и в обоих случаях вывести (или опровергнуть) требуемое свойство. Утверждение вида эквивалентно включениям или . Пример выполнения работы. 1. Даны множества; , , . Найти: a) ; b) ; Даны множества; , , . Найти: c) ; d) . Решение. a) = [1; 7) b) = [4; 7) = [4; 5] c) = Æ d) = {4} = {1; 2} = {1; 2; 4} 2. Доказать тождество AÇ (B \ C) = (AÇ B) \ (AÇ C). Решение. a) I способ. Докажем два нестрогих включения. 1) Прямое включение AÇ (B \ C) Í (AÇ B) \ (AÇ C). Þ Þ Þ Þ Þ 2) Обратное включение (A Ç B) \ (AÇ C) Í AÇ (B \ C). Þ Þ Þ Þ , так как в 1-м случае имеем противоречие Þ Þ Þ Þ b) II способ. (AÇ B) \ (AÇ C) = = = = = = = AÇ (B \ C) 3. Доказать включение множеств (A1 Ç A2) D (B1 Ç B2) Í (A1 D B1) È (A2 D B2). Решение. Þ Þ Þ Þ Þ Þ Þ Þ 4. Доказать, что A Í B Ç C Û A Í B и A Í C. Решение. 1) Докажем прямое следование, т.е. AÍ BÇ C Þ AÍ B и AÍ C. Пусть справедливо включение , покажем, что AÍ B и AÍ C.
Что и означает выполнение обоих включений . 2) Докажем обратное следование AÍ B и AÍ C Þ AÍ BÇ C. Пусть выполнены оба включения , покажем, что AÍ BÇ C. . Следовательно . Контрольные вопросы 1. Дайте определения операций дополнения, пересечения, объединения, разности и симметричной разности множеств. Приведите примеры выполнения операций. 2. Сформулируйте отрицание принадлежности элемента множествам, построенных с помощью операций над множествами. 3. Приведите способы доказательства отношений нестрогого, строгого включения и равенства множеств. Задание для лабораторной работы. 1. Для множеств варианта выполнить операции над множествами. 2. Доказать равенство множеств 2-мя способами: a) по определению равенства множеств, доказав два нестрогих включения; b) с использованием свойств операций. 3. Доказать включение множеств. 4. Доказать или опровергнуть утверждения о следовании или эквивалентности отношений между множествами. Лабораторная работа №2 НЕЧЁТКИЕ МНОЖЕСТВА Цель работы: изучение способов построения нечётких множеств и операций над нечёткими множествами. Теоретические сведения Нечеткое подмножество A универсального множества E определяется как множество упорядоченных пар A = {mA(х)/х}, где mA(х) – характеристическая функция принадлежности (или просто функция принадлежности), принимающая значения в некотором вполне упорядоченном множестве M (например, M =[ 0, 1 ] ). Функция принадлежности указывает степень (или уровень) принадлежности элемента x подмножеству A. Множество M называют множеством принадлежностей. Если M = { 0, 1 }, то нечеткое подмножество A может рассматриваться как обычное или четкое множество. Примеры записи нечеткого множества Пусть E= {x1, x2, x3, x4, x5 }, M = [ 0, 1 ]; A – нечеткое множество, для которого mA(x1)=0, 3; mA(x2)=0; mA(x3)=1; mA(x4)=0, 5; mA(x5)=0, 9. Тогда множество A можно представить в виде: A = 0, 3/x1 È 0/x2 È 1/x3 È 0, 5/x4 È 0, 9/x5 или
Для построения функции принадлежности могут использоваться прямыеметоды, когда эксперт либо просто задает для каждого xÎ E значение mA(x), либо определяет функцию совместимости. При прямых методах используются также групповые прямые методы, когда, например, группе экспертов предъявляют конкретное лицо, и каждый должен дать один из двух ответов: “этот человек лысый” или “этот человек не лысый”, тогда количество утвердительных ответов, деленное на общее число экспертов, дает значение m" лысый" (данного лица). Как правило, прямые методы задания функции принадлежности используются для измеримых понятий, таких как скорость, время, расстояние, давление, температура и т.д., или когда выделяются полярные значения. Косвенные методы определения значений функции принадлежности используются в случаях, когда нет элементарных измеримых свойств, через которые определяется интересующее нас нечеткое множество. Как правило, это методы попарных сравнений. Если бы значения функций принадлежности были нам известны, например, mA(xi) = wi, i = 1, 2, ..., n, то попарные сравнения можно представить матрицей отношений A = {aij}, где aij = wi/ wj (операция деления). На практике эксперт сам формирует матрицу A, при этом предполагается, что диагональные элементы равны 1, а для элементов симметричных относительно диагонали aij = 1 / aji. Доказано, что в общем случае задача сводится к поиску вектора w, удовлетворяющего уравнению вида Аw = lmaxw, где lmax – наибольшее собственное значение матрицы A. Имеет место теорема Перрона, согласно которой для матрицы А с положительными элементами решение данной задачи существует и является положительным. В случае идеальной согласованности экспертных оценок должно выполняться соотношение . (1) В этом случае lmax совпадает с n – размерностью матрицы А. В случае нарушения условия (1) lmax меньше n. Таким образом, величина разности lmax – n может служить мерой согласованности экспертных оценок. Выполнить операции с нечёткими множествами означает построить функции принадлежности множеств, получившихся в результате. Эти функции определяются с помощью функций принадлежности исходных множеств. 1. Дополнение. 2. Пересечение. A Ç B – наибольшее нечеткое подмножество, содержащееся одновременно в A и B; m A Ç B (x) = min{mA(x), mB(x)}. 3. Объединение. А È В – наименьшее нечеткое подмножество, включающее как А, так и В, с функцией принадлежности m AÈ B (x) = max {(mA(x), mB(x)}. 4. Разность. А \ B= А Ç с функцией принадлежности: mA\B(x) = min { mA(x), 1 – mB(x)}. Пример выполнения работы. 1. Определить нечёткое множество «молодые люди». Решение. В качестве характеристического параметра человека x будем рассматривать его возраст , . Всюду в дальнейшем для краткости записи формул через x будем обозначать его характеристический параметр . a) Определим интервал, на котором . Положим, что если , то , а если , то . Следовательно, если , то . Для построения функции принадлежности зададим значения степени принадлежности элементов в конечном множестве точек. Для этого разобьём интервал на n равных частей (например, пусть , тогда ). Выступим в роли экспертов и зададим во внутренних точках разбиения степени принадлежности элемента нечёткому множеству «молодые люди».
b) Построим аппроксимацию функции . При её построении будем использовать элементарные кривые. Например, через первые и последние 3 точки проведём параболы, а 2 средние точки (28; 0, 7) и (32; 0, 4) соединим прямой. Определим коэффициенты параболы , проходящей через точки (20; 1), (24; 0, 9), (28; 0, 7). Решив систему линейных уравнений , (*) получим . Прямая, проходящая через точки (28; 0, 7) и (32; 0, 4), задаётся формулой . Коэффициенты параболы , проходящей через точки (32; 0, 4), (36; 0, 1), (40; 0), можно определить, решив аналогичную (8) систему линейных уравнений. В этом случае получим . Однако, нетрудно за-метить, что вершина данной параболы находится в точке (40; 0), поэтому она имеет вид . Подставив в уравнение значения двух других точек и решив полученную систему уравнений, определим неизвестные параметры . Таким образом, . Построим график данной функции 2. Дано множество марок автомобилей X = {Жигули; Волга; Мерседес; Феррари; Ягуар}. Построить матрицу парных сравнений для нечёткого множества A = «скоростной автомобиль». Решение. Построим матрицу парных сравнений для определения значений функции принадлежности в конечном множестве точек косвенным методом. Так как автомобили каждой последующей марки имеют более высокие скоростные качества, то элементы матрицы , находящиеся ниже главной диагонали, превосходят 1. Степень превосходства каждой последующей марки оценим, выступив в качестве эксперта. Элемент, находящийся выше главной диагонали, согласно свойствам матрицы парных сравнений определяется как обратный симметричному элементу. Данная матрица не является идеально согласованной. 3. Даны множества:
Найти: a) ; b) c) . Решение. a) Так как , то b) c) Контрольные вопросы 1. Дайте определение нечёткого множества и функции принадлежности. 2. Каковы методы построения функций принадлежности нечетких множеств? 3. Как определяются операции над нечёткими множествами? Задание для лабораторной работы. 1. Определить нечёткое множество варианта, для этого: a) прямым методом задать функцию принадлежности нечёткого множества (использовать 3-5 точек интервала, для которого ); b) построить аппроксимацию функции принадлежности , проходящую через эти точки, используя элементарные функции, выписать её аналитическое представление и построить график; 2. Для заданных альтернатив и нечёткого множества варианта построить матрицу парных сравнений для определения функции принадлежности косвенным методом. 3. Выполнить операции над нечеткими множествами. Лабораторная работа № 3 КОМБИНАТОРНЫЕ АЛГОРИТМЫ Цель работы: изучение комбинаторных объектов, алгоритмов их генерации и применение данных алгоритмов к решению задач. Теоретические сведения Приведём эффективные алгоритмы, генерирующие основные комбинаторные объекты. 1. Размещения с повторениями. Данный алгоритм генерирует наиболее общий класс размещений с повторениями, когда i-ый элемент размещения выбирается из своего множества Xi. Генерация выполняется в лексикографическом порядке. Используемые обозначения: A – массив, содержащий размещение; x – массив, содержащий минимальные значения элементов размещения; y – массив, содержащий максимальные значения элементов размещения; k – количество элементов в размещении. { i : = k ; for ( j = ) Aj : = xj ; while ( i ³ 1 ) { вывод массива A; i : = k ; while ( Ai = yi ) i : = i -1; if ( i ³ 1) { Ai : = Ai +1; for ( j = ) Aj : = xj ; } } } 2. Перестановки без повторений. Данный алгоритм генерирует перестановки без повторений в антилексикографическом порядке. При генерации используется рекурсивная функция. Используемые обозначения: P – массив, содержащий перестановку; n – количество элементов в перестановке; « – поменять местами переменные. reverse ( m ) { i : =1; j : = m ; while ( i < j ) {Pi «Pj ; i : =i +1; j : =j -1; } } Antilex ( m ) { if ( m =1) вывод массива P ; else for ( i = ) { Antilex ( m -1); if (i < m ) { Pi «Pm ; reverse ( m -1); } } } { for ( i = ) Pi : = i; Antilex ( n ); } 3. Сочетания без повторений. Генерация сочетаний без повторений так же, как и размещений с повторениями, выполняется в лексикографическом порядке. Используемые обозначения: С – массив, содержащий сочетание; k – количество элементов в сочетании; n – количество элементов в исходном множестве. { for ( i = ) Ci : = i; p : =k; while ( p ³ 1) { вывод массива C; if ( Ck = n ) p : = p -1; else p : =k; if ( p ³ 1) for ( i = ) Ci : = Cp + i – p +1; } } 4. Размещения без повторений. При генерации размещений без повторений используется комбинация двух алгоритмов: генерация сочетаний без повторений и перестановок без повторений. Для этого в алгоритме генерации сочетаний без повторений вместо печати сгенерированной комбинации выполняется генерация всех её перестановок (так как размещения отличаются от сочетаний тем, что в них учитывается порядок выбранных элементов). При реализации этого алгоритма сначала в массиве С генерируется сочетание, затем, вместо вывода массива С, его элементы копируются в массив P и вызывается рекурсивная процедура генерации перестановок. Задание для лабораторной работы. 1. Для задания варианта определить теоретическое число комбинаций, удовлетворяющих условию или требуемых для решения задачи. 2. Написать программу, которая выполняет задание варианта с помощью генерации всех соответствующих комбинаций, используя комбинаторные алгоритмы. При этом: a) во время генерации производить подсчет общего числа сгенерированных вариантов и число вариантов, удовлетворяющих условию задачи, вывести эти значения на экран; b) если решение не единственное, то вывод комбинаций осуществлять в файл. 3. Формулу для расчета теоретического значения числа комбинаций, текст программы и результат её работы для контрольного примера оформить в отчёт. Лабораторная работа №4 БУЛЕВЫХ ФУНКЦИЙ Цель работы: овладение аппаратом булевых функций для решения проблемы выполнимости. Теоретические сведения Введем следующие обозначения . Легко проверить, что , . Теорема 1. (о разложении булевых функций). Любую булеву функцию можно представить в виде (5.1) где дизъюнкции берутся по всем возможным наборам ( ). Теорема 2. Всякая булева функция (кроме 0) имеет единственную СДН-форму . С помощью принципа двойственности легко доказать представление функции СКН-формой. Теорема 3. Всякая булева функция (кроме 1) имеет единственную СКН-форму . С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы. Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма. Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму. Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Хi или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее. В ЭВМ совершенные формы представляются в виде матрицы размера k´ n, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f. Пусть х – массив пропозиционных переменных. Предположим, хi получили некоторые значения и необходимо вычислить значение нормальной формы f. Предлагаются следующие правила:
Эффективность данного алгоритма проявляется также в том, что цикл можно прервать, как только будет найдено необходимое значение i или j. Например, вычислим значение функции f(x1, x2) = x1 ~ x2 при x1 = 0; x2 = 1. Запишем таблицу истинности функции f:
Тогда FСДНФ = ; FСКНФ = . Поскольку ни одна из строк FСДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями хj, то f (0, 1) = 0. Тоже самое можно определить и по СКНФ, так как первая строка FСКНФ совпадает со значениями хj, то f (0, 1) = 0. Сформулируем законы булевой алгебры и производные от них формулы в терминах булевых функций. 1. X Ù Y º Y Ù X, X Ú Y º YÚ X. 2. (X Ù Y)Ù Z º X Ù (YÙ Z), (XÚ Y)Ú Z º XÚ (YÚ Z). 3. XÙ X º X, XÚ X º X. 4. XÚ (X Y) º X, X (XÚ Y) º X. 5. X Ù (YÚ Z) º (X Ù Y)Ú (X Ù Z), XÚ (YÙ Z) º (XÚ Y)Ù (XÚ Z). 6. XÙ 0 º Л, XÙ 1 º X, XÚ 0 º X, XÚ 1 º 1. 7. , . 8. . 9. º 0. 10. º 1. 11. . 12. . 13. , 14. , Для преобразования одной совершенной нормальной формы в другую нужно вначале максимально упростить исходную форму, воспользовавшись законами 4, 5, 13, 14. Затем преобразовать упрощенную формулу по свойству взаимной дистрибутивности 5, получив нормальную форму, и развернуть её в требуемую совершенную форму по законам склеивания 13. Задание для лабораторной работы. 1. Написать и отладить программу в соответствии с вариантом задания. Такая программа должна содержать: a) ввод данных из файла; b) выполнение индивидуального задания варианта и вывод его результатов. 2. Продемонстрировать работу программы на контрольном примере. 3. Преобразовать аналитическое представление совершенной нормальной формы, определённой заданием, во вторую совершенную нормальную форму. 4. Текст программы, исходный файл контрольного примера, результаты работы программы на контрольном примере и преобразование совершенных нормальных форм оформить в отчет.
Лабораторная работа №5 БИНАРНЫЕ ОТНОШЕНИЯ Цель работы: изучение способов задания бинарного отношения, свойств бинарных отношений, технологии построения программ, реализующих построение бинарного отношения и проверку его свойств. Теоретические сведения Бинарным отношением между элементами множеств А и В называется любое подмножество R Í A´ B. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А. Всюду далее будут рассматриваться такие отношения. Если (x, y)Î R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R. Способы задания бинарных отношений. 1. Матричное задание. Пусть А – конечное или счетное множество А = {xi}. Тогда бинарное отношение R задаётся матрицей R = {rij}, элементы которой определяются соотношением: 2. Задание с помощью графа. Для конечного или счетного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф – фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть xi, а наличие дуги, соединяющей вершины xi и xj, означает, что (xi, xj)Î R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. 3. Задание верхними и нижними срезами – универсальный способ задания бинарного отношения для любых множеств. Верхний срез GR(x) отношения R в точке x Î А GR(x) = { yÎ A | (y, x)Î R }. Нижний срез HR(x) отношения R в точке xÎ А HR(x) = { yÎ A | (x, y)Î R }. Запишем кратко свойства бинарных отношений и условия, которым должна удовлетворять матрица бинарного отношения, удовлетворяющего этому свойству. 1) Рефлексивность. Бинарное отношение рефлексивно, если . Популярное:
|
Последнее изменение этой страницы: 2017-03-11; Просмотров: 740; Нарушение авторского права страницы