Шпаргалка по дисциплине "Дискретная математика"

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 19

Фундаментальным циклом графа G= (S,U) c остовным деревом T=(S,U’)называется простой цикл , получаемый в результате добавления в T одного из ребер G ,не принадлежаещего U’

G(S,V) неориентированный граф , содержащий n- вершин , m- графов , k- компонентов связности . Пусть Gштрих – его остов . G штрих имеет n-k ребер .   – эти ребра наз-ся ветвями остова Gштирх . Оставшиеся m-n+k ребер U1,U2,..Um-n+к, не входящие в Gштрих наз-ся хордами остова G . По определению дерева если к G’ прибавить произвольную хорду Vi,то в полученном графе G' {Vi} найдется ровно один цикл Gi . , состоящий из хорды Ui и некоторых ветвей остова G’.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 20

Поток в сети между вершиной t (источником) и s (стоком ) называется набор чисел Сij(т.е кол-во условного груза , перевозимого из вершины с номером I в вершину с номером j ) , удовлетворяющих четырем условиям :  1)числа Cij J 0 ,причем Сij>0 ,то Сij=0 (нет встречных перевозок )                                           2)Числа Сij j Qij (соответствующих пропускных способностей ребер ) 3)если вершина с номером I- промежуточная (не совпадает с источником и стоком), то количество груза , вывозимого из вершины I равно количеству груза ,ввозимого в эту вершину .                 4) количество груза , вывозимого из источника t, должно быть равно количеству груза , ввозимого в сток S и числу А: Число А называется величиной данного  потока или просто между t и s .  

Билет 21

Дана транспортная сеть G(V,E ) c источником S и стоком t ,где ребра (u,v) имеют пропускную способность с(u,v), поток f(u,v) и цену a(u,v) . Цена пересылки потока f*a . Необходимо переслать d единиц потока  . Суть задачи найти поток f(u,v),минимизирующий его общую стоимость .        Накладываются след. Условия: Ограничение пропускной способности: Поток не может превысить пропускную способность . f(u,v)<=c(u,v) . Антисимметричность : Поток из u в v должен быть противоположным потоку из u в v . f(u,v)=-f(u,v)                               Сохранение потока: f(u,w)=0          Необходимый поток:f(s,w)=d

 

 

 

 

 

 

Билет 22

При планирование и управлении сложными компонентами работ используют их граф.модели ,называемыми сетевыми графами . Сетевой граф- связный орграф без петель и контуров . Основными понятиями сетевого планирования яв-ся понятия работы и события . Работа – это любые действия ,сопровождающиеся затрачиванием ресурсов и времени , и приводящие к определенному результату . События – это рез-ат,завершения одной или нескольких работ ,и является предпосылкой , для выполнения работ следующих за ними.Любая работа на сети может быть определена двумя событиями между которыми она находится. Работа на сети может определяться дугами ,а события вертикальными сетями. Сетевой граф имеет только одно исходное событие , и одно  завешенное событие – окончание всех работ

Билет 23

Конечным автоматом называется формальная система М=(Q, Σ, δ, q0, F),где Q- конечное непустое множество состояний,    - конечный входной алфавит ,    отображение типа            ,  q0 принадлежит Q – начальное состояние , F   Q – множество конечных состояний              Запись δ(q, a) = p, где q,p∈Q и a∈Σ, означает, что конечный автомат M в состоянии q, сканируя входной символ a, продвигает свою входную головку на одну ячейку вправо и переходит в состояние p.               .Цепочка x∈Σ* принимается конечным автоматом M, если δ(q0, x) = p для некоторого p∈F. Множество всех цепочек x∈Σ*, принимаемых конечным автоматом M, называется языком, распознаваемым конечным автоматом M, и обозначается как T(M), т.е. T(M) = {x∈Σ* | δ(q0, x) = p при некотором p∈F}. Любое множество цепочек, принимаемых конечным автоматом, называется регулярным.

Билет 24 

Способы задания канонического автомата .                                               1) Табличный способ . Автомат можно задать с таблицей с 2мя входами , содержащий n строк и m столбцов , где на пересечение столбца q и строки a стоят значения ф-ий  (ai, qj)  (ai,qj) .           3)Задание автомата диаграммо Мура . Состояние автомата изображают кружками , в которые записывают символы qi(i=1..n) Из каждого кружка проводится n стрелок . Причем эта стрелка ведет в кружок соответствующий  (ai,qj) , полученный рисунок наз-ся графом автомата или диаграммой Мура.                                                       3)функциональный способ                    Ф-ией перехода автомата наз-ют ф-ию q ,которая в каждой паре (ai,vj) ставит в состояние q(ai,vj) принадлежащие V . Ф-ия перехода указывает в каком состояние окажется автомат , если она находится в состояние Vi, а на входе ему поступит сигнал ai.

 

 

 

 

 

 

 

 

 

 

 

                                 

 

 

 

 

 

 

Билет 25 .

Если в момент времени t= 1,2 .. На вход автомата A последовательно подаются входные символы X(t)принадлежащий  X и при этом автомат находится в состояние q(t) прин Q ,то под воздействием символа x(t)автомат перейдет в новое состояние q(t+1)прин Q и выдаст выходной сигнал y(t)прин y . Величины y(t),x(t),y(t+1) связаны между собой след. Ф-ями .q(t+1) ϕ(x(t),q(t)) . Эти ур-ия наз-ся каноническими уравнениями автомата . Для построения автомата A необходимо для данной булевой ф-ии найти ДНФ

 

Билет 26 .

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 27

