Подвійні функції 1
Симетрія елементів 0 і 1 в множествеB призводить до поняття подвійності.
Приклад 2 (подвійні функції).
Пропозиція 1 (Подвійна до двоїстої функції) .Функція, двоїста до двоїстої функції f дорівнює самій функції f.
Доведення. f * (x1. xn) * = (¬f (¬x1. ¬xn)) * = * = ¬¬f (¬¬x1. ¬¬xn) = * = f (x1. xn) *
Розглянемо, що відбувається з таблицею двоїстої функції. Заміна набору (x1. Xn) на (¬x1. ¬xn) відповідає `` перевертання '' таблиці. Дійсно, набори (x1. Xn) і (¬x1. ¬xn) розташовані симетрично щодо середини таблиці. Тепер залишається застосувати операцію¬ до результату функції, тобто поміняти 0 на 1 і 1 на 0. Таким чином вектор значень функції, двоїстої до вихідної, виходить з вектора вихідної функції перевертанням і заміною 0 на 1, а 1 на 0.
Приклад 3 (вектор двоїстої функції).
функції x y иx y. задаються векторами значень (0,0,0,1) і (0,1,1,1) двоїсті один до одного. Також подвійними являютсяx y иx y. задаються векторами (0,1,1,0) і (1,0,0,1). Кожна з функційx і¬x (вектори (0,1) і (1,0) відповідно) двоїста сама собі.
Теорема 1 (Принцип подвійності) .Функція, двоїста до суперпозиції функцій, дорівнює суперпозиції двоїстих функцій. точніше:
7 «Алгоритм - це система операторів, взятих з безлічі операторів деякого виконавця, яка повністю визначає певний клас алгоритмічних процесів, тобто процесів, які:
перетворюють деякі конструктивні об'єкти.
Між операторами алгоритму і операціями (елементарними діями) алгоритмічного процесу існує гомоморфності відповідність. Тому алгоритм слід також вважати моделлю алгоритмічного процесу »
Різні визначення алгоритму в явній або неявній формі містять наступний ряд загальних вимог:
детермінованість - визначеність. У кожен момент часу наступний крок роботи однозначно визначається станом системи. Таким чином, алгоритм видає один і той же результат (відповідь) для одних і тих самих вихідних даних. У сучасному трактуванні у різних реалізацій одного і того ж алгоритму повинен бути ізоморфний граф. З іншого боку, існують імовірнісні алгоритми, в яких наступний крок роботи залежить від поточного стану системи і генерується випадкового числа.
зрозумілість - алгоритм для виконавця повинен включати тільки ті команди, які йому (виконавцю) доступні, які входять в його систему команд.
завершаемості (кінцівку) - при коректно заданих вихідних даних алгоритм повинен завершувати роботу і видавати результат за кінцеве число кроків. З іншого боку, імовірнісний алгоритм може і ніколи не видати результат, але ймовірність цього дорівнює 0.
масовість - алгоритм повинен бути застосований до різних наборів вихідних даних.
Важливу роль відіграють рекурсивні алгоритми (алгоритми, що викликають самі себе до тих пір, поки не буде досягнуто деяке умова повернення). Останнім часом активно розробляються паралельні алгоритми, призначені для обчислювальних машин, здатних виконувати кілька операцій одночасно
.Граф - це безліч точок або вершин і безліч ліній або ребер, що з'єднують між собою всі або частину цих точок.
Вершини, прилеглі до одного і того ж ребру, називаються суміжними.
Якщо ребра орієнтовані, що зазвичай показують стрілками, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом. Якщо ребра не мають орієнтації, граф називається неорієнтованим.
Графи зазвичай зображуються у вигляді геометричних фігур, так що вершини графа зображуються точками, а ребра - лініями, що з'єднують точки.
Петля - це дуга, початкова і кінцева вершина якої збігаються.
Простий граф - граф без кратних ребер і петель.
Ступінь вершини - це подвоєне кількість петель, що знаходяться у цій вершини плюс кількість інших прилеглих до неї ребер.
Порожнім називається граф без ребер. Повним називається граф, в якому кожні дві вершини суміжні.
Шляхи, маршрути, ланцюги та цикли
Шлях в орієнтованому графі - це послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початковою вершиною наступної.
Вершини v0, vn називаються пов'язаними даними шляхом (або просто пов'язаними). Вершину v0 називають початком, vn - кінцем шляху. Якщо v0 = vn, то шлях називають замкнутим. Число n називається довжиною шляху.
Маршрут в графі - шлях, орієнтацією дуг якого можна знехтувати.
Ланцюг - маршрут, в якому все ребра попарно різні.
Цикл - замкнутий маршрут, який є ланцюгом.
Маршрут, в якому всі вершини попарно різні, називають простий ланцюгом. Цикл, в якому всі вершини, крім першої та останньої, попарно різні, називаються простим циклом.
Приклад 2 (граф відносини подільності)
П
