16. Задачи на раскраски, укладки, замощения.

Метод раскраски.

Суть метода вспомогательной раскраски состоит в следующем. Раскрасив некоторые ключевые элементы, которые фигурируют в задаче в несколько цветов, исследовать, что будет происходить, если выполнять условия задачи. Цвет позволяет значительно упростить понимание процесса, фигурируемого в условии, и зачастую приводит к решению. Этот метод позволяет эффективно решать ряд задач, в частности, игровые и шахматные задачи.

17. Диофантовы уравнения.

ДИОФАНТОВЫ УРАВНЕНИЯ - алгебраические уравнения или системы алгебраических уравнений, решения которых отыскиваются в целых или рациональных числах. Обычно предполагается, что Д. у. имеют число неизвестных, превосходящее число уравнений, в связи с чем они называются также неопределенными уравнениями.

Диофантовыми уравнениями называются уравнения вида , где - многочлен с целыми коэффициентами.

При исследовании диофантовых уравнений обычно ставятся следующие вопросы:

1. имеет ли уравнение целочисленные решения;

2. конечно или бесконечно множество его целочисленных решений;

3. решить уравнение на мн-ве целых чисел, т. е. найти все его целочисленные решения;

4. решить уравнение на множестве целых положительных чисел;

5. решить уравнение на множестве рациональных чисел.

Решить уравнение в целых числах (уравнение с одним неизвестным).

Решение: свободный член уравнения 1. Делители свободного члена уравнения: ±1. Старший коэффициент уравнения 1. Положительные делители старшего коэффициента: 1. Следовательно, все целые корни уравнения находятся среди чисел {-1,1}. Подставляя в уравнение заключаем, что только является корнем этого уравнения.не пральна

Диофантовы уравнения с двумя и более неизвестными подразделяются на уравнения первой степени и уравнения высших степеней.

Д. у. первой степени или так называемые линейные уравнения имеют вид , где .

Простейшим видом уравнений в целых числах являются уравнения вида , где - заданные целые числа, . Для решения уравнения (1) в целых числах потребуются некоторые факты.

Диофантовы уравнения высших степеней

Методы решения:

1. метод разложения на множители;

2. выражение одной переменной через другую и выделение целой части дроби;

3. решение уравнений как квадратных относительно одной из переменных;

4. использование чётности;

5. доказательство неразрешимости уравнений с использованием сравнений;

6. и другие методы решения диофантовых уравнений.

18. Логические задачи, решаемые с помощью графов

Графом называется любое множество точек, некоторые из которых соединены линиями или стрелками. Точки, изображающие элементы множества, называют вершинами графа, соединяющие их отрезки – рёбрами графа. Точки пересечения рёбер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками. Рёбра иногда удобнее изображать не прямолинейными отрезками, а дугами.

19. Логические задачи, решаемые с помощью составления таблиц истинности.

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

Правила для построения таблиц истинности:

Необходимо определить количество строк в таблице истинности.

К=2n, где n-количество переменных; К-количество строк.

Определить количество столбцов (количество переменных + количество логических операций).

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

Заполнить столбцы логических переменных наборами значений.

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