Математичні засади інформатики. Математична логіка та теорія типів

Інформатика як технічна наука

Історія розвитку та фундамент інформатики

Джерелом розвитку інформатики стали документалістика,вивчає раціональні засоби та методи підвищення ефективності документообігу; кібернетика (kiberneticos- майстерний в управлінні). Термін «кібернетика» запровадив М. Ампер у першій половині ХІХ ст., а М. Вінер у середині наступного століття заклав основи кібернетики як науки.

Базовим фундаментом інформатики є кібернетика - наука, що займається вивченням законів побудови та управління складних систем (наприклад, дисципліна "теорія автоматичного управління"). Кібернетика(грец. Kibernetice- Мистецтво управління) виникла на стику математики, техніки та нейрофізіології. Початком ери кібернетики вважається вихід книги М. Вінера «Кібернетика, або Управління та зв'язок у тварині та машині». Центральним поняттям кібернетики є «інформація». Ось що писав про інформацію Н. Віннер: «…у той час як ентропія є мірою дезорганізованості, інформація, яка переноситься деяким потоком послань, визначає міру організованості. Фактично ми можемо визначити інформацію... як негативну ентропію». Сьогодні кібернетика займається принципами побудови та функціонування систем автоматичного управління, а основними завданнями науки виступають методи моделювання процесу прийняття рішень технічними засобами, розробка принципів та методів штучного інтелекту.

Сучасна інформатика починається із розробки перших електронно-обчислювальних машин (ЕОМ). Поняття "ЕОМ" пов'язане з іншим, більш загальним, поняттям - обчислювальна техніка(ВТ). Це поняття визначає сукупність пристроїв для автоматичного або автоматизованого оброблення даних. Як окремий розділ інформатики під обчислювальною технікою розуміють область знань про закони побудови та функціонування обчислювальних машин.

У перших механічних попередниках комп'ютера числа представлялися як лінійних переміщень ланцюгових і рейкових механізмів, чи вигляді кутових переміщень зубчастих і важільних механізмів. Їм притаманні – повільна швидкість та великі габарити пристроїв. Перехід від реєстрації переміщень до реєстрації сигналів дозволив знизити їх габарити та підвищити швидкість роботи.

У електронних пристроях йдеться про реєстрацію станів елементів пристрою. Стан два: "ввімкнено" та "вимкнено". Тому традиційна десяткова система є незручною.

Вже 1666 року можливість представлення чисел у двійковій системі запропонував Г. Лейбніц. Він прийшов до такої системи, займаючись питаннями концепції єдності та боротьби протилежностей та розглядаючи світу у вигляді безперервної взаємодії двох початків.

Іншим важливим підґрунтям сучасної інформатики стала математична логіка, засновником якої став учений у першій половині ХІХ століття Джордж Буль. Займаючись дослідженнями законів мислення, він застосував у логіці систему формальних позначень та правил, близьку до математичної. У математичній логіці результатом формального розрахунку логічного виразу є одне із двох логічних значень: істинаабо брехня. Основні логічні операції, що лежать в основі роботи всієї обчислювальної техніки та автоматики сьогодні: кон'юнкція (І/ AND), диз'юнкція (АБО/ OR), інверсія (НЕ/ NOT), що виключає АБО ( ХОР). У таб.1. представлені таблиці істинності для зазначених логічних функций.

Крім зазначених функцій існують комбіновані логічні функції: І-НЕ (штрих Фішера) та АБО-НЕ (стрілка Пірса). Особливістю цих елементів є можливість висловити решту логічних операцій, використовуючи одну з цих функцій (І-НЕ або АБО-НЕ).

Таблиця 1

Таблиці істинності для логічних функцій

Алгебра логіки ґрунтується на своїх законах. До основних відносять такі:

Закон несуперечності: ;

Закон виключення третього: ;

Закони де Моргана: ;;

Закон подвійного заперечення: .

Велике поширення в обчислювальній техніці набув тригер - елемент, що дозволяє запам'ятати 1 біт даних. Позначення та діаграма роботи RS-Тригер представлена ​​на рис. 2.1. RS-тригер має два входи: setі reset. При подачі на вхід Sодиниці вихід тригера Q» встановлюється у стан «1». При скиданні сигналу на « S» в нуль, стан виходу не змінюється, тобто тригер запам'ятовує стан виходу. Скидання здійснюється подачею «1» на вхід « R». При цьому на виході Q» встановлюється стан «0». Подача «1» на обидва входи одночасно називається забороненим станом тригера. В цьому випадку на виході в залежності від серії логіки може бути як "0", так і "1". Щоб уникнути виникнення такого стану використовують спеціальні схеми на вході тригера.

Мал. 2.1. Позначення та діаграма роботи RS-тригера

Муніципальна бюджетна загальноосвітня установа

«Середня загальноосвітня школа №30»

ПРОГРАМА ПДОУ

ПО ІНФОРМАТИЦІ ТА ІКТ

"Математичні основи інформатики"

Тунаєвої Наталії Анатоліївни

ДЛЯ 9 КЛАСУ

на 2016-2017 навчальний рік

м. Михайлівськ, 2016 р.

Пояснювальна записка

Курс «Математичні основи інформатики» складено на основі УМК Є. В. Андрєєва, Л. Л. Босова, І. Н. Фаліна – М.: БІНОМ. Лабораторія знань, 2007. «Математичні засади інформатики» і має інтегрований, міждисциплінарний характер, матеріал курсу розкриває взаємозв'язок математики та інформатики, показує, як розвиток однієї з цих наукових галузей стимулював розвиток іншої.

Курс орієнтований на учнів 9 класів загальноосвітньої школи, які бажають розширити свої уявлення про математику в інформатиці та інформатику з математики.

Курс розрахований на учнів, які мають базову підготовку з інформатики; може вивчатися як за наявності комп'ютерної підтримки, і у безмашинному варіанті.

Цілі курсу:

формування у випускників школи засад наукового світогляду;

забезпечення наступності між загальною та професійною освітою за рахунок більш ефективної підготовки випускників школи до освоєння програм вищої професійної освіти;

створення умов для саморозвитку та самовиховання особистості.

