Зміст
Вступ 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 1 називається зводиться (по Карпу) до мови L 2 , якщо існує функція, , обчислювана за поліноміальний час, що володіє наступним властивістю: f (x) належить L 2 тоді і тільки тоді, коли x належить L 1 . Мова L 2 називається 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, ij., (3)
x (i, j) {0,1}. (4)
Тут умови (1) означають, що комівояжер рівно один раз в'їде в кожне місто (крім міста з номером 0); умови (2) означають, що комівояжер рівно один раз виїде з кожного міста (крім міста з номером 0), обмеження (3) означають існування лише одного циклу, що починається в місті з номером 0, що проходить через усі міста і завершується в місті з номером 0; обмеження (4) є природними умовами на введені змінні.
Пока...
