Применение теории графов в информатике 2

Применение теории графов в информатике

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

• посмотреть текст работы

• скачать работу можно здесь

• полная информация о работе

• весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

КАФЕДРА МАТЕМАТИКИ И ИНФОРМАТИКИ

по дисциплине «Информатика»

на тему: «Применение теории графов в информатике»

Содержание

1. Теоретическая часть

1.1 История возникновения теории графов

1.2 Основные понятия теории графов

1.3 Основные теоремы теории графов

1.4 Способы предоставления графов в компьютере

1.4.1 Требования к предоставлению графов

1.4.2 Матрица смежности

1.4.3 Матрица инциденций

1.4.4 Списки смежности

1.5 Обзор задач теории графов

1.6 Программа определения кратчайшего пути в графах

1.6.1 Язык программирования Delphi

1.6.2 Программа «Определения кратчайшего пути в графе»

2. Практическая часть

2.1 Общая характеристика задачи

2.2 Описание алгоритма решения задачи

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.

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

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

1. Теоретическая часть

3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно — объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Рис. 3. Схематичное изображение задачи о четырех красках

1) Графом G(V,E) называется совокупность двух множеств — непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E — множество ребер).

2) Ориентированным называется граф, в котором — множество упорядоченных пар вершин вида (x,y), где x называется началом, а y — концом дуги. Дугу (x, y) часто записывают как . Говорят также, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x.

3) Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей, а граф называется графом с петлями (или псевдографом).

4) Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

5) Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются гипердугами, а граф называется гиперграфом.

6) Если задана функция F : V > M и/или F : E > M, то множество M называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным.

7) Подграфом называется граф G?(V?,E?), где и/или .

a) Если V? = V, то G? называется остовным подграфом G.

b) Если , то граф G? называется собственным подграфом графа G.

c) Подграф G?(V?,E?) называется правильным подграфом графа G(V,E), если G? содержит все возможные рёбра G.

Степень (валентность) вершины — это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).

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

a) Если , то маршрут замкнут, иначе открыт.

b) Если все ребра различны, то маршрут называется цепью.

c) Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.

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

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

f) Граф без циклов называется ациклическим.

g) Для орграфов цепь называется путем, а цикл — контуром.

Рис. 4. Маршруты, цепи, циклы

В графе, диаграмма которого приведена на рис.4:

10) Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом.

11) Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом.

12) Деревом называется связный граф без циклов.

13) Остовом называется дерево, содержащее все вершины графа.

14) Паросочетанием называется множество ребер, в котором никакие два не смежны.

15) Паросочетание называется максимальным, если никакое его надмножество не является независимым.

16) Две вершины в графе связаны, если существует соединяющая их простая цепь.

17) Граф, в котором все вершины связаны, называется связным.

18) Граф, состоящий только из изолированных вершин, называется вполне несвязным.

19) Длиной маршрута называется количество ребер в нем (с повторениями).

20) Расстоянием между вершинами u и v называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической.

21) Диаметром графа G называется длина длиннейшей геодезической.

22) Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от вершины v до других вершин графа G.

23) Радиусом графа G называется наименьший из эксцентриситетов вершин.

24) Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа.

25) Множество центральных вершин называется центром графа.

Рис. 5 Эксцентриситеты вершин и центры графов (выделены)

Применение теории графов в информатике

Вы будете перенаправлены на Автор24

Применение теории графов в информатике — это использование методов определения отношений в наборе элементов.

Введение

Одним из наиболее объёмных разделов в дискретной математике считается теория графов, которая широко используется для решения различных проблем в самых разных сферах жизнедеятельности людей, в том числе и в информатике. Теория графов на научной базе занимается изучением их особенностей, параметров, характеристик и свойств. Граф является множеством точек и линий, которые соединяют этот набор точек. Основоположником теории графов считается Леонард Эйлер, решивший известную в его бытность задачу Кёнигсбергских мостах.

Теория графов

