WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Дискретная математика

Хабаровск 2011

3

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Тихоокеанский государственный университет»

Дискретная математика

Методические указания к выполнению лабораторных работ

для студентов I курса специальностей ИС и УИТС

Хабаровск Издательство ТОГУ 2011 4 Вводные положения «Математика» в переводе с греческого означает «наука», а слово «дискретный» – «отдельный, раздельный». В силу этого дискретная математика – это наука, которая изучает отдельные величины, и по этой причине в нее можно включить многие дисциплины, такие, например, как теория множеств и алгебраических структур, теория графов, теория формальных грамматик, алгоритмов и автоматов, комбинаторный анализ, теория кодирования и другие. Поскольку раздел «Математическая логика и теория алгоритмов» для студентов специальностей ИС, УИТС, ПМ вынесен за рамки курса «Дискретная математика» и к тому же количество часов, отведенных на выполнение лабораторных работ, ограничено, то в данных методических указаниях рассмотрены лишь некоторые аспекты дискретной математики.

Методические указания призваны помочь студентам овладеть навыками использования методов дискретной математики при решении различного рода задач.

Лабораторная работа № 1 посвящена позиционным системам счислений. Она поможет студентам легко ориентироваться в бинарной системе, которая является основой информатики, на этой системе построена вся алгебра Буля.

По первой лабораторной работе преподаватель выносит свое суждение об уровне подготовки каждого студента по дисциплинам «Информатика» и «Программирование», предварительное изучение которых совершенно необходимо для выполнения всех лабораторных работ. Помимо упомянутых дисциплин студенту также необходимо иметь сведения из школьного курса математики и курса «Алгебра», изучаемого в первом семестре в университетах.

Лабораторные работы № 2 и 3 относятся к теории множеств, которая является в настоящее время основанием всей математики.

Лабораторные работы № 4 и 5 затрагивают проблемы теории графов, которая применяется во многих приложениях математики, причем не только в технических, но и в естественно-научных дисциплинах.





Лабораторная работа № 6 посвящена теории кодирования, которая является основанием всех информационных систем.

ОРГАНИЗАЦИЯ ЛАБОРАТОРНЫХ РАБОТ

В процессе выполнения лабораторной работы студент должен последовательно пройти следующие этапы:

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

Разработка программы;

2.

Тестирование программы;

3.

Оформление отчета по лабораторной работе.

4.

Отчет должен содержать:

Задание (постановку задачи);

1.

Описание алгоритма или блок-схему алгоритма;

2.

Описание входных и выходных данных;

3.

Текст (код) программы;

4.

Три тестовых примера, решенных 1) «вручную» и 2) на компьютере.

5.

После завершения каждой лабораторной работы студент получает в журнале « », которая состоит из 1. « | » – это означает, что лабораторная работа оформлена на листах формата А4 правильно, то есть титульный лист содержит все необходимые сведения, на каждом внутреннем листе присутствует внизу заполненная рамка, представлена постановка задачи, дано описание алгоритма, описание входных и выходных данных, текст программы, представлено решение трех контрольных примеров.

« – » – это означает, что программа правильно реагирует на заданные 2.

преподавателем тестовые примеры.

« \ » – это означает, что студент полностью разбирается в алгоритме 3.

решения поставленной задачи.

« / » – это означает, что в программе, которую предоставил студент, 4.

он разбирается полностью.

Вариант каждого студента соответствует порядковому номеру его фамилии в списке в журнале преподавателя.

Лабораторная работа №

СИСТЕМЫ СЧИСЛЕНИЯ

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

Задание лабораторной работы № 1 отличается для студентов с четными и нечетными вариантами.

Вариант четный:

Дано натуральное число в десятичной системе счисления. Найти запись этого числа в системе счисления по основанию k, где k – натуральное число такое, что 2 k 36.

Вариант нечетный:

Дано натуральное число n в системе счисления по основанию k, где k – натуральное число такое, что 2 k 36. Найти запись числа n в десятичной системе счисления.

Для выполнения лабораторной работы № 1 необходимо вспомнить следующий теоретический материал.

Рассмотрим число 77, в котором одна и та же цифра 7 обозначает совершенно разные числа. Цифра 7, стоящая в левой позиции, обозначает семь десятков, а 7, записанная в правой позиции, означает семь единиц.

Таким образом, число 77 можно представить как 7 10 7 или 7 101 7 100. Вообще, любое натуральное число десятичной системы счисления можно записать в виде суммы соответствующих произведений.





Например, 2765 2 103 7 102 6 101 5 100. Позиция цифры определяет степень 10. Крайняя правая позиция соответствует 100, затем 101 и так далее в возрастающем порядке справа налево. Аналогично строятся другие позиционные системы счисления.

В позиционной системе счисления выбирают определенное натуральное число k, большее единицы, и объявляют его основанием этой системы.

Вводят ровно k различных символов, которые называют цифрами.

Затем каждой цифре сопоставляют числа нуль, один, два и так далее, до числа k 1.

Все остальные натуральные числа, начиная с числа k, представляют в виде последовательности цифр.

Если натуральное число n в k -ичной системе счисления, представлено последовательностью цифр n amam1 a2a1a0, то в десятичной системе счисления его можно подсчитать как в этой сумме произведений каждое число ai, i 0,, m, соответствует цифре ai системы счисления по основанию k.

Рассмотрим в качестве примера пятеричную систему счисления, в которой основание k 5.

В пятеричной системе различают пять цифр: 0, 1, 2, 3, 4. Цифра соответствует числу нуль, цифра 1 сопоставлена числу один, цифра 2 – числу два, цифра 3 – числу три, а цифра 4 есть запись числа четыре. В пятеричной системе число пять представляется цифровой последовательностью 10, число шесть – последовательностью 11, а число двести семьдесят три записывается как 2043.

Для того чтобы различать представления чисел в различных системах, мы будем писать основание системы в виде индекса при числе. Например, запись 111 соответствует числу сто одиннадцать в десятичной системе 11110 1 102 1 101 1 100 и числу семь в двоичной системе 111 1 22 1 21 1 20. Заметим, что одно и то же число имеет различные представления в отличных друг от друга системах, например 20435 27310.

Разложение по степеням основания k верно для любой k -ичной системы счисления. Возьмем в качестве примера шестнадцатеричную систему счисления, для которой недостаточно арабских цифр от 0 до 9, не хватает еще шести символов. Введем в качестве цифр дополнительные символы A, B, C, D, E, F, которые будут соответствовать числам десять, одиннадцать, двенадцать, тринадцать, четырнадцать и пятнадцать. Выберем произвольное число, например B73F16. Цифра В соответствует числу 11, цифра 7 – числу 7, цифра 3 – числу 3, цифра F – числу 15; основание системы счисления k 16. Учитывая позицию каждой цифры в записи числа B73F16, его можно представить как B73F16 11 163 7 162 3 161 15 160.

Посчитав данную сумму произведений, мы получим число 46911. Таким образом, число B73F16 записывается в десятичной системе 4691110.

