Практические задания по дискретной математике


    Найти многослойный персептрон минимальной архитектуры, моделирующий XOR
    Построить многослойный персептрон,  моделирующий выборы в США КОНТРОЛЬНАЯ  РАБОТА ПО БУЛЕВСКИМ ФУНКЦИЯМ   Вариант 1 Задача 1.  Сколько существует булевских функций  f(x, y) двуx переменных,  которые истинны (TRUE) при X=FALSE? Задача 2 Представить булевскую функцию (X OR  Y) And  Z в  виде многочлена Жегалкина Задача 3 Можно ли представить  штрих Шеффера в  виде однослойного персептрона?   Вариант 2 Задача 1 Сколько существует булевских функций  f(x, y, z) трех переменных,  которые истинны (TRUE) при Z=FALSE? Задача 2 Представить булевскую функцию (X OR  Y) And  Z в  виде многочлена Жегалкина Задача 3 Представить булевскую функцию  X OR Y OR Z в  виде персептрона.   Вариант 3 Задача 1 Сколько существует булевских функций  f(x, y, z) трех переменных,  которые истинны (TRUE) при Y =FALSE  ? Задача 2 Представить булевскую функцию (X OR  Y) And  Z в  виде многочлена Жегалкина Задача 3 Представить булевскую функцию F=(X  AND  Y)  OR (NOT  Z)   с помощью  однослойного персептрона.   Вариант  4 Задача 1 Сколько существует булевских функций  f(x, y, z) трех переменных,  которые  ложны (FALSE) при Y =FALSE? Задача 2 Найти отрицание формулы,  используя правила двойственности. F=(X  AND  Y)  OR (NOT  Z) Задача 3 Mожно ли представить стрелку Пирса в виде однослойного персептрона? ТИПОВЫЕ  КОНТРОЛЬНЫЕ ЗАДАЧИ ПО КУРСУ МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Задача 1 Задача 2 Задача 3 Задача 4 Сколько существует булевских функций от трех переменных? Задача 5 Вася и Женя решают систему n линейных уравнений  c n неизвестными методом Гаусса на одном и том же компьютере.  Вася решил систему 100 уравнений за минуту. Сколько потребуется времени  Жене для системы из 200 уравнений? Представьте следующие рассуждения в виде последовательности формул логики предикатов. 7.1. Некоторые из первокурсников знакомы со всеми второкурсниками, а некоторые из второкурсников – спортсмены. Следовательно, ряд первокурсников знаком с некоторыми спортсменами. 7.2. Членом правления клуба может быть каждый совершеннолетний член клуба. Игорь и Андрей – члены клуба. Игорь – совершеннолетний, а Андрей старше Игоря. Следовательно, Андрей может быть членом правления клуба. 7.3. Таможенные чиновники обыскивают всякого, кто въезжает в страну, кроме высокопоставленных лиц. Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, также способствовавшими провозу наркотиков. Никто из высокопоставленных лиц не способствовал провозу наркотиков. Следовательно, некоторые из таможенников способствовали провозу наркотиков. 17. Дано утверждение: «Некоторые из первокурсников знакомы с кем-либо из спортсменов. Но ни один из первокурсников не знаком ни с одним любителем подледного лова». Какие из следующих утверждений будут следствием этого и почему: а) «ни один спортсмен не является любителями подледного лова», б) «некоторые из спортсменов не являются любителем подледного лова», в) «найдется спортсмен, который любит подледный лов»? 18. Докажите нелогичность следующих рассуждений, построив интерпретацию, при которой посылки истинны, а заключение ложно. 18.1 Все студенты нашей группы – члены клуба «Спартак». А некоторые члены клуба «Спартак» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом. 18.2. Некоторые студенты нашей группы – болельщики «Спартака». А некоторые болельщики «Спартака» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом. 18.3. Каждый первокурсник знаком с кем-либо из студентов второго курса. А некоторые второкурсники – спортсмены. Следовательно, каждый первокурсник знаком с кем-либо из спортсменов.

Учебный модуль 2. КОНТРОЛЬНАЯ  РАБОТА ПО ГРАФАМ