Формирование графов требуется для определения взаимных связей элементов внутри множеств. Приведём конкретный пример. Существует множество $А = <а_1, а_2, . а_n>$, обозначающее некоторое людское сообщество, где все его компоненты изображаются в виде точек. Есть также множество $В = $, которое отображает связи между людьми, то есть это линии разной конфигурации. В множестве A$А заданы взаимные связи между людьми этого множества. Требуется выстроить граф, который будет отображать все точки и связи между ними. Связи (линии) проходят между теми парами людей, которые знакомы друг с другом. Естественно, число знакомств у каждого человека будет разным, и, вероятно, имеются такие люди, у которых вообще нет ни одного знакомого человека. Они должны обозначаться точками, от которых не отходят соединительные линии. В результате будет сформирован такой вид графа: А заданы взаимные связи между людьми этого множества. Требуется выстроить граф, который будет отображать все точки и связи между ними. Связи (линии) проходят между теми парами людей, которые знакомы друг с другом. Естественно, число знакомств у каждого человека будет разным, и, вероятно, имеются такие люди, у которых вообще нет ни одного знакомого человека. Они должны обозначаться точками, от которых не отходят соединительные линии. В результате будет сформирован такой вид графа:

Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ

Точки графа являются его вершинами, а соединяющие их линии называются рёбрами графа.

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

Готовые работы на аналогичную тему

Среди существующих строгих математических формулировок следует подчеркнуть такие определения графа:

1. Графом является систематизированный комплекс объектов разной физической природы, которые считаются вершинами графа, и связей, называемых рёбрами, которые связывают некоторые пары этих объектов.
2. Существует заполненное множество вершин $V$, причём элементы $v$, которые принадлежат множеству $V$, считаются его вершинами. Графом $G = G(V) $, который имеет множество вершин $V$, может считаться комплект пар типа $е = (а, b) $, где $а, b$ являются элементами множества $V$, и они определяют соединённые вершины. Каждая пара $е = (а, b$) является ребром графа. Множество $U$ определяется как множество рёбер $е$ графа, а вершины $а$ и $b$ будут конечными точками ребра $е$.

Графы как структурированные данные

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

• Начальные компоненты.
• Выработанные компоненты.
• Компоненты, являющиеся аналогами (подобные).

Граф — это нелинейная структура данных. Сам термин граф произошёл из греческого языка и переводится как «пишу». Таким образом, главным назначением графа является описание отношений составляющих его компонентов.

Главные понятия теории графов

Среди главных понятий теории графов следует выделить термин «инцидентность», на котором базируются остальные термины. Две вершины графа являются инцидентными, когда они соединены ребром. Когда в какой-то вершине берёт начало или оканчивается ребро, то это ребро и вершина являются инцидентными. Различные виды графов могут отличаться друг от друга по типу вершин и (или) рёбер, входящих в состав графов. Графы, у которых рёбра имеют направление (направленные рёбра), называются ориентированными. В противном случае граф считается неориентированным.

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

Курсовая работа по дисциплине «Информатика» на тему: «Применение теории графов в информатике» (стр. 2 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4

Рис. 5 Эксцентриситеты вершин и центры графов (выделены)

1.3 Основные теоремы теории графов

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

Теорема 1. Удвоенная сумма степеней вершин любого графа равна числу его ребер. [1, стр. 66]

Доказательство. Пусть А1, А2, А3, . An — вершины данного графа, a p(A1), p(А2), . p(An) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A1)+p(А2)+ . +p(An)=0,5N, или 2(p(A1)+p(А2)+ . +p(An))=N, где N — число ребер.

Теорема 2. Число нечетных вершин любого графа четно.

Доказательство. Пусть a1, a2, a3, …, ak — это степени четных вершин графа, а b1, b2, b3, …, bm — степени нечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bm ровно в два раза превышает число ребер графа. Сумма a1+a2+a3+…+ak четная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать.

Следствие 1. Нечетное число знакомых в любой компании всегда четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное число ребер, четно.

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

Теорема 3. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.

Доказательство. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, . (n-1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0 и (n-1). Это значит, что из n вершин найдутся две, имеющие одинаковые степени.

Теорема 4. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

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

Теорема 5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

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

Теорема 6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.

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

Доказательство этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как использована при этом теорема 3.6). Для доказательства к исходному графу присоединяем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл Ш. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ.

На этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы 7.

Теорема 8. Если данный граф является связным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу.

Теорема 9. Различных деревьев с n перенумерованными вершинами можно построить nn-2.

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревья используются не только математиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).

Теорема 10. Полный граф с пятью вершинами не является плоским.

Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В — число вершин плоского графа, Р — число его ребер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого.

Эту формулу можно доказать методом математической индукции. Это доказательство мы опускаем. Заметим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с другом. Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через ц1 обозначить число таких граней, то ц2=0. Далее рассуждаем от противного, а именно: предположим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.