Завдання курсу:

сформувати в учнів системне уявлення про теоретичну базу інформаційних та комунікаційних технологій;

показати взаємозв'язок та взаємовплив математики та інформатики;

прищепити учням навички, потрібні більшістю видів сучасної діяльності (налагодження контактів іншими членами колективу, планування та організація спільної діяльності тощо).

сформувати вміння розв'язання дослідницьких завдань;

сформувати вміння розв'язання практичних завдань, які вимагають отримання закінченого продукту;

розвинути здатність до самонавчання.

Курсу відводиться по 3 години на тиждень, всього 96 навчальних годин.

Курс «Математичні основи інформатики» має блочно-модульну структуру, навчальний посібник складається із 6 розділів, які можна вивчати у довільному порядку.

ТЕМАТИЧНЕ ТА ПІВРОЧНЕ ПЛАНУВАННЯ

Модуль 1. Системи числення

Тема «Системи числення» зазвичай вивчається в базовому курсі інформатики, тому школярі мають певні знання та навички, в основному, переведення цілих десяткових чисел у двійкову систему і назад.

Цілі вивчення теми:

розкрити принципи побудови систем числення та насамперед позиційних систем;

вивчити властивості позиційних систем числення;

показати, на яких ідеях засновані алгоритми переведення чисел з однієї системи числення до іншої;

розкрити зв'язок між системою числення, що використовується для кодування інформації в комп'ютері, та архітектурою комп'ютера;

ознайомити з основними недоліками використання двійкової системи у комп'ютері;

розповісти про системи числення, відмінних від двійкової використовуваних у комп'ютерних системах.

У даному модулі розібрано 145 завдань — 103 завдання у навчальному посібнику та 42 завдання у самостійних та контрольних роботах (методичний посібник).

Модуль 2. Подання інформації на комп'ютері

Розробка сучасних способів оцифрування інформації – один із яскравих прикладів співпраці фахівців різних профілів: математиків, біологів, фізиків, інженерів, IT-фахівців, програмістів. Широко поширені формати зберігання природної інформації (МРЗ, JPEG, MPEG та інших.) використовують у процесі стиску складні математичні методи. У розділі 2 не вводиться «складна математика», а лише розповідається про шляхи, сучасні підходи до подання інформації в комп'ютері.

Питання, що розглядаються в даному модулі, практично не представлені у базовому курсі інформатики.

Цілі вивчення теми:

досить докладно показати учням методи комп'ютерного уявлення цілих і речових чисел;

виявити загальні інваріанти подання текстової, графічної та звукової інформації;

ознайомити з основними теоретичними підходами до вирішення проблеми стиснення інформації.

Матеріал цього розділу, як і всього курсу загалом, надмірний. У модулі 2 докладно розібрано 138 завдань (разом із прикладами та завданнями з навчального посібника та завданнями перевірочних робіт).

Модуль 3. Введення у алгебру логіки

Цілі вивчення теми:

досить суворо викласти основні поняття алгебри логіки, які у інформатиці;

показати взаємозв'язок викладеної теорії з практичними потребами інформатики та математики;

систематизувати знання, раніше отримані на цю тему.

У навчальному посібнику докладно розглянуто рішення 124 завдань.

Модуль 4. Елементи теорії алгоритмів

Тема «Алгоритмізація» входить до базового курсу інформатики, і, як правило, школярі знайомі з такими поняттями як «алгоритм», «виконавець», «середовище виконавця» та ін. Багато хто вміє і програмувати. При вивченні даного модуля найбільша увага приділяється розділам (параграфам), зміст яких не входить до базового курсу інформатики. Метою вивчення цієї теми не є навчити учнів складати алгоритми. Алгоритмічність мислення формується протягом усього періоду навчання у школі. Проте щодо цієї теми вирішується багато завдань складання алгоритмів і оцінку їх обчислювальної складності, оскільки вивчення окремих розділів теорії алгоритмів без розробки самих алгоритмів неможливо.

Цілі вивчення теми:

формування уявлення про передумови та етапи розвитку галузі математики «Теорія алгоритмів» та безпосередньо самої обчислювальної техніки;

знайомство з формальним (математично суворим) визначенням алгоритму на прикладах машин Тьюринга чи Посту;

знайомство з поняттями "обчислювана функція", "алгоритмічно нерозв'язні задачі" та "складність алгоритму".

У цьому модулі розібрано 82 завдання.

Модуль 5. Основи теорії інформації

Мета вивчення теми:

познайомити учнів із сучасними підходами до подання, вимірювання та стиснення інформації, заснованими на математичній теорії інформації;

показати практичне застосування цього матеріалу.

Модуль 6. Математичні основи обчислювальної геометрії та комп'ютерної графіки

Мета вивчення теми: познайомити учнів з галуззю інформатики, що швидко розвивається, — обчислювальною геометрією; показати, що вона лежить в основі алгоритмів комп'ютерної графіки.

У цьому модулі розглядаються деякі алгоритми розв'язання геометричних завдань. Такі завдання виникають у комп'ютерній графіці, проектуванні інтегральних схем, технічних пристроїв та ін. Вихідними даними в таких завданнях можуть бути безліч точок, набір відрізків, багатокутник і т.п.

Тема даного модуля досить складна сприйняття. Трактування таких понять, як "інформація", "вимірювання інформації", в даному модулі дається зовсім на іншому рівні, ніж це робиться в базовому курсі інформатики. Крім того, для повного освоєння пропонованих матеріалів потрібна досить висока математична підготовка; зокрема, бажане знайомство школярів із поняттям логарифму. Саме тому даний модуль пропонується вивчати не на початку курсу, а ближче до кінця, коли учні в курсі математики з логарифмами вже познайомляться.

Частина матеріалу, наприклад формула Шеннона або її висновок, може бути опущена, а час, що вивільнився, використано для більш докладного вивчення основних елементів теорії інформації, що мають важливе значення в інформатиці. Такими елементами є формула Хартлі, закон адитивності інформації, зв'язок алфавітного підходу до вимірювання інформації з підходом, що базується на аналізі невизначеності знання про той чи інший предмет, оптимальне кодування інформації.

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

