Марям математика. Математические основы информатики
 Скачать 18.02 Kb.
|
|
Тема: Математические основы информатики Содержание Введение 1 Теория графов 1.1 Понятие и терминология теории графов 1.2 Некоторые задачи теории графов 2 Математическая логика и теория типов Заключение Список использованной литературы Введение В широком смысле информа́тика (ср. со сходными по звучанию и происхождению нем. Informatik и фр. Informatique, в противоположность традиционному англоязычному термину англ. computer science — наука о компьютерах - в США или англ. computing science — вычислительная наука -в Британии есть наука о вычислениях, хранении и обработке информации. Она включает дисциплины, так или иначе относящиеся к вычислительным машинам: как абстрактные, вроде анализа алгоритмов, так и довольно конкретные, например, разработка языков программирования Согласно тезису Чёрча — Тьюринга, все известные типы вычислительных машин качественно эквивалентны в своих возможностях: любое действие, выполнимое на одной вычислительной машине, также выполнимо и на другой. Тезис иногда преподносят как фундаментальный принцип информатики, обращая особое внимание на машину Тьюринга и машину фон-неймановской архитектуры, поскольку они имеют явное сходство с большинством из ныне действующих компьютеров. В рамках современной информатики учёные изучают также и другие типы машин, не только практически осуществимые (такие, как параллельные и квантовые компьютеры), но и сугубо абстрактные математические модели (к примеру, машина случайного доступа, которая имеет бесконечное число регистров). Темами исследований в информатике являются вопросы: что можно, а что нельзя реализовать в программах (теория вычислимости и искусственный интеллект), каким образом можно решать специфические задачи с максимальной эффективностью (алгоритмы), в каком виде следует хранить и восстанавливать информацию специфического вида (структуры данных), как программы и люди должны взаимодействовать друг с другом (пользовательский интерфейс и языки программирования) и т. п. Отдельной наукой информатика была признана лишь в 1970-х; до этого она развивалась в составе математики, электроники и других технических наук. Некоторые начала информатики можно обнаружить даже в лингвистике. С момента своего признания отдельной наукой информатика разработала собственные методы и терминологию. Первый факультет информатики был основан в 1962 году в университете Пердью (Purdue University). Сегодня факультеты и кафедры информатики имеются в большинстве университетов мира. Высшей наградой за заслуги в области информатики является премия Тьюринга. 1 Теория графов 1.1 Понятие и терминология теории графов Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В наиобщем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G={R,V}, где V есть подмножество любого счётного множества, а R - подмножество VЧV. Математические основы информатики Рис. 1. Граф с шестью вершинами и семью рёбрами Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут (см. Рис. 1). Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях»1. 1.2 Некоторые задачи теории графов * Семь мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736. * Проблема четырёх красок — была сформулирована в 1852 году, но доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)). * Задача коммивояжёра — одна из наиболее известных NP-полных задач. * Задача о клике — ещё одна NP-полная задача. * Нахождение минимального стягивающего дерева. Задача коммивояжёра заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило указывается, что маршрут должен проходить через каждый город только один раз, в таком случае выбор осуществляется среди гамильтоновых циклов. Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Простейшие методы решения задачи коммивояжёра: полный лексический перебор, жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а так же алгоритм муравьиной колонии. Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение. Задача коммивояжёра есть NP-полная задача1. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора. Назовём языком множество слов над алфавитом Σ. Задачей здесь является определение того, принадлежит данное слово языку или нет. Язык L1 называется сводимым (по Карпу) к языку L2, если существует функция,Математические основы информатики, вычислимая за полиномиальное время, обладающая следующим свойством: f(x) принадлежит L2 тогда и только тогда, когда x принадлежит L1. Язык L2 называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден и при этом сам лежит в классе NP. Таким образом, если будет найден алгоритм, решающий хоть одну NP-полную задачу за полиномиальное время, все NP-задачи будут лежать в классе P. Вернемся к задаче коммивояжера. Математическая модель. Исходные параметры модели. Пусть i=0,1,2,...,m - номера городов, i=0 - номер выделенного города (начало и окончание маршрута). Обозначим через R=Математические основы информатикиr(i,j)Математические основы информатики- (m+1)(m+1) матрицу расстояний, элемент которой r(i,j) - расстояние между городом с номером i и городом с номером j. Варьируемые параметры модели. Обозначим через X=Математические основы информатикиx(i,j)Математические основы информатики- (m+1)(m+1) матрицу неизвестных, элемент которой x(i,j) =1, если коммивояжер из города с номером i переедет в город с номером j, x(i,j) = 0, в противном случае; u(i) - специальные переменные, i=1,2,...m. Ограничения математической модели. Математические основы информатикиx(i,j) =1, j=1,2,...,m, (1) Математические основы информатикиx(i,j) =1, i=1,2,...,m, (2) u(i) - u(j) + m x(i,j) Математические основы информатикиm-1, i=1,2,...,m, j=1,2,...,m, iМатематические основы информатикиj., (3) x(i,j)Математические основы информатики{0,1}. (4) Здесь условия (1) означают, что коммивояжер ровно один раз въедет в каждый город (кроме города с номером 0); условия (2) означают, что коммивояжер ровно один раз выедет из каждого города (кроме города с номером 0), ограничения (3) означают существование лишь одного цикла, начинающегося в городе с номером 0, проходящего через все города и завершающегося в городе с номером 0; ограничения (4) являются естественными условиями на введенные переменные. Покажем, что условия (3) являются необходимыми и достаточными условиями существования лишь одного цикла. Действительно, пусть это не так и найдется подцикл с числом городов k Математические основы информатики(m-1)k (все u(i) и u(j) взаимно уничтожаются), что противоречит существованию подцикла длины k С другой стороны, покажем, что для цикла, проходящего через все города, начинающегося и заканчивающегося в городе с номером 0, найдутся величины u(i), удовлетворяющие условиям (3). Положим u(i)=p, если город с номером i будет посещен коммивояжером p-ым по порядку, p=1,2,...,m. Пусть x(i,j) = 0. Тогда условия (3) примут вид: u(i) - u(j) Математические основы информатикиm-1, что верно, так как p Пусть x(i,j) = 1. Тогда, так как если u(i) = p, то u(j)=p+1 (это следует из того, что город с номером j будет следующим в маршруте коммивояжера после города с номером i). Получим: u(i) - u(j) + m x(i,j) = p - (p+1) +m = m - 1, что и доказывает правомочность присутствия в модели ограничений (3). Постановка оптимизационной задачи. Критерий оптимальности для задачи коммивояжера имеет вид: F(X)=Математические основы информатикиМатематические основы информатикиr(i,j) x(i,j)Математические основы информатикиmin . (5) Задача (1) - (5) называется задачей коммивояжера или задачей бродячего торговца. С помощью рассмотренной математической модели описываются следующие прикладные задачи: задача минимизации времени переналадок уникального оборудования; задача развозки готовой продукции по потребителям; задача управления работой снегоочистительных машин и др. Задача выполнимости булевых формул. Задача выполнимости булевых формул (SAT или ВЫП) — задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операцийМатематические основы информатики(И),Математические основы информатики(ИЛИ) иМатематические основы информатики(HE). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной. Согласно теореме Кука, доказанной Стивеном Куком в 1971-м году, проблема SAT NP-полна. Чтобы четко сформулировать задачу распознавания необходимо условиться об алфавите, с помощью которого задаются экземпляры языка. Этот алфавит должен быть фиксирован и конечен. В своей книге Хопкрофт, Мотвани и Ульман предлагают использовать следующий алфавит: {«Математические основы информатики», «Математические основы информатики», «Математические основы информатики», «(», «)», «x», «0», «1»}. При использовании такого алфавита скобки и операторы записываются естественным образом, а переменные получают следующие имена: x1, x10, x11, x100 и т. д., согласно их номерам, записанным в двоичной системе счисления. Пусть некоторая булева формула, записанная в обычной математической нотации, имела длину N символов. В ней каждое вхождение каждой переменной было описано хотя бы одним символом, следовательно, всего в данной формуле не более N переменных. Значит, в предложенной выше нотации каждая переменная будет записана с помощьюМатематические основы информатикисимволов. В таком случае, вся формула в новой нотации будет иметь длинуМатематические основы информатикисимволов, то есть длина строки возрастет в полиномиальное число раз. Например, формулаМатематические основы информатикипримет видМатематические основы информатики. Семь мостов Кёнигсберга. Семь мосто́в Кёнигсберга существовали в Кёнигсберге (нынешнем Калининграде) в XVI—XX веках (см. Рис. 2). Взаимное расположение мостов натолкнуло математика Леонарда Эйлера на размышления, приведшие к возникновению теории графов. Математические основы информатики Рис. 2. Старинная карта Кёнигсберга. Буквами обозначены части города: А — Альтштадт, Б — Кнайпхоф, В — Ломзе, Г — Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный, 6 — Высокий, 7 — Медовый Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу, как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако доказать, что это даже теоретически невозможно. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно). На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: • Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин. • Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. • Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно невозможно пройти по всем мостам, не проходя ни по одному из них дважды1. Математические основы информатики Рис. 3. Упрощённая схема мостов Кёнигсберга. Значение букв и цифр — см. Рис.2 - комментарий к старинной карте КёнигсбергаМатематические основы информатики Рис. 4. Граф кёнигсбергских мостов Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете. Проблема четырёх красок — математическая задача, предложенная Ф. Госри (англ. Francis Guthrie) в 1852 году. Выяснить, можно ли всякую, расположенную на сфере карту, раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы в виде дуги, были раскрашены в разные цвета. К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Не смотря на последующие упрощения, доказательство практически невозможно проверить не используя компьютер. Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В 1852 году Френсис Гутри (Guthrie), составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану (DeMorgan), а тот – математической общественности. Точная формулировка гипотезы опубликована А. Кэли (Cayley, 1878). Первое доказательство появилось год спустя и принадлежало В. Кемпе (Kempe). Одиннадцать лет спустя П. Хивуд (Heawood) обнаружил в нем ошибку1. За первым ошибочным доказательством последовало множество других. В этом отношении проблема четырех красок уступала лишь знаменитой проблеме Ферма. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увеличено до 38. В 1977 году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном (Appel, Haken) и опубликовано в двух статьях. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день. Сначала мы приведем точные формулировки, докажем теорему о пяти красках и укажем некоторые эквивалентные проблемы. Проблемы раскраски карты на глобусе и плоскости эквивалентны. Действительно, в случае карты на сфере можно вырезать кусок внутренней области какой-либо страны; продырявленную сферу можно деформировать (растянуть) в плоскую область – представим, что карта сделана из тонкой резины. На плоской карте отверстие превратится в "океан", омывающий со всех сторон одну страну. Разумеется, длины границ, их форма, размеры стран подвергнутся при растяжении значительным изменениям, но сетка границ останется, добавится лишь растянутая граница прорезанного отверстия, внешняя граница океана. Ее можно убрать, то есть раскрасить океан так же, как и окруженную им страну. Такие деформации стран и их границ, очевидно, не меняют задачи раскраски. Ниже рассматривается плоская карта.Начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему, касающуюся плоских графов. Выберем столицу у каждой страны (то есть выберем по одной внутренней точке в каждой из стран) и соединим дугами столицы стран, имеющих общий сегмент границы. В результате получится так называемый плоский граф. Определение 1. Графом G называется конечное множество вершин V(G) и конечное множество ребер R(G ), так что каждое ребро имеет своими концами две различные вершины. Граф называется плоским, если вершины являются точками плоскости, а ребра – ломаными линиями (составленными из отрезков) в этой же плоскости, имеющими своими концами вершины, не пересекающимися между собой и не включающими других вершин, кроме своих концов. Отметим, что в плоском графе не допускаются петли (ребра, имеющие началом и концом одну и ту же вершину). Плоский граф разрезает плоскость на совокупность D(G) неперекрывающихся многоугольных областей, необязательно конечных (рис. 5). Математические основы информатики Рис. 5. 4-раскраска плоского графа Если перенумеровать используемые краски 1, 2, ..., n, то на соответствующем карте плоском графе этими числами окажутся занумерованы вершины / столицы. Определение 2. Правильной n-раскраской плоского графа G называется отображение f: V(G ) ® {1, 2, ..., n}, причем f(u1) # f(u2) в случае, если существует такое ребро r k R(G ), что граница r состоит из u1 и u2 . Наконец, можно сформулировать проблему четырех красок в виде следующего утверждения. Теорема 1. Любой плоский граф допускает правильную 4-раскраску. Вот решение этой-то проблемы и заняло более столетия. Однако на первый взгляд чуть более слабое утверждение о правильной 5-раскраске доказать достаточно просто. Для доказательства понадобится формула Эйлера, связывающая число вершин, ребер и областей. Пусть | M | обозначает число элементов конечного множества M. Теорема Эйлера. Для любого плоского графа | V(G) | – | R(G) | + | D(G) | = 2. Заметим, что если не учитывать внешнюю бесконечную область, то формула Эйлера для триангуляции конечного плоского графа имеет вид | V(G ) | – | R(G ) | + + | D(G ) | = 1. Теорема 2. Любой плоский граф допускает правильную 5-раскраску. Доказательство. Сначала упростим граф. Если есть несколько ребер, соединяющих некоторую пару вершин (такая ситуация может возникнуть, если две страны имеют несколько несвязанных между собой кусков границы, например как у России и Китая), то оставим только одно ребро: правильность раскраски такого уменьшенного графа все равно гарантирует правильную раскраску исходного. Проведем теперь индукцию по числу вершин графа. Для графа с тремя вершинами утверждение теоремы очевидно. Пусть оно справедливо для всех графов с n – 1 вершиной. Пусть D1 , D2 , ..., Dm – полный набор всех m = D(G ) областей графа, а N(Di) – |