Это число можно представить в виде суммы: Г=ц1+ц2+ц3+…, где ц3 – число граней, ограниченных тремя ребрами, ц4 — число граней, ограниченных четырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р=20=3ц3+4ц4+. . Умножив равенство Г=7=ц3+ ц4 + ц5 + … на три, получим ЗГ=21=3( ц3 + ц4 + ц5 + …).

Применение теории графов в информатике

Автор работы: Пользователь скрыл имя, 03 Марта 2013 в 12:50, курсовая работа

Краткое описание

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

Вложенные файлы: 1 файл

Применение теории графов в информатике.doc

Это число можно представить в виде суммы: Г=φ₁+φ₂+φ₃+…, где φ₃ – число граней, ограниченных тремя ребрами, φ₄ — число граней, ограниченных четырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р=20=3φ₃+4φ₄+. . Умножив равенство Г=7=φ₃+ φ₄ + φ₅ + … на три, получим ЗГ=21=3( φ₃ + φ₄ + φ₅ + …).

Для матрицы смежности n(p,q) = O(p 2 ).

Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.

1.4.3 Матрица инциденций

Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа

Для матрицы инциденций n(p,q) = O(pq).

1.4.4 Списки смежности

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

N : record v : 1..p; n :↑ N end record,

называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).

1.4.5 Массив дуг

Представление графа с помощью массива структур

E : array [1..q] of record b,e : 1..p end record,

отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).

1.5 Обзор задач теории графов

Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.[4, стр. 12-15]

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

Далее перечислим некоторые типовые задачи теории графов и их приложения:

— Задача о кратчайшей цепи

· составление расписания движения транспортных средств

· размещение пунктов скорой помощи

· размещение телефонных станций

— Задача о максимальном потоке

· анализ пропускной способности коммуникационной сети

· организация движения в динамической сети

· оптимальный подбор интенсивностей выполнения работ

· синтез двухполюсной сети с заданной структурной надежностью

· задача о распределении работ

— Задача об упаковках и покрытиях

· оптимизация структуры ПЗУ

· размещение диспетчерских пунктов городской транспортной сети

— Раскраска в графах

· распределение памяти в ЭВМ

· проектирование сетей телевизионного вещания

— Связность графов и сетей

· проектирование кратчайшей коммуникационной сети

· синтез структурно-надежной сети циркуляционной связи

· анализ надежности стохастических сетей связи

— Изоморфизм графов и сетей

· структурный синтез линейных избирательных цепей

· автоматизация контроля при проектировании БИС

— Изоморфное вхождение и пересечение графов

· локализация неисправности с помощью алгоритмов поиска МИПГ

· покрытие схемы заданным набором типовых подсхем

· конструктивное перечисление структурных изомеров для производных органических соединений

· синтез тестов цифровых устройств

Заключение

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

2. Практическая часть

2.1. Общая характеристика задачи

Расмотрим следующую задачу:

1. Построить таблицы по приведенным данным о доходах членов семьи (табл. 1, 2) и о расходах семьи (табл. 3) за квартал.

Доходы Чижовой М. А. за 1 квартал 2006 г., руб.

Сумма дохода в месяц

Таблица 1 Доходы Чижовой М. А. за квартал

Доходы Чижова А. С. за 1 квартал 2006 г., руб.

Сумма дохода в месяц

Таблица 2 Доходы Чижова А. С. за квартал

Расходы семьи Чижовых за 1 квартал 2006 г., руб.

Оплата телефонных счетов

Расходы на питание

Суммарный расход в месяц

Таблица 3 Расходы семьи Чижовых за квартал

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

Доходы семьи Чижовых за 1 квартал 2006 г., руб.

Сумма дохода в месяц

Таблица 4 Доходы семьи Чижовых за квартал

Бюджет семьи Чижовых за 1 квартал 2006 г., руб.

Суммарный доход в месяц

Суммарный расход в месяц

Таблица 5 Бюджет семьи Чижовых за квартал

1. По данным о бюджете семьи на квартал (табл. 5) построить гистограмму.

2.2. Описание алгоритма решения задачи

1. Запустить табличный процессор MS Excel.
2. Создать книгу с именем «Бюджет».
3. Лист 1 переименовать в лист с названием Доходы.
4. На рабочем листе Доходы MS Excel создать таблицы «Доходы Чижовой М. А. за квартал» и «Доходы Чижова А. С. за квартал».
5. Заполнить таблицы доходов исходными данными (рис. 2.1).

Рисунок 2. 1 Расположение таблиц доходов на рабочем листе Доходы MS Excel