Если, наоборот, мы хотим из десятичной системы счисления перейти в систему по основанию k, то нужно Разделить натуральное число n, записанное в десятичной системе, на число k, получить частное q1 и остаток r1. Найти соответствующую цифру r1 в k -ичной системе для остатка r1 и записать ее в крайнюю правую позицию будущего числа.

Разделить частное q1 на число k, получить частное q2 и остаток r2.

Найти соответствующую цифру r2 в k -ичной системе для остатка r2 и записать ее в следующую, находящуюся левее от r1, позицию будущего числа.

Делить частное qi на число k, выполняя все действия, аналогичные пункту 2, до тех пор, пока следующее частное qi 1 станет равно нулю.

Если на некотором шаге m частное qm 0, то мы получили искомое число rm rm1 r2r1 – это представление натурального числа n в системе счисления по основанию k. Заметьте, что цифры ri, соответствующие остаткам ri, нужно располагать в обратном порядке их появления при делении, чтобы получить искомое число.

Например, если нужно представить число 4691110 в шестнадцатеричной системе счисления, то вначале делим данное число на число 16. Получим частное q1 2931 и остаток от деления r1 15. В шестнадцатеричной системе счисления числу r1 15 соответствует цифра r1 F. Запишем ее в крайнюю правую позицию будущего представления числа 46911. На следующем шаге делим частное q1 2931 нацело на число 16. Получим новое частное q2 183 и остаток r2 3. Числу r2 3 соответствует цифра r2 3.

Запишем ее слева от цифры F и будем иметь 3F. На третьем шаге, разделив частное q2 183 на 16, получим новое частное q3 11 и остаток r3 7.

Числу r3 7 соответствует цифра r3 7. Допишем ее левее 3F и получим запись 73F. На четвертом шаге частное q3 11 снова поделим на число и получим частное q4 0, остаток r4 11. Числу r4 11 соответствует в шестнадцатеричной системе счисления цифра r4 B, поэтому и допишем ее слева от 73F. Получили число B73F16. Так как частное q4 0, то B73F есть искомое представление числа 4691110.

ДИАГРАММЫ ЭЙЛЕРА – ВЕННА

И ЗАКОНЫ ТЕОРИИ МНОЖЕСТВ

Цель лабораторной работы состоит в освоении основных операций над множествами и умении отображать эти операции на диаграммах Эйлера – Венна. Также необходимо научиться оптимально использовать законы теории множеств при упрощении выражений и доказательстве справедливости отношений.

Задание лабораторной работы № 2 каждый студент выбирает из таблицы заданий в соответствии со своим вариантом.

Вариант:

Для двух данных в таблице выражений показать справедливость их выполнения двумя способами:

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

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

Номер Два выражения соответствующего варианта варианта

A B C A B C

A C B D A B C D

A C B D A B C D

A C B A A B

A B B C A C

Для выполнения лабораторной работы № 2 необходимо использовать следующий теоретический материал.

Под множеством понимают, следуя основателю теории Г. Кантору, «многое, мыслимое как единое». Другими словами, множество есть совокупность определенных вполне различаемых объектов (субъектов), которые называются элементами, объединенных некоторым свойством. Множества будем обозначать прописными буквами латинского алфавита.

В дальнейшем будем считать, что все рассматриваемые нами множества лежат в некотором общем для всех, универсальном множестве, которое обозначим 1.

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

Таблица отношений и операций над множествами Два множества А и В равны, если они содержат одни и те же эле- А=В менты.

Множество А есть подмножестA B во множества В, если каждый элемент А является элементом и В. Говорят, что А включено в В.

Дополнением множества А до универсального множества 1 наA зывается множество A, элементы которого не принадлежат А.

Пересечением двух множеств А и В называется множество A B элементов, принадлежащих одновременно и множеству А, и множеству В.

Объединением множеств А и В называется множество элементов, принадлежащих хотя бы одному из множеств А или В.

Разностью между множествами А и В называется совокупность A B тех элементов множества А, которые не принадлежат множеству В.

Симметрическая разность А и В есть объединение двух разностей Порядок выполнения операций в выражениях определяется следующим образом. Прежде всего выполняется операция дополнения множества до универсального множества 1. Затем выполняются последовательно слева направо действия, заданные в скобках. Пересечение считают теоретикомножественным умножением, а объединение – теоретико-множественным сложением. Поэтому сначала выполняют операцию пересечения и только после нее – объединения или разности.

Пересечение и объединение рассматривают как умножение и сложение в силу того, что своими свойствами они напоминают эти арифметические операции. По этой же причине пустое множество похоже на число 0, а универсальное множество 1 – на число 1.

Рассмотрим пример, иллюстрирующий диаграммами Эйлера – Венна справедливость следующего отношения включения:

1) Расставим порядок выполнения операций в данном выражении:

2) Построим диаграмму Эйлера – Венна, на которой зададим все три множества А, В, С, фигурирующие в этом отношении:

3) В силу того, что в нашем выражении присутствуют 7 операций и одно отношение « », которое называют, помимо прочего, включением, сделаем еще 7 копий этой диаграммы.

4) Закрасим последовательно в каждой из семи диаграмм множества, которые получатся в результате выполнения указанных операций, подписывая диаграммы соответствующими выражениями. Заметим, что множества, соответствующие результатам операций 1 и 2 левой части отношения включения « », мы закрасили в более темный цвет, чем множества из правой части. Вследствие этого на восьмой диаграмме будет хорошо видно, каким образом множество, соответствующее левой части включения содержится во множестве правой части.

A B C A B C

A B C A B C

5) Проиллюстрируем последней восьмой диаграммой отношение включения « » между множествами A B C и A B C A B C.

Рассмотрим пример, иллюстрирующий диаграммами Эйлера – Венна 1) Расставим порядок выполнения операций в данном выражении:

2) Построим диаграмму Эйлера – Венна, на которой зададим два множества А, В, фигурирующие в данном отношении:

3) В силу того, что в нашем выражении присутствуют 4 операции и одно отношение равенства «=», сделаем еще 3 копии этой диаграммы.

4) Закрасим последовательно в каждой из диаграмм множества, получающиеся в результате выполнения указанных четырех операций, подписывая диаграммы соответствующими выражениями.

A B B A B A B A B

5) Заметим, что четвертая диаграмма в точности совпадает с третьей диаграммой. Таким образом, мы показали, что множество A B A B равно множеству A B.

Для выполнения второй части лабораторной работы № 2 при доказательстве справедливости заданных отношений необходимо использовать следующие законы теории множеств, верные для любых множеств А, В, С.

A B B A – закон коммутативности пересечения.

A B B A – закон коммутативности объединения.

пересечения относительно объединения.

объединения относительно пересечения.

A A A – закон идемпотентности пересечения.

A A A – закон идемпотентности объединения.

10.

11.

12.

13.

A A 1 – закон исключенного третьего.

14.

A B A B – закон де Моргана для дополнения пересечения.

15.

A B A B – закон де Моргана для дополнения объединения.

16.