У даному модулі розібрано 33 завдання — 24 у навчальному посібнику та 9 завдань практичної роботи.

Матеріали відповідного розділу підручника не входять практично до жодного підручника з базового курсу інформатики. А від професійних книг з цієї тематики їх відрізняє відносна доступність викладу та застосування математичного апарату, що практично не виходить за рамки шкільного курсу елементарної математики.

МЕТОДИ Викладання та навчання

В основу роботи з учнями з вивчення курсу «Математичні основи інформатики» покладено методику, що базується на наступних принципах навчання:

принцип навчання високому рівні проблеми;

принцип провідної ролі теоретичних знань;

принцип концентрованості організації навчального процесу та навчального матеріалу;

принцип групової чи колективної взаємодії;

принцип поліфункціональності навчальних завдань

Ця методика спирається на положення когнітивної психології:

у процесі навчання виникають не знання, вміння та навички, які психологічний еквівалент — когнітивні структури, т. е. схеми, крізь які учень дивиться світ, бачить і сприймає його;

провідною детермінантою поведінки людини не стимул як такої, а знання навколишньої людини дійсності, засвоєння якого відбувається у процесі психічного відображення;

з усіх здібностей людини функція мислення є керівною, що інтегрує діяльність сприйняття, уваги та пам'яті;

для всебічного розвитку мислення у зміст навчання крім матеріалів, що безпосередньо засвоюються учнями, необхідно включати завдання та проблеми теоретичного та практичного характеру, вирішення яких потребує самостійного мислення та уяви, численних інтелектуальних операцій, творчого підходу та наполегливих пошуків;

для розвитку мислення когнітивна психологія рекомендує використовувати ефект «напруженої потреби».

МЕТОДИ ОЦІНЮВАННЯ РІВНЯ ДОСЯГНЕННЯ УЧНІВ

Навчання високому рівні складності супроводжується дотриманням заходи проблеми, що у контролі якості засвоєння. У систему перевірки та контролю включені різноманітні способи контролю, але в будь-якому випадку система повинна володіти функцією, що розвиває по відношенню до учнів. Для цього потрібне виконання наступних умов:

жодне завдання не повинно бути залишено без перевірки та оцінювання з боку викладача;

результати перевірки повинні повідомлятись негайно;

школяр повинен максимально брати участь у процесі перевірки виконаного ним завдання.

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

Практична реалізація принципу вивчення швидкому передбачає постійний контроль за знаннями і вміннями учнів, оскільки без переконаності у повному засвоєнні матеріалу всіма учнями немає сенсу рухатися вперед.

Література

Математичні засади інформатики. Елективний курс: Методичний посібник / Є. В. Андрєєва, Л. Л. Босова, І. Н. Фаліна – М.: БІНОМ. Лабораторія знань, 2007. – 312 с.: іл.

Математичні засади інформатики. Елективний курс: Навчальний посібник / Є. В. Андрєєва, Л. Л. Босова, І. Н. Фаліна – 2-ге вид., Випр. - М: БІНОМ. Лабораторія знань, 2007. – 328 с.: іл.

Інформатики. Програми для загальноосвітніх установ. 2-11 класи: методичний посібник/упорядник М. Н. Бородін. - М: БІНОМ. Лабораторія знань, 2010. – 584 с.: іл. - (Програми та планування).

Календарно-тематичне планування - 9 клас

Математичні засади інформатики. Андрєєва Є.В., Босова Л.Л., Фаліна І.М.

М.: 2005. – 328 с.

Навчальний посібник входить до УМК для старших класів поряд з метоним посібником і хрестоматією. Матеріал розкриває взаємозв'язок математики та інформатики, показує, як розвиток однієї з цих наукових галузей стимулював розвиток іншої. Дається поглиблене уявлення про математичний апарат, що використовується в інформатиці, показується, як теоретичні результати, отримані в математиці, послужили джерелом нових ідей та результатів у теорії алгоритмів, програмування та інших розділах інформатики.

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

Формат: pdf

Розмір: 1 3, 7Мб

Завантажити: drive.google

Зміст

Глава 1. Системи числення ................................................. 11

§ 1.1. Позиційні системи числення. Основні

Визначення................................................. .................... 13

Запитання та завдання............................................... ............ 19

§ 1.2. Єдиність подання чисел у Р-ичних

системах числення................................................ ......... 20

Запитання та завдання............................................... ....... ... 24

§1.3. Подання довільних чисел у позиційних

системах числення................................................ ......... 25

1.3.1. Розгорнута та згорнута форми запису............ 25

1.3.2. Перерахування натуральних чисел 26

1.3.3. Подання звичайних десяткових дробів

У Р-нічних системах числення 28

Запитання та завдання............................................... ............ 30

§1.4. Арифметичні операції у Р-ичних системах

Обчислення................................................. ........................ 31

1.4.1. Додавання................................................. ......... 31

1.4.2. Віднімання................................................. .... 33

1.4.3. Множення................................................. ...... 33

1.4.4. Поділ................................................. ............ 35

Запитання та завдання............................................... ............ 37

§1.5. Переклад чисел із Р-ичної системи числення

у десяткову................................................ ................... 38

1.5.1. Переклад цілих Р - чисел ..................... . . 38

1.5.2. Переклад кінцевих Р-кових дробів 40

1.5.3. Переклад періодичних Р-ичних дробів......... 42

Запитання та завдання............................................... ........... 44

§1.6. Переклад чисел із десяткової системи числення

в Р-ічну.............................................. ......................... 44

1.6.1. Два способи переведення цілих чисел............ 44

1.6.2. Переклад кінцевих десяткових дробів............ 47

Запитання та завдання............................................... ............ 49

§ 1.7. Змішані системи числення...................................... 50

Запитання та завдання............................................... ........... 54

§ 1.8. Системи числення та архітектура комп'ютерів........... 54

1.8.1. Використання врівноваженої потрійної системи

Обчислення 56

1.8.2. Використання фібоначчієвої системи числення 58

1.8.3. Недвійкові комп'ютерні арифметики 60

Запитання та завдання............................................... .......... 61

