часть вторая структуры

 

алгоритмы

  • основная теорема арифметики
  • сравнение по модулю
  • теорема Ферма
  • основная теорема алгебры
  • нахождение корней квадратного полинома
  • логарифмы
  • две последовательности
  • арифметическая прогрессия
  • геометрическая прогрессия
  • принцип матиндукции
  • асимптотические обозначения
  • рекурентные соотношения
  • линейная рекурсия
  • бинарные алгебры
  • логика высказываний
  • машина Тюринга
  • машина Поста
  • логика исчисления предикатов
  • перестановки
  • матрицы графа
  • путь Эйлера
  • путь Гамильтона

  • Крис Окасаки

    * * *

    вы входите в спортивный зал, там две сотни школяров. 8 сентября - и вас мучает неодолимое желание узнать, кто же из них занимает 98-е место по росту, считая с самого маленького. нечего и мечтать о том, что вы сможете построить их по ранжиру - никто бы не смог. "Но я могу использовать QUICKSELECT!"

    забираетесь в самую гущу, закрываете глаза, вытягиваете руку и делаете три оборота. открываете глаза и выхватываете из толпы пацана, на которого указывает ваша рука. Петя Поворотов. кричите что есть мочи: "А ну ка! Все, кто ниже Петра - к стене! Остальным - стоять! Работает ОМОН. те, кто одного роста с Петром могут остаться, а могут и подойти к стене. Живо!"

    считаете детей у стены и детей на поле - 79 и 120. ага, нужный ребенок на поле и вы усаживаете детей у стены на скамейки. и Петю тоже

    снова закрываете глаза, вытягиваете руку и крутитесь три раза. открыв глаза обнаруживате, что рука указывает на сестру Петра - Лену Поворотову. опять орете: "Быстро! Те, кто выше Лены - к стене, остальным - стоять! Тот, кто одного с ней роста могут подойти к стене, а могут и остаться на площадке"

    дети вновь делятся на две группы - 60 человек у стены и 59 - на поле. ага - нужный ребенок - на поле и вы усаживаете на скамейки Лену и всех тех, кто у стенки

    процедура повторяется и теперь выбран двоюродный брат Лены - Юра Поворотов. опять оставляете коротких на поле, а длинных ставите к стенке. равные могут выбирать, где им быть

    суета - и вновь появляются две группы: 37 детей на поле и 22 - у стены. ага, нужный по росту ребенок - Юра. дело в шляпе


    основная теорема арифметики

    каждое натуральное число N может быть разложено на простые множители только одним способом

     

    сравнение по модулю

    два целых числа a и b сравнимы по модулю d (d - целое), если при делении на d они дают один и тот же остаток

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

                  a ≣ b (mod d)                   ⇒    b ≣ a (mod d)
    
                  a ≣ b (mod d) и b ≣ c(mod d)    ⇒    a ≣ c (mod d)
    
                  a ≣ a'(mod d) и b ≣ b'(mod d)   ⇒    (a + b) ≣ (a' + b') (mod d) 
                                                       (a - b) ≣ (a' - b') (mod d) 
                                                       (a * b) ≣ (a' * b') (mod d)
    

    т.о, сравнения по одному и тому же модулю можно складывать, вычитать и умножать

    * * *

    M.Масленников

    сказка про числа, которые не хотели ни с кем делиться

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

    понятное дело, что все делились с числом 1 - это число было вроде как Царь-Батюшка во всем множестве натуральных чисел (МНЧ). но деление с этим числом было безобидное и поэтому все натуральные числа исполняли этот религиозный обряд - деление на 1 - без каких-либо последствий для себя

    ну а о другом важном числе - 0 - нельзя со 100% уверенностью сказать, что оно жило в МНЧ. у него был особняк, который все другие числа называли Конторой. все числа из МНЧ побаивались числа 0, а причина - простая. само число 0 могло делиться на кого угодно, после чего результат навсегда попадал в Контору, а вот если кто-то сам пытался делиться на 0, то его без лишних эмоций превращали в пыль. то есть число 0 жило по своим законам, отличным от законов МНЧ, и ожидать от него можно было всего, чего угодно

    число 2 было хитрым. оно разделило ровно пополам всех обитателей МНЧ на тех, кто с ним делился, и тех, кто это делать категорически отказывался. первых число 2 называло честными и даже создало из них партию: Партию Честных Чисел. в партии было Политбюро из наиболее известных честных чисел: 2, 4, 6 и 8. параграф 1 Устава гласил, что в партии могут состоять любые числа, признающие Устав и Программу и оканчивающиеся на одного из членов Политбюро. Устав приняли под бурные и продолжительные аплодисменты, но когда число 2 принесло его на согласование в Контору, там параграф 1 дополнили: "и 0". так его и утвердил Царь. а Программа у партии была простая: наша цель - бесконечность

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

    число 5 было безобидно, партий своих создавать не пыталось, а на выборах всегда выдвигалось от единого и нерушимого блока честных и беспартийных. делились на него те, у кого на конце было 5. "или 0" - дополнили в Конторе

    но были в МНЧ и диссиденты: числа, не вступившие в партию, и вообще, не желавшие ни с кем делиться, кроме Царя. в народе их называли простыми числами. строго говоря, и всеми уважаемые числа 2, 3 и 5 тоже были простыми, но благодаря куче поклонников - других чисел из МНЧ, которые с ними делились, - Царь считал их «своими» и никаких репрессий к ним не применял. а вот числу 13 не повезло: оно жило рядом с честным-пречестным числом 12 и постоянно пыталось отучить его от алкоголизма. как бы не так! число 12 написало в Контору, после чего отдел Пропаганды объявил число 13 причиной всех бед и несчастий в МНЧ и обозвал его «чертовой дюжиной»

    так и жили тысячу лет в МНЧ, умножались и делились, стремясь достигнуть светлой цели - бесконечности, но никак не могли этого сделать. и партийные вожди однажды провозгласили перестройку: «давайте делиться с остатком!». а народ в МНЧ был такой, что палец ему в рот не клади - руку по локоть откусят. все сразу смекнули, что остаток-то - штука неплохая. главное, чтобы он в 0 не обратился. и вот ведь что еще негодяи придумали - конечные группы. до того всем числам на всех политзанятиях только и внушали: наша цель - бесконечность, а тут - упала дисциплина, перестали слушать партийных пропагандистов, а на улицах стали появляться антиправительственные листовки:

    Наша цель - конечная группа!

    Всем! Всем! Всем!

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

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

    Выбирайте себе модуль, умножайтесь и делитесь на него с остатком! Частное выбрасывайте, а остатки образуют конечную группу.

    Нет бесконечности!

    Контора сперва хотела принять радикальное решение: показать всем этим вольнолюбцам настоящую бесконечность, обратив их в пыль, но хитрое число 2 надоумило Контору не делать глупостей, а действовать тоньше и с выгодой для себя. надо просто подсунуть горлопанам подходящий модуль. например, честного-пречестного алкоголика - число 12

    идет как-то на нетвердых ногах число 3, а навстречу ему прямо сияет честное-пречестное число 8

    - Давай вступим в конечную группу по модулю 12
    - Давай!

    вступили. перемножились. раньше такое сколько раз вытворяли - и в Контору за это никто не попадал. а тут как только привели результат по модулю 12, глазом не успели моргнуть, как он уже в Конторе

    - Ну что, сынки, помогло вам ваше деление с остатком?

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

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

    Контора была в ярости. это кто ж теперь в модулях ходит? без 0 в конце, беспартийные, непьющие, без юбилейных медалей! по-обычному ни с кем не делятся - простые! да таких простых - раз два - и обчелся! а как же светлое будущее? с кем его строить-то будем, если все простые закончатся?

    - Не закончатся - ответил Конторе старик Эратосфен

    но на всякий случай в Конторе решили поставить все конечные группы на учет, под буквой Z (от слова zero - агентурной клички числа 0):
    Z/2 - группа по модулю 2,
    Z/3 - группа по модулю 3
    и так далее

    группа Z/2 была совсем неинтересной и состояла из одного Царя-Батюшки - числа 1

    группа Z/3 состояла из Царя и партийного Вождя - числа 2. забавные превращения там получались. партийный Вождь, перемножившись сам с собой, превращался в Царя - ну это еще можно понять, такие превращения бывали. а вот Царь-то, Царь - хорош гусь! поделившись на партийного Вождя, сам становился партийным Вождем!

    вскорости из конечных групп стали создавать ночные клубы: «Семеро козлят», «Футбольная команда», «Чертова дюжина», «17 мгновений весны» и прочая, прочая, прочая. натуральные числа были рады их появлению. особенно рад был Царь-Батюшка. сидит, бывало, в своем дворце целыми днями один-одинешенек, и поделиться-то не с кем, ни на кого он не делился. а тут, в конечной группе - делись с кем хочешь, хоть до утра. и число 2 меньше стало внимания уделять своей партии - надоели, зануды. пойдут, бывало, Царь вместе с партийным Вождем в weekend в какие-нибудь «Мгновения» душу отвести, наделиться всласть на всю трудовую неделю вперед, а там уже и число 3 (меньше пить стало) и 5 (без медалек) и 12 (подружившееся с 13) - все веселые, друг с другом делятся. какие тут партии и партбилеты! без особых проблем число 2 согласилось на переименование своей партии в множество - множество четных чисел

    ... поскипано мышами ...

    ... а вот RSA как раз и стал таким алгоритмом, в котором без простых чисел обойтись никак невозможно. только простые числа для RSA нужны большие - ведь они же секретный ключ! думало - думало об этом число 2 и решило, что длина простого числа в RSA должна быть 512 или 1024 бит. "пол-литра и литр" - по-своему расшифровало эти значения число 3

    и брошен был клич: все на поиски больших простых чисел, ибо без них не будет в МНЧ ни Internet Banking, ни электронной коммерции. а простые числа - скромные, тихо сидят себе по своим конечным группам, никаких явных признаков у них нет. как их отыскать во множестве натуральных чисел? задачу эту поручили Конторе, ну а Контора выполнила это поручение так, как умела. переписали в Конторе все простые числа до 256 и поехали по отдаленным уголкам необъятного МНЧ. случайно заезжают в какую-нибудь глухомань и хватают там первого попавшегося аборигена

    - Говори, падла, с кем делишься?
    - Гражданин начальник, ни с кем не делюсь.
    - Врешь, гад!
    - Век бесконечности не видать!

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

    - Говори, паскуда, сколько у тебя свидетелей простоты?

    и вот только после того, как найдет m-мужичок достаточное (log2m) число свидетелей своей простоты, сажают его в машину и везут в столицу: RSA-ключом будет

    всю эту процедуру прозвали в народе тестом Миллера-Рабина. вылавливают конторские таким образом пару пол-литровых мужичков - числа p и q, и готов секретный ключ. перемножают их, получают литровый открытый ключ - n, который затем одевают в нарядный сертификат

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

    * * *

    теорема Ферма (не та)

    если p - простое число, не делящее целого числа b, то b ^ (p - 1) ≣ 1 mod p


    основная теорема алгебры

    всякий алгебраический полином степени n
        f(x) = x ^ n  +  an-1 * x ^ n-1  +  ..  + a1 * x  +  a0 
    
    может быть представлен в виде произведения ровно n множителей
        f(x) = (x - x1) * (x - x2) * .. * (x - xn)
    
    x1, x2, .., xn называются корнями уравнения

    нахождение корней квадратного полинома

    	x² + b * x + c         =     0 
    
    	x² + b * x             =     -c 
    
    	x² + b * x + b² / 4    =     b² / 4 - c 
    
    	(x + b / 2)²           =     (b² - 4 * c) / 4 
    
    	x + b / 2              =     ± √ (b² - 4 * c) / 2 
    
    	x                      =     [-b ± √ (b² - 4 * c)] / 2
    

     


    логарифмы

                          x = a ^ loga x = loga (a ^ x)
    
                                     loga x
                          logb x =  -------
                                     loga b
    
                          loga x + loga y = log a (x * y) 
    
                          loga (x ^ y) = y * log a x 
    

    
                           e = lim (1 + 1/n)n
                              n → ∞
    
    
                           exp x = lim (1 + x/n)n
                                  n → ∞
    
    
                           (ln x)' = 1/x 
    
    
                           ∫ ln x dx = x * (ln x - 1)
    
    

    две последовательности

            ex = 1 + x/1 + x2/2 + x3/6 + ... + xn/n! + ...
    
            1/(1 - x) =  1 + x + x2 + x3 + ... + xn + ... , 0 < x < 1
    

    арифметическая прогрессия

         1  +  2  +  ...  +  n    =   n * (n + 1) / 2   =   n2/2  +  n/2       f(n) =  Ο(n2)
         
         1² +  2² +  ...  +  n²   =   n * (n + 1) * (2 * n + 1) / 6            f(n) =  Ο(n³) 
    

    геометрическая прогрессия

        q0 + q1 + q2 + ... = 1 / (1 - q),  0 < q < 1
    

    пример:

         1 + 1/2 + 1/4 + 1/8 + ... =  1 / (1 - 0.5) = 2
    

       1 + x + x2 + x3 + x4 + ... + xn = (1 - xn+1) / (1  - x),  x ≠ 1
    

    принцип математической индукции

    желая установить справедливость некоторой общей теоремы A при любых значениях n, мы доказываем эту теорему последовательно для бесконечного ряда специальных случаев A1, A2, ...

    возможность этого рассуждения покоится на двух предпосылках:

    1. имеется общий метод доказательства того, что если справедливо утверждение Ar, то следующее по порядку утверждение Ar+1 также справедливо;
    2. известно, что первое утверждение A1 справедливо

    предположим, что требуется установить справедливость бесконечной последовательности математических предложений A1, A2, A3, ..., которые все, совместно взятые, образуют некоторое общее предложение A. допустим, что:

    1. проведено математическое рассуждение, показывающее, что если верно Ar, то верно и Ar+1, каково бы ни было натуральное число r, и
    2. установлено, что A1 верно
    тогда все предложения нашей последовательности верны и, следовательно, предложение A доказано

    a well-known scientist once gave a public lecture on astronomy. he described how the earth orbits around the sun and how the sun, in turn, orbits around the centre of a vast collection of stars called our galaxy. at the end of the lecture, a little old lady at the back of the room got up and said: “What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise”. the scientist gave a superior smile before replying, “What is the tortoise standing on?” – “You’re very clever, young man, very clever”, said the old lady, “But it’s turtles all the way down!”

    (из Курранта)

     

    n ∈ N

    предикат: P                                   (инвариант)

    базовый случай: P(k) , k < n       (частные случаи: k = 0, k = 1)

    вывод: if P(n) == True then P(n+1) == True

    строгая матиндукция

    n ∈ N

    предикат: P                                   (инвариант)

    базовый случай: P(k) , k < n         (частные случаи: k = 0, k = 1)

    вывод: if ∀ k : k ≤ n, P(k) == True then P(n+1) == True

    матиндукция и конструктивная математика

    есть какой-то предикат P(x), и для него известно, что P(0) == True, что P(0) => P(1), и так далее. пусть оказалось, что нельзя применить индукцию. это что-то значит относительно P. однако для "простых" свойств мы вроде как убеждены, что всё хорошо. значит, где-то должна проявиться специфика конкретного P, которое является "плохим". и вот здесь непонятно, что это в принципе может значить. потому что стандартное "убедительное" рассуждение насчёт того, почему принцип индукции вообще "верен", никак не опирается на конкретную специфику свойства P. вот с примитивно-рекурсивными функциями уже гораздо интереснее, но здесь-то и нужно попытаться представить себе, "как такое может быть?" хотелось бы проследить более конкретно, где и как происходит "нарушение"

    такие вещи существуют. эти идеи развивали, в частности, Есенин-Вольпин и Вопенка. у последнего есть книга "Математика в альтернативной теории множеств", где всё строится на базе понятия "конечного", а эффект бесконечного имитируется при помощи "парадокса кучи", т.е. принцип индукции имеет ограниченную применимость. конечный "неклассический" натуральный ряд представляется в виде 1,2,...,ℵ, где ℵ - мифическое "очень большое число", до которого "нельзя досчитать". при этом аксиомы несколько варьируются. противоречие с принципом индукции возникает, но вывод такого противоречия может быть получен не раньше, чем мы досчитаем до ℵ, а поскольку про ℵ ничего не известно, то происходит имитация эффекта бесконечного. "неклассические" натуральные ряды также имеют некоторое отношение к проблеме вычислений за реальное время. скажем, можно разрешить не все рекурсивные функции, а только растущие не слишком быстро

    арифметику Пеано на самом деле тоже не очень тестировали - "больших индукций" в математической практике мало - реальная математика живет в маленьком кусочке. если удастся всю "повседневную математику" погрузить в более слабую теорию, то, во-первых, непротиворечивость PA станет не важна, а во-вторых, в противоречивость будет гораздо легче поверить. консистентность аксиоматики Пеано была доказана в расширенной системе аксиом (с трансфинитной индукцией и, кажется, чем-то ещё), но какой смысл в этом доказательстве, если нет (и не может быть) доказательства консистентности этой расширенной системы? ведь получается, что это доказательство нисколько не добавило нам уверенности в том, что PA непротиворечива

    собственно, колмогоровская сложность уже является вещью сомнительной для последовательного конструктивиста, и потому ее формализация в PA должна, скорее всего, содержать "неестественные" этапы. в терминах "ультрафинитизма" вообще нельзя рассматривать то, что "мы" называем "стандартной моделью" PA. в идеях Есенина-Вольпина как раз нет ничего "мистического". более того, он как раз пытался обосновать непротиворечивость даже ZF на базе построения её "как бы модели" на базе "как бы конечного". многие его соображения уже давно реализованы (хотя бы у Вопенки). там проблема скорее не в "экзотичности" или "неправдоподобии", а в том, что "неформальные" идеи не доведены до конца

    Coq:

    Print nat_ind.
    
        nat_ind = 
        fun P : nat -> Prop => nat_rect P
             : forall P : nat -> Prop,
               P Z -> (forall n : nat, P n -> P (S n)) -> forall n : nat, P n
    
    
    Print nat_rect.
    
        nat_rect = 
        fun (P : nat -> Type) (f : P Z) (f0 : forall n : nat, P n -> P (S n)) =>
        fix F (n : nat) : P n :=
          match n as n0 return (P n0) with
          | Z => f
          | S n0 => f0 n0 (F n0)
          end
             : forall P : nat -> Type,
               P Z -> (forall n : nat, P n -> P (S n)) -> forall n : nat, P n
    
    
    Theorem add_assoc : forall n m k , plus (plus n m) k = plus n (plus m k).
    Proof.
      induction n.
      intros.
      simpl.
      trivial.
      intros.
      simpl.
      rewrite IHn.
      trivial.
    Qed.
    
    
    Print add_assoc.
    
        add_assoc = 
        fun n : nat =>
        nat_ind (fun n0 : nat => forall m k : nat, n0 + m + k = n0 + (m + k))
          (fun m k : nat => eq_refl)
          (fun (n0 : nat) (IHn : forall m k : nat, n0 + m + k = n0 + (m + k))
             (m k : nat) =>
           eq_ind_r (fun n1 : nat => S n1 = S (n0 + (m + k))) eq_refl (IHn m k)) n
             : forall n m k : nat, n + m + k = n + (m + k)
    
        
    Lemma plus_Zero : forall n , plus n 0 = n.
    Proof .
      induction n ; simpl . reflexivity . rewrite IHn . reflexivity .
    Qed .
    
        
    Print plus_Zero.
    
        plus_Zero = 
        fun n : nat =>
        nat_ind (fun n0 : nat => n0 + 0 = n0) eq_refl
          (fun (n0 : nat) (IHn : n0 + 0 = n0) =>
           eq_ind_r (fun n1 : nat => S n1 = S n0) eq_refl IHn) n
             : forall n : nat, n + 0 = n
    
        
    Lemma plus_Succ : forall n m , plus n (S m) = S (plus n m).
    Proof.
      induction n ; simpl ; intros. reflexivity. rewrite IHn. reflexivity.
    Qed.
    
        
    Print plus_Succ.
    
        plus_Succ = 
        fun n : nat =>
        nat_ind (fun n0 : nat => forall m : nat, n0 + S m = S (n0 + m))
          (fun m : nat => eq_refl)
          (fun (n0 : nat) (IHn : forall m : nat, n0 + S m = S (n0 + m)) (m : nat) =>
           eq_ind_r (fun n1 : nat => S n1 = S (S (n0 + m))) eq_refl (IHn m)) n
        : forall n m : nat, n + S m = S (n + m)
    
    
    Theorem plus_comm : forall n m , plus n m = plus m n.
    Proof.
      induction n ; intros ; simpl .
      rewrite plus_Zero. trivial . rewrite IHn .
      rewrite plus_Succ . trivial .
    Qed.
    
    
    Print plus_comm.
    
        plus_comm = 
        fun n : nat =>
        nat_ind (fun n0 : nat => forall m : nat, n0 + m = m + n0)
          (fun m : nat => eq_ind_r (fun n0 : nat => m = n0) eq_refl (plus_Zero m))
          (fun (n0 : nat) (IHn : forall m : nat, n0 + m = m + n0) (m : nat) =>
           eq_ind_r (fun n1 : nat => S n1 = m + S n0)
             (eq_ind_r (fun n1 : nat => S (m + n0) = n1) eq_refl (plus_Succ m n0))
             (IHn m)) n
             : forall n m : nat, n + m = m + n
    

    "Big-O" ignores data storage latencies, topology, volume, available memory, and even the computational cost of every CPU instructions involved in a given implementation – instead, it merely counts the number of algorithmic operations. "Big-O" can be a valuable indication when designing algorithms but the best performing and scaling solution depends on the particular constraints of any specific problem and environment

    асимптотические обозначения для функции f(n)

    f(n) - асимптотически неотрицательна

    асимптотически точные оценки


    f(n) = Ο (g(n))
     
    ∃ c > 0, n0 > 00 ≤ f(n) ≤ c * g(n), if n > n0lim f/g < ∞

    f(n) = Θ (g(n))
     
    ∃ c1 > 0, c2 > 0, n0 > 00 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n), if n > n00 < lim f/g < ∞

    f(n) = Ω (g(n))
     
    ∃ c > 0, n0 > 00 ≤ c * g(n) ≤ f(n), if n > n0lim f/g > 0

    асимптотически неточные (граничные) оценки


    f(n) = ο (g(n))
     
    ∀ c > 0, ∃ n0 > 00 ≤ f(n) ≤ c * g(n), if n > n0lim f/g = 0

    f(n) = ω (g(n))
     
    ∀ c > 0, ∃ n0 > 00 ≤ c * g(n) ≤ f(n), if n > n0lim f/g = ∞

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

    рекурентные соотношения

    T (n) = k * T (n / m) + f (n) где

    T - время решения задачи от аргумента
    k - число подзадач
    m - величина дробления на подзадачи
    f - нерекурентный член

     

    метод подстановки

     

    метод деревьев

     

    основной метод

    выписываем рекурентное соотношение в виде:

    
       общее время ------->  T(n) = a * T(n / b) + f(nc) <------ нерекурентное слагаемое
                                    _     _____
                                    ^       ^
       кол-во частей      ----------+       |
       размер одной части ------------------+
    

    оцениваем нерекурентную часть f(nc) по параметрам рекурентной и получаем оценку работы алгоритма:

     


    если оценка для c есть:
     

    то оценка для всего алгоритма есть:
     

      log b a > c
     
    T(n) = Θ(nlog b a)

      log b a = c
     
    T(n) = Θ(nc log n)

      log b a < c
    T(n) = Θ(f(nc))

    метод Акра-Бази

    выписываем рекурентное соотношение в виде:
       T(x) = Σ [ak * T (bk * x)] + f(x)
              k
    
    где

    тогда

                           x
       T(x) = Θ (xp * (1 + ∫ [f(x)/x^(1+p)] dx)) 
                           1
    

    где

    
       p ∈ R : Σ ak * bkp = 1
               k
    

    линейная рекурсия

    однородные уравнения


    Tom Leighton, MIT

     

    неоднородные уравнения


    Tom Leighton, MIT


    бинарные алгебры

    алгебра - это совокупность образующего множества и замкнутых на нем n-арных операций


    О.П.Кузнецов, ВШЭ

    алгебры с несущим множеством, состоящим из двух элементов называют бинарными. операции, общие для всех таких алгебр:

    существуют и другие операции, как унарные, так и бинарные. всего может быть 16 бинарных операций (число подмножеств есть 2^2 = 4 и соответственно, число операций 2^4 = 16) и четыре унарных (2^1 = 2 и, соответственно, 2^2 = 4)

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

    Agda:

    module Bool where data Bool : Set where true false : Bool -- unary operations const1 : Bool → Bool const1 _ = true const0 : Bool → Bool const0 _ = false id : Bool → Bool id x = x ¬ : Bool → Bool ¬ true = false ¬ false = true -- binary operations _∨_ : Bool → Bool → Bool false ∨ false = false _ ∨ _ = true _∧_ : Bool → Bool → Bool true ∧ true = true _ ∧ _ = false _=>_ : Bool → Bool → Bool true => false = false _ => _ = true _<=>_ : Bool → Bool → Bool true <=> true = true false <=> false = true _ <=> _ = false

     

    дизъюнкция конституент единицы, равных единице на тех же наборах, что и заданная функция, называется совершенной дизъюнктивной нормальной формой функции

                    (~A /\ B)   \/   (A /\ ~B)
      

    коньюнкция конституент нуля, которые равны нулю на тех же наборах, что и заданная функция, называется совершенной конъюнктивной нормальной формой функции

                   (~A \/ ~B)   /\   (A \/ B)
      

    пять классов функций

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


    Я.М.Ерусалимский, ЮФУ

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

  • хотя бы одну функцию, не сохраняющую ноль
  • хотя бы одну функцию, не сохраняющую единицу
  • хотя бы одну нелинейную функцию
  • хотя бы одну немонотонную функцию
  • хотя бы одну несамодвойственную функцию

    система функций называется независимой, если ни одна из входящих в нее функций не выражается через другие функции этой же системы с помощью подстановки аргументов


    Я.М.Ерусалимский, ЮФУ

    множество из двух атомов { true , false } c определенными на нем операциями отрицания, конъюнкции и дизъюнкции образует Булеву алгебру

            { true , false }   ,    ~_    ,    _/\_   ,    _\/_         

    если же в качестве операций взять коньюнкцию, сложение по модулю два и единичную операцию, то получим алгебру Жегалкина

         { true , false }   ,   _/\_   ,    _⊕_    ,    1_     

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

            1    ⊕    a    ⊕    c    ⊕    (a /\ b)    ⊕    (a /\ b /\ c)
    

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

    логика высказываний

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

          Г |- А
    
    такая запись значит, что А есть теорема

    простейшей моделью является логика высказываний

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

      утверждающий модус, Modus Ponens 
            A -> B, A
            ---------
                B
    
        отрицающий модус, Modus Tollens
            A -> B, ~A
            ----------  
               ~B
      
        транзитивность
           A -> B, B -> C
           --------------
              A -> C
    
        закон противоречия
           A -> B, A -> ~B
           ---------------
                ~A
    
        объединение посылок
           A -> (B -> C)
           ---------------
           (A /\ B) -> C
    
        разъединение посылок
           (A /\ B) -> C
           ---------------
           A -> (B -> C)
    
        intro конъюнкции
            A , B
           ------
           A /\ B
    
        elim конъюнкции
           A /\ B   A /\ B
           ------   -----
             A        B
    
        intro дизъюнкции
            A          B
          -----      ------
          A \/ B     A \/ B
    

    Agda (с предыдущим модулем):

    module LogicZero where open import Bool -- => ∧ ∨ ¬ data _≡_ (x : Bool) : Bool → Set where refl : x ≡ x modus_ponens : (a b : Bool) → ((a => b) ∧ a) ≡ b modus_ponens true true = refl modus_ponens true false = refl modus_ponens false true = {!!} modus_ponens false false = refl modus_tollens : (a b : Bool) → (( a => b) ∧ (¬ a)) ≡ ¬ b modus_tollens true true = refl modus_tollens true false = {!!} modus_tollens false true = {!!} modus_tollens false false = refl tranb : (a b c : Bool) → ( a => b) ≡ true → ( b => c) ≡ true → (a => c) ≡ true tranb true true _ _ y = y tranb true false true _ _ = refl tranb true false false x _ = x tranb false _ _ _ _ = refl contra : (a b : Bool) → (a => b) ≡ true → (a => (¬ b)) ≡ true → ¬ a ≡ true contra true true _ y = y contra true false x _ = x contra false _ _ _ = refl conjpred : (a b c : Bool) → (a => (b => c)) ≡ ((a ∧ b) => c) conjpred true true true = refl conjpred true true false = refl conjpred true false _ = refl conjpred false _ _ = refl disjpred : (a b c : Bool) → ((a ∧ b) => c) ≡ (a => (b => c)) disjpred true true true = refl disjpred true true false = refl disjpred true false _ = refl disjpred false _ _ = refl

    тавтологии

    законы деМоргана       ~(A \/ B) <=> (~A /\ ~B)
    
                           ~(A /\ B) <=> (~A \/ ~B)
    
    
    
    закон контрапозиции     (A => B) <=> (~B => ~A)
    
    
    
    поглощение              A \/ (A /\ B) <=> A
    
                            A /\ (A \/ B) <=> A
    
    
    
    дистрибюция             A /\ (B \/ C) <=> (A /\ B) \/ (A /\ C)
    
                            A \/ (B /\ C) <=> (A \/ B) /\ (A \/ C)
    

    Agda (с предыдущим модулем):

    module LogicZeroTavto where
    
    open import Bool     --   =>   ∧   ∨   ¬
    
    
    data _≡_  (x : Bool) : Bool → Set where
      refl : x ≡ x
    
    
    deMorgan : (a b : Bool) → (¬ (a ∨ b)) ≡ ((¬ a) ∧ (¬ b))
    deMorgan true _ = refl
    deMorgan false true = refl
    deMorgan false false = refl
    
    contrapos : (a b : Bool) → (a => b) ≡ ((¬ b) => (¬ a))
    contrapos true true = refl
    contrapos true false = refl
    contrapos false true = refl
    contrapos false false = refl
    
    capture1 : (a b : Bool) → (a ∨ (a ∧ b)) ≡ a
    capture1 true _ = refl
    capture1 false _ = refl
    
    capture2 : (a b : Bool) → (a ∧ (a ∨ b)) ≡ a
    capture2 true _ = refl
    capture2 false _ = refl
    
    distrib1 : (a b c : Bool) → (a ∧ (b ∨ c)) ≡ ((a ∧ b) ∨ (a ∧ c))
    distrib1 true true _ = refl
    distrib1 true false true = refl
    distrib1 true false false = refl
    distrib1 false _ _ = refl
    

    аксиома исключённого третьего

    аксиома исключённого третьего (лат. tertium non datur, то есть «третьего не дано») — закон классической логики, состоящий в том, что из двух высказываний — «А» или «не А» — одно обязательно является истинным, то есть два суждения, одно из которых формулирует отрицание другого, не могут быть одновременно ложными

    с конструктивистской точки зрения, установление истинности высказывания вида «А или не А» означает:

    в конструктивной математике суждение считается истинным, только если оно доказывается ПОСТРОЕНИЕМ ТАКОГО ОБЪЕКТА. поскольку, вообще говоря, не существует метода, позволяющего для любого высказывания за конечное число шагов установить его истинность или истинность его отрицания, закон исключённого третьего не должен применяться в рамках конструктивного направления как аксиома, ибо
    1. имеются утверждения о наличии элементов в бесконечных множествах, которые никак невозможно проверить на их конечных частях. и они могут оказаться недоказуемыми. это связано с неразрешимостью
    2. сам способ порождения доказательств может быть настолько сложен, что будет моделировать задачи из общей рекурсии, про которые уже известно, что они неразрешимы

    но это все зависит от выбранной аксиоматики. в более слабых теориях возможны чудеса

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

    с другой стороны - разрешимость и даже complexity являются математическими игрушками. представьте что надо написать программу, создающую будку на Х собак, где Х - натуральное. но задача не решаема в общем виде! на 1-2 собаки надо делать классическую будку, на 3-10 - вольеры из сетки в ряд, а на большее число - уже целые комплексы т.к. надо решать совершенно другие проблемы (вроде массового выгула). но точно такая же ситуация например с задачей коммивояжёра. при некоторых размерах она тривиальным циклом решается, при некоторых требует распараллеливания, при некоторых требует суперкомпьютера с хорошим интерконнектом, а при некоторых вообще не имеет физического смысла т.к. ждать ответа придется годы

    у Тани в кармане икс конфет, а у Вани эн-большое. как им поделить лакомства по справедливости, если у Тани конфеты Прессбургера, а у Вани - примитивно-рекурсивные

    а возвращаясь к закону исключенного третьего, можно резюмировать: конструктивисты изучают то, что доказываемо, в то время как классическая логика изучает, что является "истинным"

    в современных реализациях отрицание реализовано для всех населенных типов, как ненаселенный тип False. предьявить доказательство из ненаселенного типа не представляется возможным и потому для любого реализованного типа P отрицание терма p : P , ¬ p будет термом из ненаселенного типа, то есть - его не будет. закон исключенного третьего в программировании не работает

    с точки зрения программиста отрицание классического закона исключенного третьего означает, что мы не сможем скомпилировать программу, содержащую такие две функции:

    Haskell

    data Void lemma :: Either a (a -> Void) lemma = undefined -- doubleNeg :: forall a. a -> a doubleNeg :: ((a -> Void) -> Void) -> a doubleNeg = undefined

    для второй нам придется выбирать либо использовать терм с типом (a -> Void) -> Void или обходиться без него - что равнозначно использованию конструкции forall a. a, которая по определению незаселена. и тут мы застряли! но та же самая история и с функцией lemma - чтобы она скомпилировалась, нужно удовлетворить те же самые условия, что и для двойного отрицания

    в булевой логике любое утверждение либо истинно, либо ложно, его можно просто заменить одной из этих двух констант. в конструктивной логике жизнь разнообразней. есть разница между true и irrefutable

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

    ложно оно тогда, когда у меня опять же есть конкретная программа, которая из предполагаемого док-ва этого утверждения производит ⊥, виснет. ложные утверждения - это типы плохих, негодных, виснущих программ

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

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

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


    машина Тьюринга

    до того как появились компьютеры, проблема разрешимости (Entscheidungsproblem) стимулировала создание множества равноценных определений «вычислимости»:
  • машины Тьюринга
  • регистровые машины
  • µ-рекурсивные функции
  • алгоритмы Маркова
  • λ-исчисление

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

    todo

    машина Поста

    todo

    логика исчисления предикатов

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


    О.П.Кузнецов, ВШЭ

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

    предикат – это функция одного или нескольких переменных

         P (x1 , x2 , ... , xn) = true | false   

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

    итак, предикат - это функция с булевым значением. функция - она однозначно отображает множество аргументов на область значений. значений у предиката - только два, но "предикат", в отличие от "высказывания" [ (true () , false () ] , может выдавать разные значения в зависимости от "чего-то" [ true (x1, y1, z1, ...) , false (xn, yn, zn, ...) ]. для функции это "что-то" есть её аргумент - на один и тот же аргумент она всегда выдаёт одно и то же значение. на один и тот же набор фактов (элементарных высказываний) предикат всегда выдает одно и то же значение. это - логика предикатов

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

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

    Agda (с предыдущим модулем):

    module LogicOne1 where
    
    open import Bool
    
    
    
    data ℕ : Set where
      ze : ℕ
      su : ℕ → ℕ
    
    
    infix 5 _<=_
    _<=_ : (x y : ℕ) → Bool 
    ze     <= _       = true 
    (su x) <= ze      = false 
    (su x) <= (su y)  = x <= y
    
    infix 10 _+_
    _+_ : (x y : ℕ) → ℕ
    ze   + y  = y
    su x + y  = su (x + y)
    
    
                             
    -- predicate with arity = 1, gomogeneous 
    big? : (x : ℕ) → Bool
    big? x = su (su (su ze)) <= x
    
                                
    -- predicate with arity = 2, geterogeneous
    notTwoWhenTrue? : (x : ℕ) → (a : Bool) → Bool
    notTwoWhenTrue? (su (su ze)) true = false
    notTwoWhenTrue? _ _ = true
    
                                
    -- predicate with arity = 3, homogeneous
    ord? : (x y z : ℕ) → Bool
    ord? x y z = (x <= y) ∧ (y <= z) 
    
                                  
    
    -- examples
                                  
    te01 : (x y z : ℕ) → Bool
    te01 x y z = (big? x) ∧ (ord? x y z)
    
    te02 : (x : ℕ) → (a b : Bool) → Bool
    te02 x a b = notTwoWhenTrue? x a ∨ b
    
    {-# BUILTIN NATURAL ℕ #-}
    ex01 = te01 40 50 60         -- true
    ex02 = te02 2 true false     -- false
    

    операцией связывания квантором общности называется правило, по которому каждому предикату P(...,x,...) сопоставляется высказывание, обозначаемое ∀x.P(...,х,...), которое истинно в том и только в том случае, когда предикат Р тождественно истинен при любом x, и ложно в противном случае. в выражении ∀x.P(...,х,...) переменная х уже перестает быть переменной, то есть вместо нее невозможно подставить какие бы то ни было конкретные значения, так как необходимо, чтобы условие выполнялось для всех значений x. говорят, что переменная x связанная

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

    если на предикат навешивается квантор, то фактически (из-за связывания переменной) этот предикат уменьшает свою арность на единицу. если навесить по квантору на каждую переменную, то предикат превратится в "высказывание"

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

    итак, переменная, на которую навешен квантор, называется связанной; несвязанная квантором переменная называется свободной. выражение, на которое навешивается квантор, называется областью действия квантора и все вхождения переменной, на которую навешен квантор, в это выражение являются связанными

    взяв любое множество S, мы можем задать для него предикат χ такой, что:

     χ(x) = (true if x ∈ S, false if x !∈ S)
    и для любого унарного предиката P, мы можем рассмотреть множество всех x, удовлетворяющих
    P(x) = true 
    таким образом, множества и предикаты являются лишь различными способами выражения одних и тех же понятий: вместо трактовки S как множества и записи x ∈ S, мы можем рассматривать его как предикат и записывать как S(x)

    для кванторов (в классической логике) выполняются:

        ∀x . P(x) = ~ (∃x . ~ P(x))
        ∃x . P(x) = ~ (∀x . ~ P(x))
    

    на интервале (конечной области) - это аналоги законов деМоргана. на двух обьектах это в точности законы деМоргана

        ∀x . (P1(x) /\ P2(x)) = ∀x . P1(x) /\ ∀x . P2(x)
        ∃x . (P1(x) \/ P2(x)) = ∃x . P1(x) \/ ∃x . P2(x)
    
        ∃y . ∀x . P(x,y) => ∀x . ∃y . P(x,y)
    

    Agda (с предыдущим модулем):

    module Quantors where
    
    open import Bool
    
    
    data ℕ : Set where
      ze : ℕ
      su : ℕ → ℕ
    
    infix 10 _+_
    _+_ : (x y : ℕ) → ℕ
    ze   + y  = y
    su x + y  = su (x + y)
    
    
    
    data _≡_  {a : Set} (x : a) : a → Set where
      refl : x ≡ x
    
    
    
    leftUnit : ∀ n → (ze + n) ≡ n
    leftUnit n = refl 
    
    rightUnit : ∀ n → (n + ze) ≡ n
    rightUnit ze = refl   
    rightUnit (su n) = subst su (rightUnit n)
    
    comm : ∀ n → ∀ m → (n + m) ≡ (m + n)
    comm ze ze = refl
    comm ze (su m) = subst su (comm ze m)
    comm (su n) ze = subst su (comm n ze)
    comm (su n) (su m) = {!!}
    
    assoc : ∀ n → ∀ m → ∀ k → (n + (m + k)) ≡ ((n + m) + k)
    assoc ze m k = refl
    assoc (su n) m k = subst su (assoc n m k)
    
    

    перестановки

    число подмножеств множества с кардинальностью n :

       k = 2 ^ n 

    число перестановок множества с кардинальностью n :

     k = n!  

    биномиальные коэфициенты

                                     (n, k) = n! / [k! * (n - k)!]
    

    полиномиальные коэфициенты

                                      (n, k1 k2 .. kr)  =  n! / [k1! * k2! * ... * kr!]
    

    формула Стирлинга

                                      n!   ∼   ( 2 * π * n )1/2  *  ( n / e )n
    

    матрицы графа

    связная (incidence) матрица

    связная матрица графа
    матрица размерностью n × m,
    где n (строки) - представляют вершины графа,
    m (столбцы) - представляют ребра графа

    неориентированная
    aij = 1 если вершина i и ребро j соединены
    aij = 0 если вершина i и ребро j не соединены

    сумма любого ряда есть степень соответствующей вершины графа (число ребер, сходящихся в этой вершине)
    сумма любого столбца есть 2

    ориентированная
    aij = -1 если ребро j выходит из вершины i
    aij = 1 если ребро j входит в вершину i
    aij = 0 если вершина i и ребро j не соединены

    сумма любого ряда есть разность входящих/выходящих ребер соответствующей вершины графа
    сумма любого столбца есть 0

    смежная (adjacency) матрица

    неориентированная смежная матрица графа
    размерностью n, где n - число вершин графа . строки и столбцы представляют вершины графа

    при наличии ребра из вершины i в вершину j значение элемента wij равно 1, а при отстутствии ребра равно 0

    сумма любого ряда|столбца есть степень соответствующей вершины графа (число ребер, сходящихся в этой вершине)

    ориентированная смежная матрица
    знак элемента определяется направлением ребра

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

    множество собственных значений смежной матрицы называется спектром графа

    на главной диагонали смежной матрицы графа без петель всегда будут нули ("петля" - ребро A → A, или B → B, но не циклический путь вида A → B → A)

    если M - смежная матрица графа, то любой элемент xij матрицы Mn - число путей длины n из вершины i в вершину j

    матрица расстояний

    матрица расстояний графа имеет значением каждого своего элемента xij минимальное количество ребер на пути из вершины i в вершину j

    Лаплассиан графа

    пусть di - степень вершины i - число входящих/выходящих ребер.

    Лаплассиан графа есть квадратная матрица:

                Lij =     di   if i==j
                       | -1    if vivj ∈ egde
                       |  0    otherwise 
    

    Лаплассиан может быть получен из смежной матрицы M путем несложной замены, с последующей операцией умножения и транспонирования

    сначала в каждом столбце j матрицы M заменяем:

  • элемент с индексом i < j становится положителен
  • элемент с индексом i > j становится отрицателен
  • и затем полученную таким образом матрицу S транспонируют и перемножают

                                         L = S * S⁺     
    

    наименьший ненулевой собственный вектор Лапласиана называется спектральным разрывом

    спектральный разрыв равен нулю тогда и только тогда, когда граф несвязен (есть изолированные вершины)

    сложностью графа называется число, равное произведению ненулевых собственных чисел Лапласиана деленное на число вершин

                        c = Π λi / n
    

    сложность - это число спан-деревьев графа

    Лаплассиан еще называют матрицей Кирхгофа или admittance matrix

    если граф является деревом, то Dij = det L(i,j) (при числе вершин больше двух)

    
                                incidence matrix                M
    
                                adjacency matrix                A
    
                                distance  matrix                D
                                
                                directed  matrix                S
                                
                                Laplasian                       L = S * S⁺
    
    

    путь Эйлера

    путь, содержащий все ребра, причем каждое ребро входит в путь единожды

    связный граф содержит путь Эйлера тогда и только тогда, когда все его вершины имеют четные степени

    import Test.HUnit
    import Data.List (nub)
    import Data.Graph
    import GHC.Arr (assocs)
    import Data.Monoid 
    import System.IO (hFlush, stdout)
    
    te = runTestTT $ TestLabel "" $ TestList $
       [ TestCase $ assertBool "" $ euler [(0,2),(1,3),(0,1),(2,3)]
       , TestCase $ assertBool "" $ euler [(0,1),(1,0),(0,0)]
       , TestCase $ assertBool "" $ euler [(0,1),(1,0)]
       , TestCase $ assertBool "" $ euler [(1,1)]
       , TestCase $ assertBool "" $ not $ euler [(0,1),(0,2),(0,3),(1,4),(2,4),(3,4)]
       , TestCase $ assertBool "" $ not $ euler [(0,1),(0,2),(0,3),(2,4),(3,4)]
       , TestCase $ assertBool "" $ not $ euler [(0,1),(1,0),(1,2)]
       , TestCase $ assertBool "" $ not $ euler [(0,1),(1,2)]
       , TestCase $ assertBool "" $ not $ euler [(0,1)]
       ]
    
    euler :: [Edge] -> Bool 
    euler xs = 
      let ys = mylst xs ; gr = buildG (minimum ys, maximum ys) xs  
      in getAll . mconcat $ zipWith 
        (\(_,y1) (_,y2) -> All $ mod (y1 + y2) 2 == 0) 
          (GHC.Arr.assocs $ indegree gr) 
          (GHC.Arr.assocs $ outdegree gr)
      where
        mylst:: [(Int,Int)] -> [Int]
        mylst xs = nub $ foldr (\(x , y) acc -> x : (y : acc)) [] xs
    
    main = putStr "input [(vi,vj)] : " >> hFlush stdout >> readLn >>= \xs -> putStrLn $ 
      if euler xs then "this is euler graph" else "this is not euler graph"
    

    путь Гамильтона

    путь, содержащий все вершины, причем каждая вершина входит в путь единожды

    любой турнирный (расщепленный, m = n >= 2, связный) граф содержит путь Гамильтона