Формулировка проблемы 4-х красок

Достаточно ли 4 х красок для такой раскраски произвольной географической карты при которой 2-е ее соединение страны имеющим общую границу окрашены в различные цвета.

Картой назыв связный плоский мультиграф без мостов. грани имеющие общее ребро называются смежными тогда функция раскраски для граней  ставит в соответствие каждой внутренней грани  число – цвет грани.

Карта назыв К раскрашиваемой если для нее существует правильная К раскраска, т.е. такая что  - смежные вершины.

всякая карта 4-х раскрашиваемая (всякий планарный граф и раскрашиваемая)

Т./ всякий планарный граф 5-ти раскрашиваемый.

Раздел3

Введение в теорию алгоритмов

Основные требования к алгоритму.

1. Данные – алгоритм работает с применением исходных данных – выдает результаты т.е. перерабатывает входные, выходные и промежуточные данные. Данные есть слова конечной длинны данного алгоритма.

2. Память - может быть бесконечной, единица измерения данных и памяти должны быть согласованы. Память используется для хранения данных.

3. шаги Алгоритм состоит из элементарных шагов.

4. Детерминирование – после каждого шага должно быть известно куда идти дальше или остановка.

5. результативность – после конечного числа шагов получение информации (или остановка после конечного числа шагов)

Тезис черта.

Несмотря на нестрогость интуитивное представление об алгоритме является настолько отчетливым, что практически не возникает разногласий около того является ли алгоритмич тот или иной процесс, ситуация оказывается принципиальной когда имеют дело с задачами решение которых неизвестно относительно которых является???????????????????????? они по сути не могут быть алгоритмически разрешены.

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

Тезис черта: класс задач решаемых в любой из формальных алг моделей и есть класс всех задач которые могут быть решены интуитивно алг методами.

Три основных типа универсальных алгоритмических моделей.

1. Связывает понятие с вычислениями и числовыми функциями

Пример: рекурсивные функции – хорошо развитая и изученная модель данного типа.

2. Связывает понятие алг с некоторыми детерминированными устройствами выполняющими в каждый отдельный момент некоторые примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Пример: машина тюьринга

Маштна Тьюринга.

-УУ

-галовка(пишушая и считывающая)

УУ

может находится к важдый момент времени

 - начальное состояние

 - заключ состояние

Q-назыв Внутринний алфавит

Если УУ в состояние  то машина прекращает работу.

Лента – рабита на ячейки в каждой ячейки записан один из символов алфавита

лента бесконечна в обе стороны одна в начальный момент времени и последущие только конечные число ячеек заполнено не пустыми символами.

 - пустой символ

Если ячейка пуста считается что в ней записан пустой символ.

Головка перемещается вдоль ленты и в каждый момент времени обозревает содержимое одной ячейки считывает ячейку вписывает в ячейку какой-либо символ из алфавита А вместо обозреваемого а затем сдвигается вправо, влево или останавливается.

сдвиг зависит от УУ в процессе работы УУ в зависимости: 

1. от состояния в котором находится УУ.

2. символ обозреваемый головкой выполняет сл действия

-головка записывает в обозреваемую ячейку  и происходит сдвиг на ячейку вправо или влевл или ост на месте на