НЕ нашли? Не то? Что вы ищете?

  Вариант 1

Задача 1.  Составить программу, которая :

Генерирует случайную матрицу смежности размером 6 Х 6, составленную из 0 и 1

При этом вероятность единицы должна быть 0,3


Находит  в соответствующем ориентированном графе  вершину с выходной степенью 2.

Задача 2

Задача 3

  Вариант 2

Задача 1

Генерирует случайную матрицу смежности размером 6 Х 6, составленную из 0 и 1

При этом вероятность единицы должна быть 0,4

Находит в соответствующем ориентированном графе  вершину наибольшей степени

Задача 2

Задача 3

  Вариант 3

Задача 1

Генерирует случайную матрицу смежности размером 5 Х 5, составленную из 0 и 1

При этом вероятность единицы должна быть 0,5



Находит  в соответствующем ориентированном графе  вершину наименьшей степени

Задача 2

Задача 3

  Вариант  4

Задача 1

Генерирует случайную симметричную матрицу смежности размером 7 Х7, составленную из 0 и 1.  При этом вероятность единицы должна быть 0,3
Находит диаметр  соответствующем неориентированном графе  диаметр

Задача 2

Задача 3

Задание  1

Составить программу, которая :

Генерирует случайную матрицу смежности размером 6 Х 6, составленную из 0 и 1

При этом вероятность единицы должна быть 0,5

Нарисовать соответствующий ориентированный граф.  Представить граф в виде списка смежных вершин

Найти все клики в этом графе не более чем с 3 вершинами
Найти  вершину с выходной степенью 2.

Задание  2

Составить программу, которая :

Генерирует случайную матрицу смежности размером 6 Х 6, составленную из 0 и 1

При этом вероятность единицы должна быть 0,4

Нарисовать  соответствующий ориентированный граф.  Представить граф в виде списка смежных вершин

Найти (программно) вершину наибольшей степени
Написать программу,  которая ищет  все простые циклы длины не более 3.

Задание  3

Составить программу, которая :

Генерирует случайную матрицу смежности размером 5 Х 5, составленную из 0 и 1

При этом вероятность единицы должна быть 0,5

Нарисовать соответствующий ориентированный граф.  Представить граф в виде списка смежных вершин

Найти все клики в этом графе не более чем с 4 вершинами

Найти  (программно) вершину наименьшей степени

Задание  4

Составить программу, которая :

Генерирует случайную симметричную матрицу смежности размером 7 Х7, составленную из 0 и 1 При этом вероятность единицы должна быть 0,3

Нарисовать соответствующий неориентированный граф.  Представить граф в виде списка смежных вершин


Написать программу, которая ищет диаметр графа и найти диаметр Найти все  циклы длины не более 4.

Задание по булевским функциям

    Сколько существует булевских функций от двух переменных? От трех? 2) Найти булевские функции от 2 переменных, представимые однослойным персептроном 3) Представим ли штрих Шеффера однослойным персептроном? 4) Представима ли стрелка Пирса однослойным персептроном Дан граф с вершинами 1  , 2, 3, 4, 5, 6,7

В графе даны ребра с расстояниями

D(1,2) =10

D(1,3)=5

D(2,3)=7

D(3,5)=12

D(3,4) =13

D(3,7)=8

D(4,6)=7

D(4,5)=1

D(5,6) =11

D(5,7)=5

D(6,3)=2

D(6,4)=12

Найти кратчайшие расстояния между всеми вершинами методом Дейкстры (или Флойда Уоршолла)

    Дан граф с вершинами 1  , 2, 3, 4, 5, 6,7

В графе даны ребра с расстояниями

D(1,2) =11

D(1,3)=1

D(2,4)=7

D(3,5)=12

D(3,4) =13

D(3,6)=8

D(4,6)=7

D(4,5)=1

D(5,2) =11

D(5,7)=5  D(6,3)=2  D(6,4)=1  Найти кратчайшие расстояния между всеми вершинами методом Дейкстры (или Флойда Уоршолла)