Висновок................................................. .............................. 61

Глава 2. Подання інформації на комп'ютері ....... 63

§ 2.1. Подання цілих чисел........................................... 65

2.1.1. Подання цілих позитивних чисел... 66

2.1.2. Подання цілих негативних чисел... 68

2.1.3. Перелік чисел у цілісній комп'ютерній

арифметиці 71

2.1.4. Особливості реалізації арифметичних операцій

у кінцевому числі розрядів 73

Запитання та завдання............................................... .......... 74

§2.2. Подання дійсних чисел............................... 74

2.2.1. Нормалізований запис числа............................ 75

2.2.2. Подання дійсних чисел

у форматі з плаваючою комою.......................... 80

2.2.3. Виконання арифметичних операцій

над речовими числами............................... 81

2.2.4. Особливості реалізації речовинної
комп'ютерної арифметики......................... 84

Запитання та завдання............................................... .......... 88

§2.3. Подання текстової інформації............................. 89

Запитання та завдання............................................... ........... 95

§ 2.4. Подання графічної інформації........................ 96

2.4.1. Загальні підходи до подання

у комп'ютері інформації природного
походження................................................. .... 97

2.4.2. Векторне і растрове графічне представлення.

Інформації................................................ 102

2.4.3. Квантування кольору............................................. 104

2.4.4. Колірна модель RGB ....................................... 107

2.4.5. Колірна модель CMYK ................................... 112

2.4.6. Колірна модель HSB ....................................... 115

Запитання та завдання............................................... ........ 119

§ 2.5. Подання звукової інформації............................ 120

2.5.1. Поняття звукозапису.......................................... 122

2.5.2. Імпульсно-кодова модуляція.......................... 123

2.5.3. Формат MIDI ..................................................... 127

2.5.4. Принципи комп'ютерного відтворення

Звуку................................................. ................. 128

Запитання та завдання............................................... ........ 129

§2.6. Методи стиснення цифрової інформації.......................... 130

2.6.1. Алгоритми оборотних методів........................ 132

2.6.2. Методи стиснення з регульованою втратою інформації 141

Запитання та завдання............................................... ........ 145

Висновок................................................. ........................... 145

Розділ 3. Введення в алгебру логіки ................................ 147

§3.1. Алгебра логіки. Поняття висловлювання ................ 148

Запитання та завдання............................................... ........ 151

§ 3.2. Логічні операції. Таблиці істинності 152

Запитання та завдання............................................... ........ 162

§ 3.3. Логічні формули. Закони алгебри логіки.............. 164

Запитання та завдання............................................... ........ 167

§ 3.4. Методи вирішення логічних завдань.............................. 168

Запитання та завдання............................................... ........ 172

§ 3.5. Алгебра перемикальних схем 173

Запитання та завдання............................................... ........ 175

§ 3.6. Булеві функції................................................ ............ 176

Запитання та завдання............................................... ........ 178

§ 3.7. Канонічні форми логічних формул.

Теорема про СДНФ ......................................................... 178

Запитання та завдання............................................... ........ 184

§ 3.8. Мінімізація булевих функцій у класі

диз'юнктивних нормальних форм............................... 185

Практичні завдання................................................ .. 189

§ 3.9. Повні системи булевих функцій............................... 190

Запитання та завдання............................................... ........ 192

§ 3.10. Елементи схемотехніки. Логічні схеми.............. 193

Запитання та завдання............................................... ........ 197

Висновок................................................. ............................ 197

Глава 4. Елементи теорії алгоритмів ........................... 199

§4.1. Концепція алгоритму. Властивості алгоритмів..................... 200

Запитання та завдання............................................... ........ 208

§ 4.2. Уточнення концепції алгоритму. Машина Т'юрінга. . 209

4.2.1. Необхідність уточнення поняття алгоритму. 209

4.2.2. Опис машини Тьюринга.............................. 212

4.2.3. Приклади машин Т'юрінга................................ 215

4.2.4. Формальний опис алгоритму. Математичне

опис машини Тьюринга.........................................218

Запитання та завдання............................................... ......... 220

§4.3. Машина посту як уточнення поняття алгоритму. . . 220

Запитання та завдання............................................... ........ 223

§4.4. Алгоритмічно нерозв'язні задачі

та обчислювані функції............................................... .. 224

Запитання та завдання............................................... ........ 229

§4.5. Поняття складності алгоритму....................................... 230

Запитання та завдання............................................... ........ 234

§ 4.6. Аналіз алгоритмів пошуку............................................ 234

4.6.1. Послідовний пошук у невпорядкованому масиві 235

4.6.2. Алгоритм бінарного пошуку в упорядкованому масиві 237

Запитання та завдання............................................... ........ 238

§ 4.7. Аналіз алгоритмів сортування..................................... 238

4.7.1. Обмінне сортування методом «бульбашка». . . 239

4.7.2. Сортування вибором.......................................... 241

4.7.3. Сортування вставками........................................ 243

4.7.4. Сортування злиттям......................................... 244

Запитання та завдання............................................... ......... 247

Висновок................................................. ............................ 248

Глава 5. Основи теорії інформації .............................. 249

§ 5.1. Концепція інформації. Кількість інформації.

Одиниці виміру інформації.................................. 250

Запитання та завдання............................................... ......... 254

§5.2. Формула Хартлі визначення кількості

Інформація................................................. .................. 254

Запитання та завдання............................................... ......... 260

§ 5.3. Застосування формули Хартлі 261

Запитання та завдання............................................... ......... 265

§5.4. Закон адитивності інформації. Алфавітний

підхід до вимірювання інформації.................................. 266

Запитання та завдання............................................... ......... 269

§5.5. Інформація та ймовірність. Формула Шеннона............. 269

Запитання та завдання............................................... ......... 276

§5.6. Оптимальне кодування інформації

та її складність............................................... ............... 277

Запитання та завдання............................................... ......... 280

Висновок................................................. ............................ 281

Глава 6. Математичні основи обчислювальної

геометрії та комп'ютерної графіки ................ 283

§ 6.1. Координати та вектори на площині............................ 285

Запитання та завдання............................................... ........ 292