17.

18.

19.

20.

21.

22.

23.

Замечание 1. Очевидно, что =1 и 1 =.

Замечание 2. Для любых множеств А и В верно, что A A B.

Замечание 3. Законы де Моргана можно распространить на большее число множеств:

справедливость этого отношения, используя законы теории множеств.

Возьмем левую часть A B A B данного равенства и сведем ее к правой части A B.

1) Вначале избавимся от разности «–», применив 22-й закон для выражения в скобках, получим B A B B A B. Над знаком «=» всегда будем ставить номер используемого закона.

2) Опустив внешние скобки, используем 15-й закон де Моргана для дополнения пересечения B A B B A B.

4) Используем для второго члена объединения 13-й закон B B, а затем 10-й закон B A B A.

5) Таким образом, вместо выражения в скобках B A B в левую часть A B A B исходного равенства можно подставить множество 6) Далее в полученном выражении 23-го 7) К уменьшаемому этой разности применим 6-й закон дистрибутивности.

8) Используем 14-й закон 9) Уменьшаемое A B A станет равно A B.

10) Вычитаемое разности A B A A B A преобразуем с помощью 1-го закона коммутативности и 3-го закона ассоциативности переA B A A A B A A B.

сечения. Получим 11) Затем, используя последовательно 13, 1 и 9-й законы, будем иметь 12) Вспомним, что уменьшаемое равно A B, а вычитаемое равно.

Применим к полученной разности 22-й закон A B A B.

14) Используя 11-й закон, получим A B 1 A B.

15) Таким образом, мы из левой части A B A B заданного отношения получили его правую часть A B, тем самым доказав справедливость равенства A B A B A B.

Рассмотрим также в качестве примера отношение включения A B C B C. Докажем справедливость этого выражения, используя законы теории множеств и второе замечание.

1) Преобразуем левую часть A B C данного отношения с помощью 2) Симметрическую разность « » в правой части B C отношения включения распишем по определению B C B C C B.

3) К полученному выше выражению применим два раза 22-й закон, тогда 4) Заметим, что первый член объединения B C фигурирует и в левой части отношения включения в качестве члена пересечения.

5) Для того чтобы к B C присоединилось множество А, используем 6) В последнем выражении раскроем скобки с помощью 5-го закона дистB C A B C A.

дем иметь 8) С помощью 1-го закона коммутативности и 3-го закона ассоциативности это преобразованная правая часть.

A B C A B C B C A C B.

Это означает, что левая часть исходного отношения включения, равная по первому пункту этого примера A B C, содержится в качестве первого члена объединения в правой части B C, равной по

ВИДЫ БИНАРНЫХ ОТНОШЕНИЙ

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

Задание лабораторной работы № 3 отличается для студентов с четными и нечетными вариантами.

Вариант четный:

Дана матрица бинарного отношения, заданного на конечном множестве.

Установить, является ли данное отношение рефлексивным, антисимметричным, транзитивным.

Вариант нечетный:

Дана матрица бинарного отношения, заданного на конечном множестве.

Установить, является ли данное отношение иррефлексивным, симметричным, транзитивным.

Для выполнения лабораторной работы № 3 необходимо использовать следующий теоретический материал.

Предварительно вспомним некоторые распространенные обозначения. Символ « » читается «для каждого», « » – «существует», «» – «принадлежит», «» – « не принадлежит», знак «:» означает слова «такой, что».

Если дано некоторое конечное множество А, то все его элементы можно пронумеровать:. Произвольные элементы множества А будем обозначать ai или a, b, c.

Два элемента a и b, записанные друг за другом, будем называть упорядоченной парой и обозначать a, b. Здесь a является первой компонентой данной пары, b – второй компонентой.

Если к примеру множество C 1,, то можно составить упорядоченные пары,1 и 1,, которые абсолютно различны между собой и совершенно отличны от самого множества 1, тем, что в упорядоченной паре важен порядок появления элементов. К тому же, если из пары 1, удалить одну компоненту, то пара исчезнет. Но во множестве 1, каждый элемент не зависит от другого элемента, и если мы уберем элемент * из C 1,, то в этом множестве С останется еще элемент 1.

Множество всех упорядоченных пар, компоненты которых принадлежат А, называют декартовым произведением множества А и обозначают A2. Таким образом, A2 a, b : a A, b A.

Например, если C 1,, то его декартово произведение есть множество C 2 1,1, 1,,,,1.

Если в декартовом произведении множества А выделить некоторые упорядоченные пары, отличающиеся особым свойством, то мы получим новое множество R. Это множество R будет подмножеством A2, т. е.

R A2. Множество R называют бинарным отношением, заданным на множестве А.

Если бинарное отношение состоит из упорядоченных пар, в которых первая компонента совпадает со второй, то оно называется тождественным на всем множестве А и обозначается I A. Таким образом, I A a, a : a A. Заметим, что каждый элемент множества А образует пару с одинаковыми компонентами, попадающую в тождественное отношение.

Например, если C 1,, то тождественное отношение, заданное на всем С, есть множество I C 1,1,,.

Если дано бинарное отношение R A2, то обратным к нему называют отношение R 1 b, a : b A, a A, a, b R.

Например, если на множестве C 1, задано бинарное отношение R 1,,,, то обратным к нему будет отношение R 1,1,,.

Заметим, что в обратном отношении R 1 все упорядоченные пары записываются в обратном порядке, нежели пары в исходном R.

Если даны два бинарных отношения R A2 и S A2, то композицией R A2 и S A2 называют новое отношение Замечание 1. Композиция R S будет отличаться от S R.

Например, если на множестве C 1, заданы бинарные отношения S R,. Рассмотрим подробнее, каким образом получается композиция R S из отношений R и S. Возьмем первый элемент 1, R. Второй компонентой этой пары является. Найдем все такие пары в S, которые начинаются именно со. В S есть такая пара,1. Составим из упорядоченных пар 1, R и,1 S новую пару 1,1, убрав посредника *.

Эта пара 1,1 R S. Возьмем следующий элемент, R. Второй компонентой этой пары снова является. Найдем все пары из S, которые начинаются со. В S есть такая пара,1. Составим из упорядоченных пар, R и,1 S новую пару,1, убрав посредника между ними.

Полученная пара,1 R S. Поскольку мы перебрали все элементы, R S 1,1,,1. Аналогично для определения композиции S R к паре подбираем пару из R, первой компонентой которой является 1.

Это будет пара 1, R. Составим из пары,1 S и 1, R, убрав посредника 1, новую пару, S R. Таким образом, S R,.

что Отношение называется антиR R IA дует, что Отношение называется транR RR зитивным, если из того, что пары Если на конечном множестве задано бинарное отношение R A, то можно построить матрицу этого отношения. Номера строк и столбцов матрицы будут совпадать с номерами элементов множества А. Таким образом, матрица отношения будет квадратной, n - го порядка, где n – количество элементов, содержащихся в А. Матрицу заданного отношения R A2 обозначим M R. Каждый элемент mij M R равен нулю или единице. mij 1, если упорядоченная пара ai, a j R. Но если пара a, a R, то mij 0. Ноль в данном контексте следует воспринимать не как число, а как слово «нет», единицу можно считать словом «да», или «истинно, что пара ai, a j R » и т. п.