1. Лист 2 переименовать в лист с названием Расходы.
2. На рабочем листе Расходы MS Excel создать таблицу расходов семьи Чижовых за квартал.
3. Заполнить таблицу расходов исходными данными (рис. 2.2)

Рисунок 2. 2 Расположение таблиц расходов на рабочем листе Расходы MS Excel

1. Заполнить строку Сумма дохода в месяц таблиц «Доходы Чижовой М. А. за 1 квартал 2006 г., руб.» и «Доходы Чижова А. С. за 1 квартал 2006 г., руб.», находящихся на листе Доходы следующим образом:

Занести в ячейку С6 формулу:

Размножить введенную в ячейку С6 формулу для остальных ячеек (с С4 по F4 и с С12 по F12) данных строк.

Таким образом будет автоматически подсчитаны суммы дохода в месяц (рис. 2.3).

Рисунок 2. 3 Автоматический подсчет суммы доходов в месяц

1. Заполнить строку Суммарный расход в месяц таблицы «Расходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Расходы следующим образом:

Занести в ячейку С10 формулу:

Размножить введенную в ячейку С10 формулу для остальных ячеек (с С10 по F10) данной строки.

Таким образом будет автоматически подсчитана сумма расхода в месяц (рис. 2.4).

Рисунок 2. 4 Автоматический подсчет суммы расходов в месяц

1. Лист 3 переименовать в лист с названием Итоги.
2. На рабочем листе Итоги MS Excel создать таблицу «Доходы семьи Чижовых за 1 квартал 2006 г., руб.»
3. Заполнить строки Зарплата, Прочие поступления, Сумма дохода в месяц таблицы «Доходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

Занести в ячейку С4 формулу:

Размножить введенную в ячейку С4 формулу для остальных ячеек (с С4 по F6) данной таблицы.

Таким образом будут автоматически подсчитана сумма дохода в месяц (рис. 2.5).

Рисунок 2. 5 Автоматический подсчет суммы доходов в месяц

1. На рабочем листе Итоги MS Excel создать таблицу «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.»
2. Заполнить строку Суммарный доход в месяц таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

Занести в ячейку С11 формулу:

Размножить введенную в ячейку С11 формулу для остальных ячеек (с С11 по F11) данной таблицы.

1. Заполнить строку Суммарный расход в месяц таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

Занести в ячейку С12 формулу:

Размножить введенную в ячейку С12 формулу для остальных ячеек (с С12 по F12) данной таблицы.

1. Заполнить строку Остаток таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

Занести в ячейку С13 формулу:

Размножить введенную в ячейку С13 формулу для остальных ячеек (с С13 по F13) данной таблицы.

Таким образом будет заполнена таблица «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.» (рис. 2.6)

Учебный проект: Его высочество граф математический/Вики-статья Применение теории графов в науке и технике

Применение информационных технологий в науке и технике

Содержание

• 1 Гипотеза:
• 2 Цели:
• 3 Из истории развития информационных технологий
• 4 Применение графов в информатике, химии, биологии, теории массового облуживания, экономике
  • 4.1 Влияние информационных технологий на развитие общества
  • 4.2 Классификация информационных технологий
  • 4.3 Графы в биологии
  • 4.4 Графы в теории массового обслуживания
  • 4.5 Графы в математике
• 5 Применение графов в других областях
• 6 Выводы
• 7 Ресурсы

Гипотеза: [ править ]

В жизни современного общества информационные технологии находят широкое применение.

Цели: [ править ]

1.Изучить применение графов в:

• информатике;
• химии;
• биологии;
• теории массового обслуживания;
• математике.

2.Выяснить, в каких еще областях применяется теория графов.

Из истории развития информационных технологий [ править ]

