Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Эта теорема эквивалентна теореме 1 о правильной 4-раскраске карт. Доказательство эквивалентности не очень сложно, и его можно найти в большинстве учебников по теории графов.

Объясним лишь, как 4-раскраска областей кубического графа порождает 3-раскраску его ребер. Пусть области кубического графа окрашены четырьмя красками. Вместо того чтобы нумеровать краски числами 1, 2, 3 и 4, занумеруем их парами (0, 0), (0, 1), (1, 0) и (1, 1). При отсутствии разделяющих ребер к каждому ребру примыкают две разные области. Припишем ребру, разделяющему области, окрашенные с помощью (i, j) и (k, l ), цвет по формуле (i + k, j + l )(mod 2). Здесь n(mod 2) означает остаток от деления n на 2. Различающиеся пары цветов областей порождают только три пары (0, 1), (1, 0) и (1, 1) для раскраски ребер.

Доказательство Аппеля и Хакена, в целом хотя и принятое математическим сообществом, вызывает до сих пор определенный скептицизм. Для читателя, поверхностно знакомого с математикой, предыдущая фраза должна вызвать изумление: а как же обязательный для математики принцип исключенного третьего, в соответствии с которым утверждение либо справедливо, либо нет? Дело обстоит не так просто. Вот что пишут сами авторы доказательства: "Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно".

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

Вернемся сначала к доказательствам формулы Эйлера и теоремы о 5-раскраске. Ее-то вроде бы нетрудно проверить, взяв лист бумаги и карандаш. Но рассуждения в ней основаны на очевидных соображениях типа: "Плоский граф разрезает плоскость на совокупность D(G) неперекрывающихся многоугольных областей". Между тем это утверждение не принадлежит к числу аксиом или школьных теорем плоской геометрии, и его нужно доказывать. Соответствующая теорема, сформулированная К. Жорданом, доказывается очень непросто, однако основные трудности связаны с тем, как следует понимать слова типа "разрезает", интуитивно вполне ясные, но с трудом поддающимся формализации. В свете этого замечания становится уже не совсем понятным, доказана ли теорема о пяти красках или мы поверили правдоподобным рассуждениям, основанным на интуитивных представлениях о свойствах геометрических фигур.

Долгое время идеалом математической строгости были формулировки и доказательства Евклида, в которых осуществлялась программа вывода теорем из аксиом по определенным правилам (метод дедукции, позволяющий получать неочевидные утверждения из очевидных посредством ряда явно предъявляемых элементарных, очевидно законных, умозаключений). Этот образец строгости и в наше время недостижим в курсе школьной математики, но для современной чистой математики стандарты Евклида недостаточны. Евклид, по-видимому, не задумывался над тем, почему прямая делит плоскость на две части (и что это значит), он не определял понятия "между", считая это понятие очевидным и т.д. Большая часть соответствующих утверждений доказана или включена в аксиоматику геометрии только в последнюю сотню лет. Формальные выводы из новой системы аксиом стали гораздо длиннее, чем в античные времена.

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

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

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

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

2 Математическая логика и теория типов

Математическая логика — раздел математики, изучающий доказательства. Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу» ⁰.

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

Важную роль в математической логике играет понятие исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и , то выводима и формула B.

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

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

Теория типов — математически формализованная база для проектирования, анализа и изучения систем типов данных в теории языков программирования (раздел информатики). Многие программисты используют это понятие для обозначения любого аналитического труда, изучающего системы типов в языках программирования. В научных кругах под теорией типов чаще всего понимают более узкий раздел дискретной математики, в частности λ-исчисление.

Современная теория типов была частично разработана в процессе разрешения парадокса Рассела и во многом базируется на работе Бертрана Рассела и Альфреда Уайтхэда «Principia Mathematica» (этот фундаметальный трёхтомник математической логики до сих пор не издан на русском языке)⁰.

Заключение

Прародителем информатики является кибернетика, основанная американским математиком Норбертом Винером, опубликовавшим в 1948 году одноименную книгу. Основоположником советской школы кибернетики и информатики признан профессор МГУ Алексей Андреевич Ляпунов.

Слово «информатика» для обозначения комплекса компьютерных наук было введено в словарь русского языка в 1976 году академиком Андреем Петровичем Ершовым.

Несмотря на широкую распространенность термина «информатика», у специалистов до сих пор нет единого мнения о его толковании. Существуют три подхода:

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

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

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

Таким образом, к настоящему времени имеются три толкования термина «информатика».

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

Второе – информатика как полный набор компьютерных наук, точный эквивалент computer science. В данном значении термин объединяет самые разные стороны программирования и использования компьютеров, методов их конструирования и разработки программного обеспечения. Такое толкование чаще всего используется в обычном профессиональном языке и при обратном переводе на английский. Например, «факультет информатики» правильнее всего перевести как «computer science faculty» или «computer science department» в зависимости от того, на какую аудиторию рассчитан перевод (в британском английском более распространено слово «faculty», а в американском – «department»).

Третье – информатика в узком смысле, когда за рамки computer science выносятся детальные вопросы технического устройства компьютеров (hardware), а в составе науки остаются проблемы их применения. В таком значении термин обычно используется в узкопрофессиональной среде программистов, а также в учебных программах. Именно так его следует понимать в общепринятом в образовательной среде словосочетании «информатика и вычислительная техника», иначе получается логическая некорректность.

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

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

Для профессионального употребления рекомендуется руководствоваться узким подходом, выделяя в самостоятельные науки кибернетику, вычислительную технику и информатику⁰.

Возникновение информатики во второй половине XX столетия не является случайностью. Компьютер и электросвязь – два закономерных продукта и инструмента информационной революции, знаменующей переход от индустриальной к постиндустриальной (информационной) эпохе в истории человечества.

Список использованной литературы

1. Апокин И. А., Майстров Л. Е. История вычислительной техники: От простейших счетных приспособлений до сложных релейных систем. М.: Наука, 2000.

2. Гладких Б. А. От абака до компьютера. Томск: Изд-во НТЛ, 2005.

3. Гутер Р. С., Полунов Ю. Л. От абака до компьютера. М.: Знание, 2001. .

4. Кук Д., Бейз Г. Компьютерная математика. М., Наука, 2000.

5. Марков А.А. Элементы математической логики. М.: Изд-во МГУ, 2004.

6. Пойа Д. Математическое открытие. М.: Наука, 2000.

7. Прилуцкий М.Х. Математические основы информатики. Нижний Новгород: Нижег.гос.ун-т, 2000.

8. Симонович С., Евсеев Г., Алексеев А. Общая информатика. М.: Дело, 1999.

9. Турецкий В.Я. Математика и информатика. Екатеринбург: Пропаганда, 2002.

10. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.: Мир, 2006.

11. Частиков А. Архитекторы компьютерного мира. Спб: БХВ-Петербург, 2002.

12. Шенфилд Дж. Математическая логика. М.: Наука, 2005.

0 Прилуцкий М.Х. Математические основы информатики. Нижний Новгород: Нижег.гос.ун-т, 2000. С. 21.

Характеристики

Список файлов реферата