Эту матрицу перестановкой столбцов можно свести к.

Нетрудно доказать следующие свойства матриц отношений.

Если отношение R A2 рефлексивно, то его матрица имеет на главной диагонали только единицы, т. е. mii 1 для.

Если отношение R A2 антирефлексивно, то его матрица имеет на главной диагонали только нули, т. е. mii 0 для.

Если отношение R A2 антисимметрично, то для каждого элемента его матрицы такого, что mij 1 симметричный ему элемент m ji 0 для Если отношение R A2 транзитивно, то элементы его матрицы должны удовлетворять следующему условию. Если mij 1 и в то же самое время m jk 1, то обязательно должно выполняться mik 1 для, Рассмотрим, например, матрицу отношения M R.

1) Поскольку на главной диагонали стоят ноль и единица, то R C 2 не является ни рефлексивным, ни иррефлексивным отношением.

2) В силу того, что элементу m12 1 соответствует симметричный ему элемент m21 0, делаем вывод, что отношение R A2 антисимметрично.

3) Для элемента m12 1 только один соответствующий ему элемент m22 1.

Проверяем, что выполняется условие транзитивности m12 1, следовательно, отношение R A2 транзитивно.

СПОСОБЫ ЗАДАНИЯ ГРАФОВ

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

Задание лабораторной работы № 4 является общим для всех вариантов.

В городе имеется N остановок и M маршрутов автобусов, заданных через остановки. Построить граф движения автобусов с помощью а) матрицы смежности вершин;

б) матрицы инцидентности.

Для выполнения лабораторной работы № 4 нужно воспользоваться данным ниже теоретическим материалом.

Графом называют совокупность двух множеств V и Е, которые определим следующим образом. Множество V будем всегда предполагать непустым и конечным, его элементы назовем вершинами. Элементы множества Е задаются с помощью вершин, их называют ребрами. Всякое ребро есть неупорядоченная пара вершин. Обозначим произвольное ребро ek («e» – это первая буква английского слова «edge», что в переводе означает «ребро»), а вершину vi («v» – это первая буква слова «vertex» – «вершина»), тогда ek vi, v j.

В случае, когда ek vi, v j, говорят, что вершины vi и v j являются концами ребра ek, а само ребро ek инцидентно каждой из вершин vi и v j.

Считают также, что вершины vi и v j инцидентны ребру ek.

Вершины vi и v j называются смежными, если они инцидентны одному и тому же ребру ek vi, v j, т. е. они являются его концами.

Граф будем обозначать G («G» – это первая буква слова «Graph» – «граф»), или V, E, или G V, E.

Граф обычно изображают в виде диаграммы, на которой вершины задаются точками, а ребра – непрерывными линиями, соединяющими точки.

В данном графе G вершины обозначены своими номерами. Множество V задается 6 вершинами, V 1, 2, 3, 4, 5, 6. Множество ребер Е содержит ребер, E 2, 3, 2, 4, 4, 5, 4, 6, 5, 6.

Если в ребре ek vi, v j его концы vi и v j совпадают, то такое особое ребро ek vi определяется только одной вершиной и называется петлей.

вершинам, то они называются кратными ребрами.

Если в ребре ek vi, v j ввести ориентацию, другими словами, считать, что первая вершина vi является началом ребра, а вторая вершина v j – концом ребра ek, то само ребро превратится в упорядоченную пару вершин ek vi, v j. В этом случае говорят, что ek – ориентированное ребро, или дуга.

Граф, в котором все ребра ориентированы, называют орграфом.

Обозначать орграф будем через Г, («Г» – буква греческого алфавита, соответствующая букве «G» латинского алфавита).

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

В этом орграфе Г имеется 5 вершин, V 1, 2, 3, 4, 5, и 4 дуги, Матрица инцидентности графа G состоит из n строк и m столбцов, где n – это число вершин, m – число ребер. Обозначим матрицу инцидентности графа G через InG («In» – это первые две буквы слова «incidence» – «инцидентность»). Каждый элемент mij матрицы InG является либо 0, либо 1. Элемент mij InG равен единице, если вершина vi инцидентна ребру e j.

В противном случае элемент mij InG равен нулю.

Рассмотрим в качестве примера граф G. Матрица инцидентности данного графа будет размерности 6 5, так как в графе 6 вершин и 5 ребер.

В каждом столбце, соответствующем номеру ребра, матрица InG имеет только две единицы, соответствующие номерам вершин, инцидентных этому ребру. Так, первое ребро графа G задается вершинами 2 и 3, поэтому в матрице инцидентности в первом столбце единицы стоят во второй и третьей строках. Второе ребро инцидентно вершинам 2 и 4, по этой причине во втором столбце матрицы единицы стоят во второй и четвертой строках. Аналогично задаются третье и все остальные ребра.

Матрица инцидентности орграфа Г состоит из n строк и m столбцов, где n – это число вершин, m – число дуг. Обозначим матрицу инцидентности орграфа Г через In. Каждый элемент mij этой матрицы In является либо 0, либо 1, либо (–1). Элемент mij In равен 1, если вершина vi является началом дуги e j. Элемент mij In равен (–1), если вершина vi является концом дуги e j. В остальных случаях элемент mij In равен нулю.

Рассмотрим в качестве примера орграф Г. Матрица инцидентности данного орграфа будет размерности 5 4, так как в графе 5 вершин и 4 дуги.

Первый столбец матрицы инцидентности In соответствует дуге (1, 2) орграфа Г, которая имеет начало в вершине 1, поэтому в первой строке матрицы стоит единица, а конец дуги находится в вершине 2, по этой причине во второй строке стоит (–1). Второй столбец матрицы определяет дугу (2, 3), поэтому во второй строке стоит единица, а в третьей строке стоит (–1). Аналогично задаются третья и четвертая дуги.

Матрица смежности вершин графа G или орграфа Г является квадратной, n–го порядка, где n – это число вершин. Обозначим матрицу смежности графа G (орграфа Г) через AdG или Ad («Ad» – это первые буквы слова «adjacency» – смежность»). Каждый элемент mij этой матрицы единице, если вершины vi и v j являются смежными, т. е. инцидентны одному и тому же ребру (дуге). В противном случае элемент mij AdG m Ad равен нулю.

Рассмотрим в качестве примера тот же граф G. Матрица смежности вершин данного графа будет размерности 6 6, так как в графе 6 вершин.

Первое ребро {2, 3} графа G задается смежными вершинам 2 и 3, поэтому в матрице смежности во второй строке, третьем столбце стоит единица.

Второе ребро {2, 4} инцидентно вершинам 2 и 4, поэтому во второй строке, четвертом столбце стоит единица и т. д.

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

ДЕРЕВЬЯ

Цель лабораторной работы состоит в изучении основных алгоритмов на графах.

