Зміст
Вступ 3
1 Теорія графів 5
1.1 Поняття та термінологія теорії графів 5
1.2 Деякі задачі теорії графів 6
2 Математична логіка і теорія типів 25
Висновок 27
Список використаної літератури 30

Введення

У широкому сенсі інформатика (пор. зі схожими за звучанням і походженням ньому. 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-повна задача [2]. Часто на ній проводять обкатку нових підходів до евристичного скорочення повного перебору.
Назвемо мовою безліч слів над алфавітом Σ. Завданням тут є визначення того, належить дане слово мови чи ні. Мова L ₁ називається зводиться (за Карпу) до мови L _2, якщо існує функція, , Обчислювана за поліноміальний час, що володіє наступною властивістю: f (x) належить L ₂ тоді і тільки тоді, коли x належить L _1. Мова L ₂ називається 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) + mx (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, що не проходить через місто з номером 0. Складаючи всі нерівності (3) за умов, що x (i, j) = 1 по містах підциклу, отримаємо mk (M-1) k (всі u (i) і u (j) взаємно знищуються), що суперечить існуванню підциклу довжини k <m.
З іншого боку, покажемо, що для циклу, що проходить через усі міста, який починається і закінчується в місті з номером 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 <m+1 і p> 0.
Нехай x (i, j) = 1. Тоді, так як якщо u (i) = p, то u (j) = p +1 (це випливає з того, що місто з номером j буде наступним у маршруті комівояжера після міста з номером i). Отримаємо:
u (i) - u (j) + mx (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 року. У цьому листі Ейлер пише про те, що він зміг знайти правило, користуючись яким легко визначити, чи можна пройти по всіх мостах, не проходячи двічі по жодному з них (у разі семи мостів Кенігсберга це неможливо).
На спрощеній схемі частини міста (графі) мостах відповідають лінії (ребра графа), а частинам міста - точки з'єднання ліній (вершини графа). У ході міркувань Ейлер прийшов до наступних висновків:
• Кількість непарних вершин (вершин, до яких веде непарне число ребер) графа завжди парне. Неможливо накреслити граф, який мав би непарне число непарних вершин.
• Якщо всі вершини графа парні, то можна, не відриваючи олівця від паперу, накреслити граф, при цьому можна починати з будь-якої вершини графа і завершити його в тій же вершині.
• Граф з більш ніж двома непарними вершинами неможливо накреслити одним розчерком.
Граф кенігсберзькими мостів мав чотири непарні вершини, отже неможливо пройти по всіх мостах, не проходячи по жодному з них двічі [3].


Рис. 3. Спрощена схема мостів Кенігсберга. Значення букв і цифр - див. Рис.2 - коментар до старовинної карті Кенігсберга


Рис. 4. Граф кенігсберзькими мостів
Створена Ейлером теорія графів знайшла дуже широке застосування: наприклад, її використовують при вивченні транспортних і комунікаційних систем, зокрема, для маршрутизації даних в Інтернеті.
Проблема чотирьох фарб - математична задача, запропонована Ф. Госрі (англ. Francis Guthrie) в 1852 році.
З'ясувати, чи можна будь-яку, розташовану на сфері карту, розфарбувати чотирма фарбами так, щоб будь-які дві області, що мають загальний ділянку кордону у вигляді дуги, були розфарбовані в різні кольори.
К. Аппель і В. Хакен довели в 1976 р., що так можна розфарбувати будь-яку карту. Це була перша велика математична теорема, для доказу якої був застосований комп'ютер. Не дивлячись на наступні спрощення, доказ практично неможливо перевірити не використовуючи комп'ютер.
Розфарбовуючи географічну карту природно користуватися по можливості меншою кількістю квітів, однак так, щоб дві країни, які мають спільну частину кордону (не тільки спільну точку), були пофарбовані по-різному. У 1852 році, Френсіс Гутрі (Guthrie), складаючи карту графств Англії, звернув увагу, що для такої мети цілком вистачає чотирьох фарб. Його брат, Фредерік, повідомив про це спостереженні відомому математику О. Де Моргану (DeMorgan), а той - математичної громадськості. Точна формулювання гіпотези опублікована А. Келі (Cayley, 1878).
Перший доказ з'явилося рік потому і належало В. Кемпе (Kempe). Одинадцять років по тому П. Хівуд (Heawood) виявив у ньому помилку [4]. За першим помилковим доказом було безліч інших. У цьому відношенні проблема чотирьох фарб поступалася лише знаменитої проблеми Ферма. До середини 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) у разі, якщо існує таке ребро rk 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) - число ребер, що складають кордон i-й області графа. При цьому N (Di) ³ 3 для будь-якого i. Будь-яке ребро входить в межу в точності двох областей, тому
N (D1) + N (D2) + ... + N (Dm) = 2R (G).
Внаслідок нерівностей N (Di) ³ 3 маємо
2R (G) = N (D1) + N (D2) + ... + N (Dm) ³ 3m = 3D (G),
звідки 2R (G) ³ 3D (G).
За формулою Ейлера | V (G) | - 2 + | D (G) | = | R (G) |, звідки
3 | R (G) | = 3 | V (G) | - 6 + 3 | D (G) | £ 3 | V (G) | - 6 + 2 | R (G) |
і, отже,
| R (G) | £ 3 | V (G) | - 6.
Зауважимо, що подвійну кількість ребер можна ототожнити і з іншого характеристикою графа. Нехай a1, a2, ... ..., An є повний набір n = V (G) вершин графа, а M (aj) - число ребер, що сходяться у вершині з номером j. Але кожне ребро закінчується двома вершинами, тому
2R (G) = M (a1) + M (a2) + ... + M (an).
Крім того, як це випливає з нерівності (1), 2 | R (G) | £ 6 | V (G) | - 12. Отже,
M (a1) + M (a2) + ... + M (an) £ 6 | V (G) | - 12.
З останнього нерівності можна вивести, що існує принаймні одна вершина, в якій сходиться не більше п'яти ребер. Дійсно, припустимо противне, тобто "j M (aj) ³ 6. Тоді
M (a1) + M (a2) + ... + M (an) ³ 6n = 6V (G),
що суперечить (2).
Перенумеруем вершини так, що у вершині a = an сходиться не більше п'яти ребер.
Якщо у вершині a сходяться не більше чотирьох ребер, то розглянемо граф G \ a, який виходить з G усуненням вершини a і всіх закінчуються в ній ребер. Граф G \ a допускає правильну 5-розмальовку за припущенням індукції. А так як ребра з'єднують вершину a не більше ніж з чотирма вершинами цього меншого графа, то для правильної розмальовки a залишається принаймні один колір (з п'яти).
Нехай тепер в a сходиться рівно п'ять ребер. Розглянемо граф H É G, що складається з тих п'яти вершин, куди приходять ребра, що виходять з a і з'єднують їх (в G) ребер. У графі H обов'язково знайдуться дві вершини, не з'єднані ребром. Дійсно в іншому випадку в п'ятикутнику H буде C ₅ ² = 10 ребер (це неважко порахувати і безпосередньо). Однак у силу (1)
| R (H) | £ 3 | V (H) | - 6 = 3 "5 - 6 = 9,
і ми приходимо до протиріччя.
Нехай b і g суть ті вершини H, які не сполучені між собою. Не з'єднані вони і в G \ a. Розглянемо граф G ', який виходить з G \ a за допомогою деформації, яка ототожнює (поєднує) b і g. Граф G '- це плоский граф, тому що при ототожненні вершин у цій ситуації не може виникнути петлі. Але для G 'справедливо припущення індукції, і існує деяка його правильна 5-розмальовка j. Роз'єднаємо в цьому розфарбоване графі вершини b і g. Тоді правильну 5-розмальовку отримує і граф G \ a, причому таку, що j (b) = j (g). Іншими словами, b і g розфарбовані однаково і, отже, розфарбування п'яти сусідніх з a вершин графа H використовує не більше чотирьох кольорів.
Використовуємо залишився колір для розмальовки вершини a і отримаємо правильну 5-розмальовку G!
Проблема чотирьох фарб здається на перший погляд ізольованою завданням, мало пов'язаної з іншими розділами математики та практичними завданнями. Насправді це не так. Відомо більше 20 її переформуліровок, які пов'язують цю проблему із завданнями алгебри, статистичної механіки і завданнями планування. І це теж характерно для математики: вирішення завдання, що вивчається з цікавості, виявляється корисним в описі реальних і зовсім різних за своєю природою об'єктів і процесів. Тут ми розглянемо одну задачу, еквівалентну проблеми чотирьох фарб.
Нехай i, j і k суть стандартні поодинокі напрямні вектори координатних осей x, y і z відповідно. У тривимірному просторі визначено векторний добуток векторів, що позначається знаком i. Якщо u, uk R3 - два вектори, то їх векторний добуток uiu має довжину а напрямок визначається за правилом свердлика або правої руки. Легко переконатися в тому, що цей твір не асоціативно, тобто твір u1 i u2 i ... i un, взагалі кажучи, не визначено, якщо в ньому не розставлені дужки. Дійсно, наприклад, 0 = ii (jij) (iij) ij = - i. Для того, аби вираження u1 i u2 i ... i un мало певний сенс, у ньому потрібно правильним чином розставити n - 2 пари дужок. Такий вираз з дужками називається асоціацією.
Теорема 3. Для кожної пари асоціацій, пов'язаних з виразом u1 i u2 i ... i un, існує така підстановка {u1, u2, ..., un} {i, j, k} (тобто {i, j, k} підставляються якимось чином замість всіх uk), що значення асоціацій будуть рівні між собою і відмінні від нуля.
Затвердження стосується тільки векторів у тривимірному просторі і здається простим, але довести його так само важко, як і теорему про 4-розфарбуванні. Доказ еквівалентності останньої теореми проблеми чотирьох фарб дано Л. Кауфманом та пояснено на пальцях. Тут ми тільки коротко пояснимо зв'язок цих завдань.
По-перше, причому тут графи? Графічно асоціацію можна уявляти собі у вигляді дерева, тобто графа спеціального виду, влаштованого наступним чином. Твору будь-якої пари uiu відповідає пара ребер (гілок), що мають спільну вершину, при цьому кінці гілок відповідають співмножником, а загальне початок - твору. Крок за кроком виконуючи дії, визначені в асоціації дужками, приходимо до кореня цього дерева, відповідному результату виконання всіх множення у заданій асоціації. У верхній частині рис. 2 представлені дерева, зумовлені асоціаціями (u1 i u2) i (u3 i u4) (внизу, гілками вгору) і (((u1 i u2) i u3) i u4) (вгорі, гілками вниз).
Склеим тепер обидва ці дерева по кінцях гілок (кінці відповідають всім елементам асоціації u1, u2, u3, u4) і потім з'єднаємо коріння обох дерев додатковим ребром. Вийде плоский граф, зображений в нижній частині рис. 6. Відзначимо два специфічних властивості такого графа: у будь-якій його вершині сходиться рівно три ребра (ця властивість називається кубичной графа). Видалення будь-якого ребра не призводить до поділу графа на дві не пов'язані між собою компоненти (це властивість назвемо відсутністю розділяє ребра).


Рис. 6. Плоский граф
Ця конструкція узагальнюється для будь-якої пари асоціацій з однаковою кількістю співмножників.
По-друге, причому тут розмальовки? Будемо вважати вектори i, j і k трьома фарбами, приписаними всіх елементів асоціації або, що те ж, кінцевим гілках дерев. Інші гілки аж до кореня забарвляться за правилами обчислення векторного добутку. Якщо ми хочемо після обчислень отримати ненульовий результат, то, як легко перевірити, три ребра, які сходяться в будь-якій вершині, повинні бути розфарбовані по-різному.
Тим самим кубічний плоский граф, отриманий склеюванням двох дерев різних асоціацій, отримає таку розмальовку ребер, що в будь-якій вершині сходяться три по-різному забарвлених ребра. Це так звана правильна 3-розфарбування ребер.
По-третє, до чого тут проблема чотирьох фарб? Справа в тому, що проблеми правильної 4-розмальовки вершин і правильної 3-раcкраскі ребер еквівалентні. Точніше, справедлива
Теорема 4. Кожен кубічний граф без поділяють ребер допускає правильну 3-розмальовку ребер.
Ця теорема еквівалентна теоремі 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) неперекривающіхся багатокутних областей". Тим часом це твердження не належить до числа аксіом або шкільних теорем плоскої геометрії, і його потрібно доводити. Відповідна теорема, сформульована К. Жорданом, доводиться дуже непросто, проте основні труднощі пов'язані з тим, як слід розуміти слова типу "розрізає", інтуїтивно цілком ясні, але насилу піддається формалізації. У світлі цього зауваження стає вже не зовсім зрозумілим, чи доведена теорема про п'ять фарбах або ми повірили правдоподібним міркуванням, заснованим на інтуїтивних уявленнях про властивості геометричних фігур.
Довгий час ідеалом математичної строгості були формулювання та докази Евкліда, в яких здійснювалася програма виведення теорем з аксіом за певними правилами (метод дедукції, що дозволяє отримувати неочевидні затвердження з очевидних допомогою ряду явно пропонованих елементарних, очевидно законних, умовиводів). Цей зразок строгості і в наш час недосяжний в курсі шкільної математики, але для сучасної чистої математики стандарти Евкліда недостатні. Евклід, мабуть, не замислювався над тим, чому пряма ділить площину на дві частини (і що це означає), він не визначав поняття "між", вважаючи це поняття очевидним і т.д. Велика частина відповідних тверджень доведена або включена в аксіоматику геометрії тільки в останню сотню років. Формальні висновки з нової системи аксіом стали набагато довше, ніж в античні часи.
Важко навіть уявити довжину повного виведення теореми про п'ять фарбах відповідно до сучасних стандартів математичної логіки і системи аксіом геометрії. Але абсолютно точно, що таке міркування ніхто ніколи не робив через марність цього заняття: формальні висновки практично не піддаються перевірці в силу властивостей людської психіки: крім їх набагато більшою (порівняно зі звичними міркуваннями) довжини їх свідоме засвоєння йде набагато повільніше. Тому зазвичай задовольняються упевненістю в тому, що формальний висновок можливий у принципі.
У формулі Ейлера, наприклад, математики не сумніваються. Взагалі прийняття докази є якийсь соціальний акт. Видатний алгебраїст Ю.І. Манін у своїй книзі "доказові і недоказове" [5] пише з цього приводу: "... відсутність помилок в математичній роботі (якщо вони не виявлено), як і в інших природничих науках, часто встановлюється за непрямими даними: мають значення відповідність з спільними сподіваннями, використання аналогічних аргументів на інших роботах, роздивляння "під мікроскопом" окремих ділянок докази, навіть репутація автора, словом, відтворюваність у широкому сенсі. "Незрозумілі" докази можуть зіграти дуже корисну роль, стимулюючи пошуки більш доступних міркувань. "
Саме така історія відбувається і з доказом теореми про чотири фарбах. Не так давно з'явився новий доказ, причому та частина, яка виконана не на комп'ютері, вже піддається перевірці. Проте комп'ютерна частина все ще залишається швидше предметом віри. Адже навіть перевірка роздруківок всіх програм і всіх вхідних даних не може гарантувати від випадкових збоїв або навіть від прихованих вад електроніки (згадаємо, що помилки при виконанні поділу у першої версії процесора Pentium були випадково знайдені після півроку після початку його комерційних продажів - до речі, математиком, фахівцем у теорії чисел). Мабуть, єдиний спосіб перевірки комп'ютерних результатів - написати іншу програму і для іншого типу комп'ютера. Це, звичайно, зовсім не схоже на стандартний ідеал дедуктивних міркувань, але саме так здійснюється перевірка тверджень у всіх експериментальних науках [6].
З яких математика, стало бути, виключена марно.

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