§ 6.2. Способи опису ліній на площині 292

6.2.1. Загальне рівняння прямої ................................... 292

6.2.2. Нормоване рівняння прямої...................... 294

6.2.3. Параметричні рівняння прямої, променя, відрізка 296

6.2.4. Способи опису кола........................... 297

Запитання та завдання............................................... ........ 298

§6.3. Завдання комп'ютерної графіки на взаємне

розташування точок та фігур......................................... 298

і проходить через задану точку.................. 298

6.3.2. Розташування точки щодо прямої,

променя або відрізка............................................... 299

6.3.3. Взаємне розташування прямих, відрізків, променів 301

6.3.4. Взаємне розташування кола

і прямий................................................ ............. 303

6.3.5. Взаємне розташування двох кіл. . . 305
Запитання та завдання............................................... ......... 307

§ 6.4. Багатокутники................................................. ........... 307

6.4.1. Перевірка опуклості багатокутника............... 308

6.4.2. Перевірка належності точки внутрішньої

області багатокутника 308

6.4.3. Обчислення площі простого багатокутника. 310

Запитання та завдання............................................... ......... 311

§6.5. Геометричні об'єкти в просторі 312

6.5.1. Основні формули............................................ 312

6.5.2. Визначення перетину прямої лінії

і трикутника у просторі........................... 314

6.5.3. Обертання точки навколо заданої прямої

в просторі................................................ ... 315

Запитання та завдання............................................... ........ 317

Висновок................................................. ........................... 318

Додаток................................................. ........................ 319

Предметний покажчик................................................ ...... 320

Вступ 3

1 Теорія графів 5

1.1 Поняття та термінологія теорії графів 5

1.2 Деякі завдання теорії графів 6

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

Висновок 27

Список використаної літератури 30

Вступ

У широкому сенсі інформатика (пор. зі подібними за звучанням і походженням нім. Informatik і фр. Informatique, на противагу традиційному англомовному терміну англ. computer science - наука про комп'ютери - в США або англ. computing science - обчислювальна наука - у Британії є наука про обчислення, зберігання та обробку інформації Вона включає дисципліни, що так чи інакше стосуються обчислювальних машин: як абстрактні, на кшталт аналізу алгоритмів, так і досить конкретні, наприклад, розробка мов програмування.

Згідно з тезою Черча - Тьюринга, всі відомі типи обчислювальних машин якісно еквівалентні у своїх можливостях: будь-яка дія, що здійснюється на одній обчислювальній машині, також здійсненна і на іншій. Тезу іноді подають як фундаментальний принцип інформатики, звертаючи особливу увагу на машину Тьюринга і машину фон-нейманівської архітектури, оскільки вони мають явну схожість з більшістю комп'ютерів, що нині діють. У рамках сучасної інформатики вчені вивчають також інші типи машин, як практично здійсненні (такі, як паралельні і квантові комп'ютери), а й суто абстрактні математичні моделі (наприклад, машина випадкового доступу, що має нескінченне число регістрів).

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

Окремою наукою інформатику було визнано лише 1970-х; раніше вона розвивалася у складі математики, електроніки та інших технічних наук. Деякі початки інформатики можна знайти навіть у лінгвістиці. З моменту свого визнання окремою наукою інформатика розробила власні методи та термінологію.

Перший факультет інформатики було засновано 1962 року в університеті Пердью (Purdue University). Сьогодні факультети та кафедри інформатики є у більшості університетів світу.

Вищою нагородою за заслуги у сфері інформатики є премія Тьюринга.

1 Теорія графів

Теорія графів - розділ дискретної математики, що вивчає властивості графів. У загальному сенсі граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин

G = (R, V),

де V є підмножина будь-якої лічильної множини,

а R - підмножина V×V.

Мал. 1. Граф із шістьма вершинами та сімома ребрами

Теорія графів знаходить застосування, наприклад, у геоінформаційних системах (ГІС). Існуючі або новопроектовані будинки, споруди, квартали і т. п. розглядаються як вершини, а дороги, що з'єднують їх, інженерні мережі, лінії електропередач і т. п. - як ребра. Застосування різних обчислень, які виробляються на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут (див. рис. 1).

Термінологія теорії графів досі не визначена суворо. Зокрема в монографії Гудман, Хідетнієм, 1981 сказано «У програмістському світі немає єдиної думки про те, який із двох термінів "граф" чи "мережа". Ми вибрали термін "мережа", оскільки він, мабуть, найчастіше зустрічається в прикладних областях».

* Сім мостів Кенігсберга - один з перших результатів теорії графів, опублікований Ейлером в 1736.

* Проблема чотирьох фарб - була сформульована в 1852 році, але доказ отримано лише в 1976 (достатньо 4-х фарб для карти на сфері (площині)).

* Завдання комівояжера - одне з найбільш відомих NP-повних завдань.

* Завдання про клік - ще одне NP-повне завдання.

* Знаходження мінімального стягуючого дерева.

Завдання комівояжераполягає у відшуканні найвигіднішого маршруту, що проходить через зазначені міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Як правило вказується, що маршрут повинен проходити через кожне місто лише один раз, у такому разі Вибір здійснюється серед гамільтонових циклів.

Існує маса різновидів узагальненої постановки задачі, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична і симетрична.

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

Усі ефективні (що скорочують повний перебір) методи розв'язання задачі комівояжера – методи евристичні. У більшості евристичних методів не найефективніший маршрут, а наближене рішення. Найчастіше затребувані звані any-time алгоритми, тобто поступово поліпшують деяке поточне наближене рішення.

Завдання комівояжера є NP-повне завдання. Часто у ньому проводять обкатку нових підходів до евристичного скорочення повного перебору.

Назвемо мовою безліч слів над алфавітом? Завданням тут є визначення того, належить це слово мові чи ні. Мова 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) + m x(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) є природними умовами на введені змінні.

Покажемо, що умови (3) є необхідними та достатніми умовами існування лише одного циклу.

Справді, нехай це не так і знайдеться підцикл із кількістю міст 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 0.