Алгоритм обладает следующими свойствами:                              1) Дискретность. Это свойство состоит в том ,что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов . При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени , те преобразование исходных данных в результат осуществляется во времени дискретно .                                   2)Определенность. Каждое правило алгоритма должно быть четким , однозначным . 3)Результативность. Алгоритм должен приводить к решению за конечное число шагов . 4)Массовость. Алгоритм решения задачи разрабатывается в общем виде , те он должен быть применим для некоторого класса задач , различающихся лишь исходными данными . 5)Правильность. Алгоритм правильный , если его выполнение дает правильные результаты решения поставленной задачи .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 28

Простейшие рекурсивные ф-ии . Рассмотрим ф-ии ,которые наз-ся базисными 1)Нуль-ф-ия .0 (x=0) 2)Ф-ия следования x’=x+1 представлена для перехода к след этапу задания .               3)Функция тождества или ф-ия выделения аргумента для каждого n>=1 и 1<= I <=n               эти ф-ии вычисления и на их основе строятся более сложные выч. Ф-ии с помощью преобразований.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 29

^ Оператор суперпозиции. Суперпозиция  является мощным средством получения  новых функций из уже имеющихся. Суперпозицией называется любая подстановка функций в функции. Оператором суперпозиции  называется подстановка в функцию от m переменных m функций от n одних и тех же переменных.                Примитивно-рекурсивная ф-ия . В основе этого оператора лежит способ выч-ия ф-ии ,которая состоит в том,что задается f(0) и называется рекурентная ф-ия. f(n+1)=h(f(n)) позволяющая вычислять f(n+1),если известно f(n) с помощью этой ф-лы послед.  вычислится f(1),f(2) – такой процесс последовательного последовательного вычисления значений функции наз-ся рекурсией . Пусть. заданы какие-либо чисо=ловые значения ф-ии n местного q (n+2) местная h (n+1) местная частичная ф-ия f ,вд из ф-ий g и h c помощью оператора прим-рекурсивной ф-ии , если она может быть задана схемой примитвной рекурсии . 3)Минимизация . Говорят ,что ф-я f имеющая n аргументов получается из получаются из n-местных ф-ий q операций минимизации , если для новых чисел x1,x2,xn из No={0,1…}  равенству f{x1..xn}= k выч-ся для всех i<k . Оператор минимизации – это очевидное оюощение оператора , взятия обратной ф-ии . Обобщение довольно глубокое , так как от ф-ии не требуется ,чтобы она была взаимно однозначной (по переменной хn+1)

 

 

 

 

 

 

 

 

 

 

 

 

Билет 30

Функции , которые могут быть получены из простейших 0(х),s(х)=x+1 , lnm(x1…xn)=xm применением конечного числа раз операторов суперпозиции и примитивной рекурсии ,называются примитивно рекурсивными  Примит рекурсивные ф-ии всюду определены ,те определены для всех значений их аргумента .  

 

Билет 31

Частично-рекурсивная ф-ия. f(x1..x2) –частично рекурсив , если она могла быть получена из простейших примитивно-рекурсивных ф-ии .С помощью конечного числа приложений оператора суперпозиции , примитивн рекурсив . и минимализации .

Билет 32

Примитивно-рекурсивным предикатом будем называть   определенный предикат на мн-ве No Определение : P(x1..xn) n-местный предикат на мн-ве No. Ф-ия Up(x1..xn) наз-ют характеристической ф-ией для Р , если эта ф-ия удовлетворяет условию.       

Предикат наз-ся примитивно-рекурсивным ,если его характеристическая ф-ия примитив-рекурсивна         p(x1..xn) разрешима ,если характеристическая ф-я Up вычисляема и p(x1..xn) не разрешим , если Up не вычисляема

 

 

 

Билет 33

Нормальный алгритм Маркова –математическое построение ,предназначенное для уточнения понятия алгоритм. Нормальный алгоритм Маркова задается алфавитом А и нормальной схемой подстановок . Алфавит – конечное , непустое множество элементов называемых буквами . Различные сочетания букв образуют слова . Нормальная схема подстановок – это конечный набор , состоящий из пар слов , где любое слово переходит в правое ( но не наоборот ) .

Билет 34

Алгоритм Тьюринга

2 конечных алфавита А и Q . A – внешний алфавит . Конечный алфавит символов , которые подаются на входе машины Тью и выдаются на выходе . Q- внутренний алфавит ,конечный алфавит символов ,комбинации которых определяют внутреннее состояние МТ .                 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 35

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

Абстрактный исполнитель (абстрактная вычислительная машина) . Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма . В состав машины входит бесконечная в обе стороны лента , разделенная на ячейки и управляющее устройство , способное находится в одном из множества состояний . Число возможных состояний управляющего устройства конечно и точно задано . Управ.устройство может перемещаться влево и вправо по ленте ,читать и записывать в ячейки символы некоторого конечно алфавита . Выделяется особый пустой символ , заполняющий все клетки ленты ,кроме тех ,из них на которые записаны входные данные . Управляющее устройство работает согласно правилам перехода , которые представляют алгоритм реализуемый данной машиной Тьюринга . Каждое правило перехода предписывают машине , в зависимости от текущего состояния и наблюдаемого в текущей клетке символа , записать в эту новый символ , перейти в новое состояние и переместиться на одну клетку влево или вправо . Некоторые состояния машины Тьюринга могут быть помечены как терминальные , и переход в любое из них означает конец работы , остановку алгоритма . Машина Тьюринга называется детерминируемой, если каждая комбинация состояния и ленточного символа в таблице соответствует не более одного правила . Если существует 2 и более команд , такая машина Тьюринга называется недетерминированной