Математична логіка - розділ математики, що вивчає докази. Відповідно до визначення П. С. Порецкого, «математична логіка є логіка з предмета, математика за методом» [7].
Застосування в логіці математичних методів стає можливим тоді, коли судження формулюються на деякій точному мовою. Такі точні мови мають дві сторони: синтаксис і семантику. Синтаксисом називається сукупність правил побудови об'єктів мови (зазвичай званих формулами). Семантикою називається сукупність угод, що описують наше розуміння формул (або деяких з них) і дозволяють вважати одні формули вірними, а інші - ні.
Важливу роль у математичній логіці відіграє поняття числення. Обчисленням називається сукупність правил виводу, що дозволяють вважати деякі формули виведеними. Правила виводу поділяються на два класи. Одні з них безпосередньо кваліфікують деякі формули як виведені. Такі правила виведення прийнято називати аксіомами. Інші ж дозволяють вважати виведеними формули A, синтаксично пов'язані деяким наперед визначеним способом з кінцевими наборами виведених формул. Широко застосовуваним правилом другого типу є правило modus ponens: якщо виведені формули A і , То виводиться і формула B.
Ставлення числень до семантики виражається поняттями семантичної придатності та семантичної повноти обчислення. Обчислення І називається семантично придатним для мови Я, якщо будь-яка виводиться в І формула мови Я є вірною. Аналогічно, обчислення І називається семантично повним в мові Я, якщо будь-яка вірна формула мови Я виведена в І.
Багато з розглянутих в математичній логіці мов мають семантично повними і семантично придатними численнями. Зокрема, відомий результат К. Геделя про те, що так зване класичне числення предикатів є семантично повним і семантично придатним для мови класичної логіки предикатів першого порядку. З іншого боку, є чимало мов, для яких побудова семантично повного і семантично придатного обчислення неможливо. У цій області класичним результатом є теорема Геделя про неповноту, яка стверджує неможливість семантично повного і семантично придатного обчислення для мови формальної арифметики.
Теорія типів - математично формалізована база для проектування, аналізу і вивчення систем типів даних в теорії мов програмування (розділ інформатики). Багато програмісти використовують це поняття для позначення будь-якого аналітичного праці, вивчає системи типів в мовах програмування. У наукових колах під теорією типів найчастіше розуміють більш вузький розділ дискретної математики, зокрема λ-числення.
Сучасна теорія типів була частково розроблена в процесі вирішення парадоксу Рассела і багато в чому базується на роботі Бертрана Рассела і Альфреда Вайтхед «Principia Mathematica» (цей фундаметальний тритомник математичної логіки до цих пір не видано російською мовою) [8].