Задание лабораторной работы № 5 отличается для студентов с четными и нечетными вариантами.

Вариант четный:

Дан простой связный взвешенный граф с помощью весовой матрицы смежности вершин. Найти алгоритмом Прима дерево покрытия минимального веса для данного графа и вес полученного дерева. Дерево покрытия можно задавать весовой матрицей смежности вершин.

Вариант нечетный:

Дан простой взвешенный граф или орграф с помощью весовой матрицы смежности вершин. Найти алгоритмом Дейкстры кратчайший путь между двумя заданными вершинами и цену этого пути. Кратчайший путь можно задавать перечислением его вершин.

Для выполнения лабораторной работы № 5 можно воспользоваться следующим теоретическим материалом.

Граф называется простым, если он не содержит ни петель, ни кратных ребер.

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

Например, в графе G для каждого ребра можно определить его вес Если граф (орграф) – простой и взвешенный, то его можно задать с помощью весовой матрицы смежности вершин. Ее будем обозначать WadG или Wad («W» – это первая буква слова «weight» – «вес»). Эта матрица строится аналогично матрице смежности вершин AdG Ad. Разниm Ad, которые значение на вес ребра ek vi, v j или дуги ek vi, v j.

Например, граф G является простым и взвешенным, поэтому его весовая матрица смежности вершин примет следующий вид:

Вес ребра {2, 3} равен 1, поэтому во второй строке, третьем столбце стоит единица, а вес ребра {2, 4} равен 8, по этой причине во второй строке, четвертом столбце стоит число 8 и т. д.

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

Для графа G можно в качестве примеров указать такие маршруты как 2, 3 или 4, 5, 6, 4.

Если в маршруте начало v0 совпадет с конечной вершиной vk, то маршрут называют замкнутым.

Например, маршрут 4, 5, 6, 4 оказался замкнутым.

Говорят, что вершины vi и v j связаны, если существует маршрут, началом которого является вершина vi, а концом маршрута – вершина v j.

Например, вершины 2 и 3 в графе G являются связанными потому, что для них существует маршрут, началом которого служит вершина 2, а концом – вершина 3, тогда как 1 и 2 – несвязанные вершины.

Граф называют связным, если в нем любые две вершины являются связанными.

Например, граф G не является связным, в нем вершины 1 и 2 несвязанные.

Цепью называется маршрут, в котором все ребра различны.

В рассмотренном нами выше примере оба маршрута 2, 3 и 4, 5, 6, оказались цепями.

Замкнутая цепь называется циклом.

Например, маршрут 4, 5, 6, 4 является циклом в графе G.

Деревом называют простой связный граф без циклов. Его будем обозначать «Т» («Т» – это первая буква слова «tree» – «дерево»).

В качестве примера рассмотрим Если дан граф G V, E, то его подграфом называют такой граф G V, E, что 1) V V, 2) E E и 3) каждое ребро в подграфе инцидентно вершинам только из множества V.

Деревом покрытия данного графа G V, E, называют такой его подграф T V, E, что, во-первых, он является деревом, во-вторых, он содержит все вершины исходного графа.

Весом дерева покрытия связного взвешенного графа называют сумму весов всех ребер, входящих в это дерево.

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

Рассмотрим на примере графа G V, E все шаги алгоритма Прима.

Возьмем произвольную вершину. (Договоримся в дальнейшем выбирать вершину только под первым номером.) Присвоим ей постоянную метку, равную нулю: L(1) 0 («L» – это первая буква слова «label» – «метка»). Вершина считается помеченной, если она получила свою постоянную метку.

Всем еще не помеченным вершинам, но смежным с помеченной на предыдущем шаге вершиной присвоим текущие метки, равные весу ребра, инцидентного данным вершинам.

В нашем примере это l1 2 5. Заметим, что постоянные метки пишут прописной буквой L, а текущие – строчной l. Индекс буквы l означает вершину, помеченную на предыдущем шаге.

Из списка всех текущих меток выберем самую минимальную.

Так как у нас пока всего одна текущая метка l1 2 5, то ее и выбираем.

Затем присвоим вершине, записанной в скобках, постоянную метку, равную текущей метке.

При этом все текущие метки только что помеченной вершины удаляем из списка меток.

Повторяем последовательно шаги 2 и 3 до тех пор, пока все вершины не окажутся помеченными.

Вес искомого дерева покрытия равен сумме всех постоянных меток.

так как она минимальная. Присвоим 3-й вершине постоянную метку L2 3 1. Удалим из списка меток l2 3 1. Снова повторим второй пункт, дополнив список текущей меткой l3 4 9. Выберем минимальную l3 4 9. Затем согласно второму пункту l4 5 7, l4 6 3. Выбираем выбираем минимальную l4 5 7, метим 5-ю вершину L4 5 7, удалив l4 5 7 и l6 5 9. Поскольку все вершины оказались помеченными, мы получили искомое дерево покрытия T V, E. Найдем его вес, суммируя 5 + 1 + 8 + 3 + 7 = 24. Эти же постоянные метки демонстрируют структуру дерева покрытия T Для отыскания во взвешенном графе или орграфе кратчайшего маршрута между заданными вершинами применяют алгоритм Дейкстры.

Ценой маршрута во взвешенном графе называется сумма весов всех ребер, образующих маршрут.

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

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

Текущие метки равны не весу ребра, а сумме веса ребра и постоянной метки, найденной на предыдущем шаге.

Выполняем все действия, аналогичные действиям пункта 3 алгоритма Прима.

Повторяем последовательно шаги 2 и 3 до тех пор, пока не пометим конечную вершину искомого кратчайшего маршрута.

Цена маршрута будет равна постоянной метке конечной вершины.

Кратчайший маршрут восстанавливается в обратном порядке, начиная с метки конечной вершины маршрута. Эта метка покажет вершину, смежную с конечной вершиной. Найдем соответствующую метку, а по ней вершину предыдущего шага. Продолжим аналогичные действия до тех пор, пока не попадем в начальную вершину кратчайшего маршрута.

КОДИРОВАНИЕ

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

Задание лабораторной работы № 6 отличается для студентов с четными и нечетными вариантами.

Вариант четный:

Дан текст на русском языке. Закодировать его алгоритмом Фано, причем кроме зашифрованного текста выписать схему кодирования и указать ее цену.

Вариант нечетный:

Дан текст на русском языке. Закодировать его алгоритмом Хаффмана, причем кроме зашифрованного текста выписать схему кодирования и указать ее цену.

Для выполнения лабораторной работы № 6 необходимо использовать следующий теоретический материал.

алфавитом. Элементы ai A будем называть буквами.

Последовательность букв, т. е. буквы алфавита, записанные друг за другом, назовем словом, его будем обозначать ( a j a j a j ). Количеk ство слов в алфавите А обозначим A.

Говорят, что задано алфавитное кодирование, если каждой букве ai A алфавита А сопоставлено определенное слово i B алфавита В, причем такие слова i B называют элементарными кодами.