На ранних этапах истории для синхронизации выполняемых действие человеку потребовались кодированные сигналы общения. Человеческий мозг решил эту задачу без искусственно созданных инструментов: развилась человеческая речь. Речь являлась и первым носителем знаний. Знания накапливались и передавались от поколения к поколению в виде устных рассказов.Природные возможности человека по накоплению и передаче знаний получило первую технологическую поддержку с созданием письменности. Процесс совершенствования носителей информации еще продолжается: камень — кость — глина — папирус — шелк — бумага магнитные и оптические носители — кремний — . Письменность стала первым историческим этапом информационной технологии. Второй этап информационной технологии — возникновение книгопечатания. Оно стимулировало развитие наук, ускоряла темпы накопления профессиональных знаний. Знания, овеществленные через технологии в станки, машины, новые технологии, становились источниками новых идей. Т. О. Цикл: знания — наука — общественное производство — знания замкнулся. Спираль технологической цивилизации начала раскручиваться с бешеной скоростью. Книгопечатание создало информационные предпосылки роста производительных сил. Но информационная революция связанна с созданием ЭВМ в конце 40-х годов. С этого же времени начинается эра развития информационных технологии. Весьма важным свойством информационной технологии является то, что для нее информация не только продукт, но и исходное сырье. Электронное моделирование реального мира на ЭВМ требует обработки существенно большого объема информации, чем содержит конечный результат. В развитии информационной технологии можно выделить этапы. Каждый этап характеризуется определенным признаком. 1.Начальный этап развития ИТ (1950-1960-е годы) характеризуется тем, что в основе взаимодействия человека и ЭВМ лежат машинные языки. ЭВМ доступна только профессионалам 2.Следующий этап (1960-1970-е годы) характеризуются созданием операционных систем. Ведется обработка нескольких заданий, формулируемых разными пользователями; основная цель — наибольшая загрузка машинных ресурсов. 3.Третий этап (1970-1980-е годы) характеризуется изменением критерия эффективности обработки данных, основными стали человеческие ресурсы по разработке и сопровождению программного обеспечения. К этому этапу относятся распространение мини- ЭВМ Осуществляется интерактивный режим взаимодействия нескольких пользователей 4.Четвертый этап (1980-1990-е годы) новый качественный скачек технологии разработки программного обеспечения. Центр тяжести технологических решений переносятся на создания средств взаимодействия пользователей с ЭВМ при создании программного продукта. Ключевое звено новой информационной технологии — представление и обработка знаний. Создаются базы знаний, экспертные системы. Тотальное распространение персональных ЭВМ.

Применение графов в информатике, химии, биологии, теории массового облуживания, экономике [ править ]

Влияние информационных технологий на развитие общества [ править ]

Каждая смена поколений средств информационной технологии требует переобучения и радикальной перестройки мышления специалистов и пользователей, смена оборудования и создания более массовой вычислительной техники. ИТ, как передовая область науки и техники определяет ритм времени технического развития всего общества. Соответственно ИТ влияет на экономику, выводя ее в сторону наукоемкости, при этом ИТ определяет трудосберегающий характер развития общества, так как ИТ берет на себя управление многими видами работ и технологических операций. ИТ влияет и на экологию. Она — средство создания искусственного мира, поэтому оказывает экологическое давление на естественную среду. Главная опасность этого — сужение многообразия форм жизни. Примером влияния ИТ может служить влияние ЭВМ на экологию человека. Но ИТ, с другой стороны — это возможный путь спасения экологического равновесия природы. Формирование информационной структуры техносферы позволит повысить эффективность и безопасность технологических производств. Мы обсуждали ИТ сточки зрения понятия «технология». Теперь обсудим ИТ с точки зрения информации. Термин «информация» происходит от латинского «informatio» — разъяснение, изложение, осведомленность. Понятие информации, должно быть, связана с определенным объектом, свойство которого она отражает. Информация относительно независима от ее носителя, так как возможны ее преобразования и передача по различным физическим средам разными физическими сигналами. При этом не важно содержание информации.

Классификация информационных технологий [ править ]

Основная классификация информационных технологий, это классификация, по технологии обработки: •Технологии обработки текстовой информации (текстовые редакторы, текстовые процессоры). •Технологии обработки числовой информации (табличные процессоры). •Технологии обработки графической информации (Графические редакторы, программы обработки векторной графики). •Технологии создания и обработки базы данных (системы управления базами данных). Все базовые информационные технологии делятся на три группы: •Информационные системы. •Офисные технологии. •Телекоммуникации.

Графы в биологии [ править ]

Графы играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы в теории массового обслуживания [ править ]

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

Графы в математике [ править ]

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

Применение графов в других областях [ править ]

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

Выводы [ править ]

В любой области науки и техники встречаешься с графами. Графы — это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи, различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Многие математические факты удобно формулировать на языке графов. Теория графов является частью многих наук. Теория графов — одна из самых красивых и наглядных математических теорий. В последнее время теория графов находит всё больше применений и в прикладных вопросах. Возникла даже компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов.

Добавить комментарий Отменить ответ

Имя *

Email *

Комментарий

Сохранить моё имя, email и адрес сайта в этом браузере для последующих моих комментариев.