Висновок

Прабатьком інформатики є кібернетика, заснована американським математиком Норбертом Вінером, що опублікував в 1948 році однойменну книгу. Основоположником радянської школи кібернетики та інформатики визнаний професор МДУ Олексій Андрійович Ляпунов.
Слово «інформатика» для позначення комплексу комп'ютерних наук було введено в словник російської мови в 1976 році академіком Андрієм Петровичем Єршовим.
Незважаючи на широку поширеність терміна «інформатика», у фахівців досі немає єдиної думки про його тлумаченні. Існують три підходи:
• надширокий, що включає в інформатику все, що пов'язано з будь-якими процесами отримання, перетворення і передачі інформації;
• широкий, що включає в інформатику все, що пов'язано з комп'ютерами, в тому числі питання конструювання обчислювальної техніки;
• вузький, що визначає інформатику тільки як науку про застосування комп'ютерів, тобто як науку про комп'ютерні технології.
Таким чином, до теперішнього часу є три тлумачення терміну «інформатика».
Перше - надширокої, при якому в сферу її ведення потрапляє весь комплекс наук, так чи інакше пов'язаних з отриманням і обробкою інформації, незалежно від використання комп'ютерів. У цьому значенні термін часто використовується у виданнях філософської та методологічної спрямованості, а також у непрофесійної середовищі (журналістами, політиками).
Друге - інформатика як повний набір комп'ютерних наук, точний еквівалент computer science. У даному значенні термін поєднує найрізноманітніші боку програмування і використання комп'ютерів, методів їх конструювання та розробки програмного забезпечення. Таке тлумачення найчастіше використовується у звичайному професійною мовою і при зворотному перекладі на англійську. Наприклад, «факультет інформатики» краще за все перевести як «computer science faculty» або «computer science department» залежно від того, на яку аудиторію розрахований переклад (у британському англійською більш поширене слово «faculty», а в американському - «department») .
Третє - інформатика у вузькому сенсі, коли за рамки computer science виносяться детальні питання технічного пристрою комп'ютерів (hardware), а в складі науки залишаються проблеми їх застосування. У такому значенні термін зазвичай використовується в вузькопрофесійного середовищі програмістів, а також у навчальних програмах. Саме так його слід розуміти в загальноприйнятому в освітньому середовищі словосполученні «інформатика і обчислювальна техніка», інакше виходить логічна некоректність.
Як відомо, будь-яка класифікація умовна і має деяку ціль. У світлі всього викладеного ми, маючи на увазі підготовку фахівців у галузі комп'ютерних наук, будемо користуватися останнім, вузьким тлумаченням і визначимо інформатику як наукову дисципліну, предметом якої є комп'ютерні технології. Замість терміна «комп'ютерні» часто використовуються аналогічні за змістом визначення "нові інформаційні» або просто «інформаційні», тому в спеціальній літературі можна зустріти терміни «ІТ-служба», «ІТ-спеціаліст», «факультет ІТ» і т.п.
Для ілюстрації меж розділу між кібернетикою, обчислювальною технікою та інформатикою можна скористатися таким образним порівнянням. Якщо уподібнити кібернетика, розробляє алгоритми, композитору, який тут складає музику, а конструктора ЕОМ - скрипковому майстру, то фахівця з інформатики можна буде порівняти зі скрипалем, які реалізують задум композитора і збагачують його своєю майстерністю і талантом. Тому інформатика - не просто галузь знань, а неподільний сплав ремесла, науки і мистецтва.
Для професійного вживання рекомендується керуватися вузьким підходом, виділяючи в самостійні науки кібернетику, обчислювальну техніку й інформатику [9].
Виникнення інформатики в другій половині 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.