Таблица, в которой записаны все буквы ai A и соответствующие им элементарные коды i B, называется схемой алфавитного кодирования, обозначается.

алфавита А можно представить последовательностью элементарных кодов алфавита В следующим образом: j j j (каждой букве a j слова соответствует определенный элементарный код j ), при этом B называют кодом слова A.

Последовательность слов A алфавита А называют текстом на языке A.

Перевод всех слов A данного текста в коды B алфавита В называют кодированием.

Если задан текст на языке A, то можно подсчитать для каждой буквы ai A частоту ее появления в этом тексте. Обозначим ее mi. Будем считать, что все mi 0, другими словами, мы исключим все буквы, не встреa но найти цену схемы кодирования – число здесь M mi – количество всех букв в тексте.

Алгоритм кодирования Фано состоит в следующем.

Расположим встречающиеся в заданном тексте буквы так, чтобы m1 m2 mn 0, т. е. по убыванию частоты их появления в тексте. Каждая буква ai A имеет такой же номер, что и mi – число ее появления в этом тексте, написанном, между прочим, на русском языке. Если буквы имеют одинаковую частоту, то располагаем их по алфавиту русского языка. Для каждой буквы ai A требуется найти элементарный код i B. В алгоритме Фано алфавит B 0,1.

Разобьем отсортированный список всех букв на две группы так, чтобы суммы частот появлений букв каждой из групп были как можно более ний на две группы. Кодам i B, соответствующим буквам из первой группы, приписываем 0. Зато кодам i B, сопоставленным буквам из второй группы, приписываем 1. По тому же принципу каждая из полученных групп снова разбивается на подгруппы, и это разбиение определяет символ, 0 или 1, приписываемый справа к коду i B. Процедура разбиения продолжается до тех пор, пока все множество букв не будет разбито на подгруппы, состоящие только из одной буквы. В результате каждой букве ai A будет соответствовать элементарный код i B, образованный из нулей и единиц.

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

В качестве примера закодируем текст «шла Саша по шоссе и сосала сушку» с помощью алгоритма Фано. Подсчитаем, что буква «ш» встречается 4 раза, «л» – 2 раза, «а» – 5, «с» – 6, «п» – 1, «о» – 3, «е» – 1, «и» – 1, «у» – 2, «к» – 1 раз, пробелов « » – 6 раз. Расположим частоты появления букв по убыванию. Заметим, что номер буквы в списке букв соответствует номеру частоты в упорядоченном по убыванию списке частот, причем буквы с одинаковой частотой располагаются по алфавиту русского языка. Таким образом, имеем mi mi не станет минимальной среди всех разбиений на две группы.

Находим, что сумма первых трех частот 6 6 5 такова, что разность (6 6 5) (4 3 2 2 1 1 1 1) минимальна. Поэтому первые три буквы кодируем пока нулями, а остальные – единицами.

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

Так как разность (4 3) (2 2 1 1 1 1) является минимальной среди всех разбиений, то четвертая и пятая буквы попадут в одну подгруппу, а остальные в другую. Таким образом, коду первой буквы дописываем справа ноль, коду второй и третьей буквы – единицу. Для нижней «половины»:

коду четвертой и пятой буквы дописываем ноль, а остальным – единицу.

Первая «четвертинка» уже не может поделиться, так как содержит всего одну букву. Вторая «четвертинка», очевидно, поделится так, что к коду второй буквы потребуется дописать справа 0, а к коду третьей буквы добавим 1. Аналогично, поделив пополам третью «четвертинку», мы получим, что код четвертой буквы удлинится на 0, а код пятой буквы – на 1. Заметим, что разность (2 2) (1 1 1 1) минимальна среди всех разбиений последней «четвертинки» на подгруппы, следовательно, к кодам шестой и седьмой буквы допишем ноль, а к остальным – единицу. Имеем На четвертом шаге кроме последних двух «восьмушек» никакие другие не могут поделиться, поэтому разобьем их пополам и получим Произведем последний раз разбиение на подгруппы. Будем иметь Номер буквы и Буква Частота появления Элементарный код Мы получили схему кодирования Цена этой схемы кодирования P F Цена в 3,2 единицы означает, что для каждой буквы текста потребуется примерно три позиции в закодированном сообщении. Так как букв в заданном тексте 32, то всего закодированный текст займет примерно 102 позиции (32 3,2=102,4). Сам закодированный текст будет выглядеть следующим образом:

« 101010100111100011000101101100111101101».

Алгоритм Хаффмана опишем следующим образом. Как и в алгоритме Фано, расположим встречающиеся в заданном тексте буквы по убыванию частоты их появления в тексте, написанном на русском языке. Если буквы имеют одинаковую частоту, то располагаем их по алфавиту русского языка. Для каждой буквы ai A требуется найти элементарный код i B. В алгоритме Хаффмана алфавит B 0,1.

На первом этапе алгоритма Хаффмана в списке частот m1 m2 mn сложим последние две частоты mn1 mn. Полученную сумму mn1 mn вставим в упорядоченный список частот от m1 до mn так, чтобы он опять стал убывающим, причем мы должны выделить и запомнить номер суммы mn1 mn в новом списке частот. Договоримся, что пока частоты mi будут больше, чем сумма mn1 mn, номера i этих частот в новом списке сохраняются. Как только сумма mn1 mn m j, так сразу же запоминаем номер j потому, что в новом списке сумма mn1 mn будет иметь именно этот номер. Все остальные частоты m j mn1 mn получат в новом списке номера на единицу больше, чем в старом. Продолжаем процедуру суммирования двух последних частот списка по циклу до тех пор, пока весь список не сожмется в одно число На втором этапе алгоритма Хаффмана вводим два элементарных кода 1 0 и 2 1, соответствующие предпоследнему списку частот (вернее двум буквам, появляющимся в тексте с такими частотами). Если n 2, то схема найдена и алгоритм завершен. Если n 2, то код буквы с выделенным номером j временно исключается из списка кодов путем сдвига вверх кодов букв с номерами, большими j, а затем в конец нового списка добавляется пара кодов, полученных из кода буквы с номером j удлинением его на 0 и 1 соответственно. Далее продолжаем по циклу до тех пор, пока каждой букве ai A текста не сопоставим ее элементарный код Рассмотрим пример. Закодируем текст «шла Саша по шоссе и сосала сушку» с помощью алгоритма Хаффмана. Воспользуемся таблицей предыдущего примера На первом этапе суммируем две последних частоты 1 1 и составляем новый список частот, вставляя сумму, равную двум, на шестое место и запоминая этот номер 6.

Номер бук- Буква Частота появления Новый список частот Продолжаем этот процесс по циклу до тех пор, пока не получим сумму всех частот, равную 32.

Номер Частота Нобуквы и появле- вый частоты ния бу- спив спи- квы в сок На втором этапе алгоритма Хаффмана вводим два элементарных кода 1 0 и 2 1 для первой и второй буквы соответственно. Выделим код под номером один, так как в соответствующей таблице частот первая частота 19 также выделена.