Нехай 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 року. У цьому листі Ейлер пише про те, що він зміг знайти правило, користуючись яким легко визначити, чи можна пройти всіма мостами, не проходячи двічі по одному з них (у випадку семи мостів Кенігсберга це неможливо).

На спрощеній схемі частини міста (графі) мостам відповідають лінії (ребра графа), частинам міста - точки з'єднання ліній (вершини графа). У ході міркувань Ейлер дійшов таких висновків:

Число непарних вершин (вершин, до яких веде непарне число ребер) графа завжди парне. Неможливо накреслити граф, який мав би непарну кількість непарних вершин.

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

Граф із більш ніж двома непарними вершинами неможливо накреслити одним розчерком.

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

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

Мал. 4. Граф кенігсберзьких мостів

Створена Ейлером теорія графів знайшла дуже широке застосування: наприклад, її використовують щодо транспортних і комунікаційних систем, зокрема, для маршрутизації даних у Інтернеті.

Проблема чотирьох фарб- математичне завдання, запропоноване Ф. Госрі (англ. Francis Guthrie) у 1852 році.

З'ясувати, чи можна будь-яку, розташовану на сфері карту, розфарбувати чотирма фарбами так, щоб будь-які дві області, що мають спільну ділянку кордону у вигляді дуги, розфарбували в різні кольори.

К. Аппель та В. Хакен довели у 1976 р., що так можна розфарбувати будь-яку карту. Це була перша велика математична теорема, на доказ якої був застосований комп'ютер. Незважаючи на подальші спрощення, доказ практично неможливо перевірити без використання комп'ютера.

Розфарбовуючи географічну карту, природно користуватися по можливості меншою кількістю кольорів, проте так, щоб дві країни, що мають спільну частину кордону (не тільки загальну точку), були пофарбовані по-різному. В 1852 Френсіс Гутрі (Guthrie), складаючи карту графств Англії, звернув увагу, що для такої мети цілком вистачає чотирьох фарб. Його брат, Фредерік, повідомив про це спостереження відомого математика О. Де Моргана (DeMorgan), а той – математичної громадськості. Точне формулювання гіпотези опубліковано А. Келлі (Cayley, 1878).

Перший доказ з'явився через рік і належало В. Кемпе (Kempe). Одинадцять років потому П. Хівуд (Heawood) виявив у ньому помилку. За першим помилковим доказом було безліч інших. У цьому плані проблема чотирьох фарб поступалася лише знаменитої проблемі Ферма. До середини 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) – число ребер, що становлять межу 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 сходиться рівно п'ять ребер. Розглянемо граф H É G, що складається з тих п'яти вершин, куди приходять ребра, що виходять з a і ребер, що з'єднують їх (у G). У графі H обов'язково знайдуться дві вершини, не з'єднані руба. В іншому випадку в п'ятикутнику H буде C 5 2 = 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, u k R3 – два вектори, їх векторний твір u i u має довжину а напрям визначається за правилом буравчика чи правої руки. Легко переконатися в тому, що цей твір не асоціативний, тобто твір u1 i u2 i ... i un взагалі не визначено, якщо в ньому не розставлені дужки. Дійсно, наприклад, 0 = i i (j i j) (i i j) i j = - 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-розмальовку. Доказ еквівалентності останньої теореми проблеми чотирьох фарб дано Л. Кауфманом і пояснено на пальцях. Тут ми лише коротко пояснимо зв'язок цих завдань.

По-перше, до чого тут графи? Графічно асоціацію можна уявляти як дерева, тобто графа спеціального вигляду, влаштованого наступним чином. Добутку будь-якої пари u i u відповідає пара ребер (гілок), що мають загальну вершину, при цьому кінці гілок відповідають співмножникам, а загальний початок – твору. Крок за кроком виконуючи дії, вказані в асоціації дужками, приходимо до кореня цього дерева, що відповідає результату виконання всіх перемножень у заданій асоціації. У верхній частині рис. 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-розмальовки ребер еквівалентні. Точніше, справедлива

Теорема 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) багатокутних областей, що не перекриваються". Тим часом це твердження не належить до аксіом або шкільних теорем плоскої геометрії, і його потрібно доводити. Відповідна теорема, сформульована К. Жорданом, доводиться дуже непросто, проте основні труднощі пов'язані з тим, як слід розуміти слова типу "розрізає", інтуїтивно цілком ясні, але важко піддається формалізації. У світлі цього зауваження стає вже не зовсім зрозумілим, чи доведено теорему про п'ять фарб або ми повірили правдоподібним міркуванням, заснованим на інтуїтивних уявленнях про властивості геометричних фігур.

Довгий час ідеалом математичної суворості були формулювання та докази Евкліда, в яких здійснювалася програма виведення теорем з аксіом за певними правилами (метод дедукції, що дозволяє отримувати неочевидні твердження з очевидних за допомогою ряду явно пред'явлених елементарних, очевидно законних, висновків). Цей зразок суворості і в наш час недосяжний у курсі шкільної математики, але для сучасної чистої математики стандарти Евкліда недостатні. Евклід, мабуть, не замислювався над тим, чому пряма ділить площину на дві частини (і що це означає), він не визначав поняття "між", вважаючи це поняття очевидним і т.д. Більшість відповідних тверджень доведено або включено в аксіоматику геометрії тільки в останню сотню років. Формальні висновки з нової системи аксіом стали набагато довшими, ніж в античні часи.

Важко навіть уявити довжину повного виведення теореми про п'ять фарб відповідно до сучасних стандартів математичної логіки та системи аксіом геометрії. Але абсолютно точно, що таке міркування ніхто ніколи не робив через марність цього заняття: формальні висновки практично не піддаються перевірці в силу властивостей людської психіки: крім їх набагато більшої (порівняно зі звичними міркуваннями) довжини їх свідоме засвоєння йде набагато повільніше. Тому зазвичай задовольняються впевненістю у цьому, що формальний висновок можливий у принципі.

У формулі Ейлера, наприклад, математики не сумніваються. Загалом прийняття доказу є певний соціальний акт. Визначний алгебраїст Ю.І. Манін у своїй книзі "Доказне і недоказове" пише з цього приводу: "...відсутність помилок у математичній роботі (якщо вони не виявлені), як і в інших природничих науках, часто встановлюється за непрямими даними: мають значення відповідність із загальними очікуваннями, використання аналогічних аргументів інших роботах, розглядання " під мікроскопом " окремих ділянок докази, навіть репутація автора, словом, відтворюваність у сенсі. " Незрозумілі " докази можуть зіграти дуже корисну роль, стимулюючи пошуки доступніших міркувань."

Саме така історія відбувається і з доказом теореми про чотири фарби. Нещодавно з'явився новий доказ, причому та частина, яка виконана не на комп'ютері, вже піддається перевірці. Однак комп'ютерна частина все ще залишається скоріше предметом віри. Адже навіть перевірка роздруківок всіх програм і всіх вхідних даних не може гарантувати від випадкових збоїв або навіть від прихованих вад електроніки (згадаймо, що помилки при виконанні поділу в першій версії процесора 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.

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

Теоретично алгоритмів NP-повні завдання - це клас завдань, які у класі NP (тобто яких поки що не знайдено швидких алгоритмів рішення, але перевірка того, чи це рішення правильним, проходить швидко), яких зводяться всі завдання класу NP. Це означає, що якщо знайдуть швидкий алгоритм для вирішення будь-якого з NP-повних завдань, будь-яке завдання з класу NP може бути вирішене швидко.

Якщо не вдатися до хитрощів зістрибнути у воду і доплисти до протилежного берега, що дозволить вирішити завдання з мостами, але, на жаль, змінить умову завдання з графами.

Однак із доказу Хівуд зрозумів, що п'яти фарб справді достатньо. Тим не менш, для будь-якої конкретної карти вистачало чотирьох фарб!

Марков А.А. Елементи математичної логіки. М: Вид-во МДУ, 2004. С. 211.

Кук Д., Бейз Р. Комп'ютерна математика. М., Наука, 2000. С. 156.

Турецький В.Я. Математика та інформатика. Єкатеринбург: Пропаганда, 2002. С. 109.

Симонович З., Євсєєв Р., Алексєєв А. Загальна інформатика. М.: Справа, 1999. З. 231.

Гладкі Б. А. Від абака до комп'ютера. Томськ: Вид-во НТЛ, 2005. С. 87.

Назва: Математичні основи інформатики - Елективний курс - Навчальний посібник.

Навчальний посібник входить до УМК для старших класів поряд з методичним посібником та хрестоматією.
Матеріал розкриває взаємозв'язок математики та інформатики, показує, як розвиток однієї з цих наукових галузей стимулював розвиток іншої. Дається поглиблене уявлення про математичний апарат, який використовується в інформатиці, демонструється, як результати, отримані в математиці, послужили джерелом нових ідей та результатів у теорії алгоритмів, програмування та інших розділах інформатики.

Зміст
Від авторів. 8
Глава 1. Системи числення. 11
§1.1. Позиційні системи числення. Основні визначення. 13
Запитання та завдання. 19
§1.2. Єдиність уявлення чисел у Р-ичних системах числення. 20
Запитання та завдання. 24
§1.3. Подання довільних чисел у позиційних системах числення. 25
1.3.1. Розгорнута та згорнута форми запису. 25
1.3.2. Перерахування натуральних чисел. 26
1.3.3. Подання звичайних десяткових дробів у Р-ичних системах числення. 28
Запитання та завдання. 30
§1.4. Арифметичні операції у Р-ичних системах числення. 31
1.4.1. Додавання. 31
1.4.2. Віднімання. 33
1.4.3. множення. 33
1.4.4. Розподіл. 35
Запитання та завдання. 37
§1.5. Переклад чисел із Р-ичної системи числення до десяткової. 38
1.5.1. Переклад цілих Р-чисел. 38
1.5.2. Переклад кінцевих дробів. 40
1.5.3. Переклад періодичних Р-шних дробів. 42
Запитання та завдання. 44
§1.6. Переклад чисел із десяткової системи числення до Р-їчної. 44
1.6.1. Два способи переведення цілих чисел. 44
1.6.2. Переклад кінцевих десяткових дробів. 47
Запитання та завдання. 49
§ 1.7. Змішані системи числення. 50
Запитання та завдання. 54
§ 1.8. Системи числення та архітектура комп'ютерів. 54
1.8.1. Використання врівноваженої потрійної системи числення. 56
1.8.2. Використання фібоначчієвої системи числення. 58
1.8.3. Недвійкові комп'ютерні математики. 60
Запитання та завдання. 61
Висновок. 61
Глава 2. Подання інформації на комп'ютері. 63
§ 2.1. Подання цілих чисел. 65
2.1.1. Подання цілих позитивних чисел. 66
2.1.2. Подання цілих негативних чисел. 68
2.1.3. Перерахування чисел у цілісній комп'ютерній арифметиці. 71
2.1.4. Особливості реалізації арифметичних операцій у кінцевому числі розрядів. 73
Запитання та завдання. 74
§2.2. Подання дійсних чисел. 74
2.2.1. Нормалізований запис числа. 75
2.2.2. Подання дійсних чисел у форматі з плаваючою комою. 80
2.2.3. Виконання арифметичних операцій над речовими числами. 81
2.2.4. Особливості реалізації речової комп'ютерної арифметики. 84
Запитання та завдання. 88
§ 2.3. Подання текстової інформації. 89
Запитання та завдання. 95
§ 2.4. Подання графічної інформації. 96
2.4.1. Загальні підходи до представлення на комп'ютері інформації природного походження. 97
2.4.2. Векторні і растрові подання графічної інформації. 102
2.4.3. Квантування кольорів. 104
2.4.4. Колірна модель RGB. 107
2.4.5. Колірна модель CMYK. 112
2.4.6. Колірна модель HSB. 115
Запитання та завдання. 119
§ 2.5. Подання звукової інформації. 120
2.5.1. Концепція звукозапису. 122
2.5.2. Імпульсно-кодова модуляція. 123
2.5.3. Формат MIDI. 127
2.5.4. Принципи комп'ютерного відтворення звуку. 128
Запитання та завдання. 129
§ 2.6. Методи стиску цифрової інформації. 130
2.6.1. Алгоритми оборотних методів. 132
2.6.2. Методи стиснення із регульованою втратою інформації. 141
Запитання та завдання. 145
Висновок. 145
Глава 3. Введення у алгебру логіки. 147
§ 3.1. Алгебра логіки. Концепція висловлювання. 148
Запитання та завдання. 151
§ 3.2. Логічні операції. Таблиці істинності. 152
Запитання та завдання. 162
§ 3.3. Логічні формули. Закони логіки алгебри. 164
Запитання та завдання. 167
§ 3.4. Методи розв'язання логічних завдань. 168
Запитання та завдання. 172
§ 3.5. Алгебра перемикальних схем. 173
Запитання та завдання. 175
§ 3.6. Булеві функції. 176
Запитання та завдання. 178
§ 3.7. Канонічні форми логічних формул. Теорема про СДНФ. 178
Запитання та завдання. 184
§ 3.8. Мінімізація булевих функцій у класі диз'юнктивних нормальних форм. 185
Практичні завдання. 189
§ 3.9. Повні системи булевих функцій. 190
Запитання та завдання. 192
§ 3.10. Елементи схемотехніки. Логічні схеми. 193
Запитання та завдання. 197
Висновок. 197
Розділ 4. Елементи теорії алгоритмів. 199
§ 4.1. Концепція алгоритму. Властивості алгоритмів. 200
Запитання та завдання. 208
§ 4.2. Уточнення концепції алгоритму. Машина Т'юрінга. 209
4.2.1. Необхідність уточнення поняття алгоритму. 209
4.2.2. Опис машини Тьюринга. 212
4.2.3. Приклади машин Т'юрінга. 215
4.2.4. Формальний опис алгоритму. Математичне опис машини Тьюринга. 218
Запитання та завдання. 220
§4.3. Машина посту як уточнення поняття алгоритму. 220
Запитання та завдання. 223
§4.4. Алгоритмічно нерозв'язні завдання та функції, що обчислюються. 224
Запитання та завдання. 229
§4.5. Поняття складності алгоритму. 230
Запитання та завдання. 234
§ 4.6. Аналіз алгоритмів пошуку. 234
4.6.1. Послідовний пошук у невпорядкованому масиві. 235
4.6.2. Алгоритм бінарного пошуку у впорядкованому масиві. 237
Запитання та завдання. 238
§ 4.7. Аналіз алгоритмів сортування. 238
4.7.1. Обмінне сортування методом «бульбашка». 239
4.7.2. Сортування вибором. 241
4.7.3. Сортування вставками. 243
4.7.4. Сортування злиттям. 244
Запитання та завдання. 247
Висновок. 248
Розділ 5. Основи теорії інформації. 249
§ 5.1. Концепція інформації. Кількість інформації. Одиниці виміру інформації. 250
Запитання та завдання. 254
§ 5.2. Формула Хартлі визначення кількості інформації. 254
Запитання та завдання. 260
§ 5.3. Застосування формули Хартлі. 261
Запитання та завдання. 265
§ 5.4. Закон адитивності інформації. Алфавітний підхід до виміру інформації. 266
Запитання та завдання. 269
§5.5. Інформація та ймовірність. Формула Шеннона. 269
Запитання та завдання. 276
§ 5.6. Оптимальне кодування інформації та її складність. 277
Запитання та завдання. 280
Висновок. 281
Глава 6. Математичні основи обчислювальної геометрії та комп'ютерної графіки. 283
§ 6.1. Координати та вектори на площині. 285
Запитання та завдання. 292
§ 6.2. Способи опису ліній на площині. 292
6.2.1. Загальне рівняння прямої. 292
6.2.2. Нормоване рівняння прямої. 294
6.2.3. Параметричні рівняння прямого, променя, відрізка. 296
6.2.4. Способи опису кола. 297
Запитання та завдання. 298
§6.3. Завдання комп'ютерної графіки на взаємне розташування точок та фігур. 298
6.3.1. Пряма, перпендикулярна даній та проходить через задану точку. 298
6.3.2. Розташування точки щодо прямої, променя чи відрізка. 299
6.3.3. Взаємне розташування прямих, відрізків, променів. 301
6.3.4. Взаємне розташування кола та прямої. 303
6.3.5. Взаємне розташування двох кіл. 305
Запитання та завдання. 307
§ 6.4. Багатокутники. 307
6.4.1. Перевіряє опуклість багатокутника. 308
6.4.2. Перевірте належність точки внутрішньої області багатокутника. 308
6.4.3. Обчислення площі простого багатокутника. 310
Запитання та завдання. 311
§6.5. Геометричні об'єкти в просторі. 312
6.5.1. Основні формули. 312
6.5.2. Визначення перетину прямої лінії та трикутника у просторі. 314
6.5.3. Обертання точки навколо заданої прямої у просторі. 315
Запитання та завдання. 317
Висновок. 318
Додаток. 319
Предметний покажчик.

Використання фібоначчієвої системи числення.
На зорі комп'ютерної ери було зроблено ще два відкриття в області позиційних способів представлення чисел, які, однак, маловідомі і в той період не привернули особливої ​​уваги математиків та інженерів. Йдеться про властивості фібоначчієвої системи числення та системи числення золотої пропорції.

В останні десятиліття XX століття групою математиків під керівництвом професора А. П. Стахова в СРСР було отримано надзвичайно цікаві результати, пов'язані з вирішенням проблеми надійності зберігання, обробки та передачі в комп'ютерних системах. Математиками було запропоновано використовувати як систему числення в комп'ютерах фібоначчієву систему. Нагадаємо, що алфавітом цієї системи є цифри 0 і 1, а базисом - послідовність чисел Фібоначчі: 1, 2, 3, 5, 8, 13, 21, 34....

Безкоштовно завантажити електронну книгу у зручному форматі, дивитися та читати:
Скачати книгу Математичні основи інформатики - Елективний курс - Навчальний посібник - Андрєєва Є.В. Босова Л.Л. Фаліна І.М. - fileskachat.com, швидке та безкоштовне скачування.