Исключим временно выделенный код 0 из списка кодов и поднимем вверх код 1, а затем в конец нового списка добавим пару кодов, полученных из кода 0 добавлением к нему 0 и 1 соответственно. Получим Первый код 1 мы выделили, так как соответствующая ему частота 13 в списке частот также выделена. Продолжая по аналогии процесс формирования кодов по соответствующим спискам частот, мы получим таблицу Имеем схему кодирования, полученную алгоритмом Хаффмана Цена этой схемы кодирования такая же, как и у схемы, полученной с помощью алгоритма Фано. Но закодированный текст будет совершенно другим:

« 001010000010110001110000111100010100111».

1. Новиков Ф. А. Дискретная математика для программистов : учеб. пособие для вузов / Ф. А. Новиков. – 2-е изд. – СПб. : Питер, 2005. – 368 с.

2. Белоусов А. И. Дискретная математика : учеб. для втузов / А. И. Белоусов, С. Б. Ткачев ; под ред. В. С. Зарубина, А. П. Крищенко. – 2-е изд., стер. – М. : Изд-во МГТУ им. Н. Э. Баумана, 2002. – 744 с.

3. Андерсон Д. А. Дискретная математика и комбинаторика / Д. А. Андерсон. – М. : Издательский дом «Вильямс», 2003. – 960 с.

4. Сафьянова Е. Н. Дискретная математика : учеб. пособие для вузов : в ч. / Е. Н. Сафьянова. – Томск : Изд-во ТУСУР, 2000. – Ч. 1. – 106 с.

5. Сафьянова Е. Н. Дискретная математика : учеб. пособие для вузов : в ч. / Е. Н. Сафьянова. – Томск : Изд-во ТУСУР, 2000. – Ч. 2. – 99 с.

6. Элементы теории множеств : метод. указания для студентов, изучающих курс «Дискретная математика» / сост. Т. М. Попова. – Хабаровск :

Изд-во ХГТУ, 2002. – 15 с.

7. Акимов О. Е. Дискретная математика: Логика, группы, графы / О. Е.

Акимов. – М. : Лаборатория Базовых Знаний, 2003. – 376 с.

8. Романовский И. В. Дискретный анализ : учеб. пособие по прикладной математике и информатике / И. В. Романовский. – СПб. : Невский диалект, 2001. – 240 с.

Вводные положения

Лабораторная работа № 1. Системы счисления

Лабораторная работа № 2. Диаграммы Эйлера – Венна и законы теории множеств…

Лабораторная работа № 3. Виды бинарных отношений

Лабораторная работа № 4. Способы задания графов

Лабораторная работа № 5. Деревья

Лабораторная работа № 6. Кодирование

Методические указания к выполнению лабораторных работ Издательство Тихоокеанского государственного университета.



 
Похожие работы:

«Методические указания к выполнению практикума по курсу Информатика. Информационные системы в экономике Содержание Введение Раздел 1. Моделирование бизнес-процессов предприятия средствами BPwin ПРИЛОЖЕНИЕ к разделу 1. Пример создания IDEF0-модели средствами BPwin для компании МЕД (модели бизнес-процесса продаж) Раздел 2. Реализация бизнес-процессов предприятия средствами Microsoft Dynamics Axapta Раздел 3. Реализация бизнес-процессов предприятия средствами Microsoft Dynamics Nav Раздел 4....»

«Бюллетень новых поступлений за январь 2014 года 1 Ш 141 Практикум по современному русскому языку. Морфология: П 691 учебное пособие для вузов / Л. И. Рахманова, В. Н. Суздальцева, В. И. Кононова и др. - Москва: Аспект Пресс, 2012. - 103с. - Авт. указ. на обороте тит.л. - ISBN 978-5-7567-0592-8 (в обл.) : 239-00р. 2 В 314 Иродов Игорь Евгеньевич. И 831 Квантовая физика. Основные законы: учебное пособие для вузов / Иродов Игорь Евгеньевич. - 3-е изд., стер. - Москва: БИНОМ.Лаборатория знаний,...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ Высшего профессионального образования Тверской государственный университет УТВЕРЖДАЮ Декан факультета ПМиК _А.В.Язенин 2009 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине ЭКОНОМИЧЕСКАЯ ТЕОРИЯ для студентов 1 курса очной формы обучения направления 080801.62 – Прикладная информатика Обсуждено на заседании кафедры Составитель: экономики Д.э.н., профессор 5 января 2012г. Протокол № 5 _Горшенина Е.В. Зав. кафедрой Горшенина Е.В. Тверь...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Томский государственный университет систем управления и радиоэлектроники (ТУСУР) Кафедра автоматизированных систем управления СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ Методические указания по самостоятельной и индивидуальной работе студентов всех форм обучения для направления подготовки: 230100.62 Информатика и вычислительная техника Томск-2011 2 Горитов...»

«УДК 378.147(07) ББК 74.580.253я73 С89 Электронный учебно-методический комплекс по дисциплине Информационнокоммуникационные технологии в образовании подготовлен в рамках инновационной образовательной программы Информатизация и автоматизированные системы управления, реализованной в ФГОУ ВПО СФУ в 2007 г. Рецензенты: Красноярский краевой фонд науки; Экспертная комиссия СФУ по подготовке учебно-методических комплексов дисциплин С89 Информационно-коммуникационные технологии в образовании. Версия 1.0...»

«СОДЕРЖАНИЕ 1. ЛАБОРАТОРНЫЙ ПРАКТИКУМ ИЗМЕРНИЕ ПАРАМЕТРОВ ПЕ- 2 РЕДАЧИ ЭЛЕКТРИЧЕСКИХ КАБЕЛЕЙ ЛАБОРАТОРНАЯ РАБОТА № 1 4 1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 4 2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ РАБОТЫ 9 2.1. УСТРОЙСТВО ПРИБОРА П-321 9 2.2. ПОДГОТОВКА ПРИБОРА П – 321 К РАБОТЕ 13 2.3. ПОРЯДОК РАБОТЫ С ПРИБОРОМ 14 3. ОПИСАНИЕ ЛАБОРАТОРНОГО МАКЕТА 14 4. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ 15 5. СОДЕРЖАНИЕ ОТЧЕТА 15 6. КОНТРОЛЬНЫЕ ВОПРОСЫ ЛАБОРАТОРНАЯ РАБОТА N2 1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФГБОУ ВПО СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ИНФОРМАЦИИ Методические указания к выполнению практических работ дисциплины Вычислительные системы для направления (ий) подготовки (специальности (ей)) 230100 Информатика и вычислительная техника Квалификация (степень) выпускника магистр Разработчик(и) программы: Шепилова Е.В. Владикавказ 2013 Оглавление Практическая...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ИНФОРМАТИКИ М.И. БАРАБАНОВА МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ПРОВЕДЕНИЯ ЛАБОРАТОРНЫХ РАБОТ ПО ТЕМЕ Создание презентаций средствами PowerPoint ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ 2004 ПРЕЗЕНТАЦИИ СОДЕРЖАНИЕ СОДЕРЖАНИЕ ВВЕДЕНИЕ КЛАССИФИКАЦИЯ ПРЕЗЕНТАЦИЙ СИСТЕМНЫЕ ТРЕБОВАНИЯ ДЛЯ MS POWERPOINT 2002 ЗАПУСК MICROSOFT POWERPOINT СОЗДАНИЕ...»

«Министерство образования и науки Российской Федерации Владивостокский государственный университет экономики и сервиса _ БАЗЫ ДАННЫХ Учебная программа курса по специальности 351400 Прикладная информатика в экономике Владивосток Издательство ВГУЭС 2004 Учебная программа по дисциплине Базы данных разработана для студентов специальности Прикладная информатика в экономике, изучающих базы данных в качестве дисциплины общего профессионального цикла. Содержит организационно-методические указания и...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра математического анализа и моделирования УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ СИСТЕМ Основной образовательной программы по направлению подготовки 010500.62 – Прикладная математика и информатика Благовещенск 2012 г. УМКД разработан канд. физ.-мат. наук, доцентом...»

«ИНФОРМАТИКА •ИЗДАТЕЛЬСТВО ТГТУ• ББК 381я73-5 УДК 621ю391(075) Г15 Утверждено Редакционно-издательским советом университета Р е ц е н з е н т ы: Кандидат экономических наук, доцент В. Л. Пархоменко Кандидат педагогических наук, доцент Е. В. Бурцева Информатика: Программа, методические указания и контрольные задания / Сост.: И. В. ГалыГ15 гина, Л. В. Галыгина. Тамбов: Изд-во Тамб. гос. техн. ун-та, 2004. 48 с. Методическое пособие адресовано студентам 1 и 2 курсов заочного отделения...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФГБОУ ВПО СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) Кафедра автоматизированной обработки информации Методические указания к лабораторным работам дисциплины: Теория принятия решений для направления подготовки: 230100 – Информатика и вычислительная техника профиль: Автоматизированные системы обработки информации и управления квалификация (степень) выпускника: бакалавр Составитель: асс. Гречаный С.В....»

«МИНИСТЕРСТВО КУЛЬТУРЫ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КУЛЬТУРЫ И ИСКУССТВ МЕНЕДЖЕР ИНФОРМАЦИОННЫХ РЕСУРСОВ Учебно-методическое пособие Под общей редакцией профессора В.К. Клюева Рекомендовано Учебно-методическим объединением по образованию в области народной художественной культуры, социально-культурной деятельности и информационных ресурсов в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 071201 –...»

«ФЕДЕРАЛЬНАЯ СЛУЖБА ПО НАДЗОРУ В СФЕРЕ ЗАЩИТЫ ПРАВ ПОТРЕБИТЕЛЕЙ И БЛАГОПОЛУЧИЯ ЧЕЛОВЕКА 2.1.9. СОСТОЯНИЕ ЗДОРОВЬЯ НАСЕЛЕНИЯ В СВЯЗИ С СОСТОЯНИЕМ ОКРУЖАЮЩЕЙ ПРИРОДНОЙ СРЕДЫ И УСЛОВИЯМИ ПРОЖИВАНИЯ НАСЕЛЕНИЯ СОЦИАЛЬНО - ГИГИЕНИЧЕСКИЙ МОНИТОРИНГ. ИНВАЛИДНОСТЬ ДЕТЕЙ. СБОР, ОБРАБОТКА И АНАЛИЗ ПОКАЗАТЕЛЕЙ. Методические рекомендации ФЦ/3718 от 01.12.2004 Москва 2004 2.1.9. СОСТОЯНИЕ ЗДОРОВЬЯ НАСЕЛЕНИЯ В СВЯЗИ С СОСТОЯНИЕМ ОКРУЖАЮЩЕЙ ПРИРОДНОЙ СРЕДЫ И УСЛОВИЯМИ ПРОЖИВАНИЯ НАСЕЛЕНИЯ СОЦИАЛЬНО -...»

«ИНФОРМАТИКА Пособие для учителя 4 класс Часть 1. Занятия в первой четверти Допущено Департаментом общего среднего образования Министерства образования Российской Федерации Москва Просвещение Институт новых технологий образования 2004 В подготовке методического пособия принимали участие: В. И. Беликов, Е. С. Кузнецова, А. А. Муранов, С. А. Трактуева Семёнов А. Л. Информатика: Пособие для учителя : 4 кл. / А. Л. Семёнов, Т. А. Рудченко. – М.: Просвещение: Институт новых технологий образования,...»

«Т.Н. Гартман, Д.В. Клушин, В.В. Васильев, Е.Н. Павличева ВВЕДЕНИЕ В СИСТЕМЫ ПРИКЛАДНОЙ ИНФОРМАТИКИ ХИМИЧЕСКИХ ПРЕДПРИЯТИЙ Учебное пособие Москва 2006 ОГЛАВЛЕНИЕ Список сокращений Предисловие 1. Автоматизированные информационные системы (АИС). Базы и банки данных.6 1.1. Ресурсы автоматизированных информационных систем 2. Системы автоматизированного проектирования (САПР) 3. Автоматизированные системы научных исследований (АСНИ) 4. Автоматизированные системы управления (АСУ) 4.1. Системы...»

«Т.А. Санькова СУБД MICROSOFT ACCESS ДЛЯ НАЧИНАЮЩИХ 1 Министерство образования Российской Федерации Сибирская государственная автомобильно-дорожная академия (СибАДИ) Т.А. Санькова СУБД MICROSOFT ACCESS ДЛЯ НАЧИНАЮЩИХ Учебно-методическое пособие Омск Издательство СибАДИ 2003 2 ГЛАВА I ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОЕКТИРОВАНИЯ БАЗ ДАННЫХ Понятие базы данных База данных – совокупность данных, организованных по определенным правилам, предусматривающим общие принципы описания, хранения и манипулирования...»

«министерство образования российской федерации московский государственный индустриальный университет факультет довузовского образования Составители: Е.А. Роганов, Н.А. Роганова Методические указания для подготовки к вступительному экзамену по дисциплине Информатика Москва 2004 Методические указания для подготовки к вступительному экза М.: МГИУ, 2004. 36 с. мену по дисциплине Информатика Методические указания предназначены для абитуриентов, поступаю щих в Московский государственный индустриальный...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САНКТ ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ А. Г. Варжапетян ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ НА GPSS/H Учебное пособие Санкт Петербург 2007 УДК 519.682 ББК 22.18 В18 Рецензенты: кафедра морских информационных технологий Российского государственного гидрометеорологического университета; доктор технических наук, профессор кафедры вычислительных...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФГБОУ ВПО СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) Кафедра автоматизированной обработки информации Методические указания к практическим работам дисциплины: Надежность, эргономика и качество АСОиУ для направления подготовки: 230100 – Информатика и вычислительная техника профиль: Автоматизированные системы обработки информации и управления квалификация (степень) выпускника: бакалавр Составитель: к.т.н....»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.