MiRaj.net.ru


MiRaj :: статьи

Language:
Russian
English

На главную
Статьи
Книги
Программы

Ссылки
Гостевая
Авторы









логин:  
пароль:


Регистрация
Выйти


return_links(1); ?>
return_links(1); ?>
Cчетчики:



Rambler's Top100 Союз образовательных сайтов

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

    Минимизация булевых функций в различных классах


  • М.А.Райцин П.С.Сухотюк "Программный комплекс «Карно» для минимизации булевых функций методом Закревского. (pdf) "
    Статья посвящена минимизации булевых функций методом Закревского (метод карт Карно). Авторы описывают программу, с высокой эффективностью реализовывающую данный метод. Программа и более детальная информация доступна в разделе программы

  • D.Brand T.Sasao "Minimization of ADN-EXOR expressions using rewrite rules. (pdf)"
    This paper considers conditions for generating optimal two-level AND-EXOR representations using rewrite rules. Four results are presented: temporary increase in the size of expressions during minimization, adding certain two rules to rule sets proposed in literature, defining tranformations that allow the minimization of an expression to proceed by minimizing a tranformed expression instead.

  • N.Song M.A.Perkowski "Minimization of exclusive sum of products expressions for multiple-valued input incompletely specified functions. (pdf)"
    This paper presents a new operation (Exorlink) and an algorithm to minimize Exclusive-OR Sum-of-Products expressions (ESOPs) for multiple valued input, two valued output, incompletely specified functions. Exorlink is a more powerful operation than the existing ones for this problem. Evaluation on benchmark functions is given and it proves the superiority of the program to those known from the literature.

  • М.А.Райцин "Представление булевых функций с помощью графов." (pdf)
    Автор предлагает использовать оригинальное представление булевых функций в виде булева графа. Данное представление позволяет получить рад преимуществ: простой и наглядный алгоритм минимизации, наглядное разбиение функции на сумму более простых булевых функций, каждая из которых может быть минимизирована отдельно, простая работа с неопределенными булевыми функциями. Описаны способы построения и некоторые свойства булевых графов, приведен алгоритм минимизации функций, представленной булевым графом.

  • П.В. Леончик "Программа минимизации системы булевых функций." (pdf)
    Предлагается программа минимизации системы полностью определенных булевых функций в классе ДНФ. Производится сравнительный анализ эффективности разработанного алгоритма, реализованного в программе Tie и программы Espresso, широко используемого в настоящее время программного продукта]. Приводятся результаты экспериментально-статистических испытаний алгоритмов на псевдослучайных булевых функциях и стандартных примерах Benchmark.

  • М.А.Райцин "Минимизация СЧБФ на графах." (pdf) (286 Kb)
    Представлен алгоритм минимизации СЧБФ (систем частично определенных булевых функций), сложность которого зависит от входных данных как N*m*f(n), где N - число точек в графе( тождественных точек булевой функции), m-число функций, |f(n1)-f(n2)| << |n1-n2|, n - число переменнных. В качестве внутреннего представления используется оригинальное представление функций в виде булева графа. Получены практические результаты - написан и протестирован программный комплекс, реализующий описаный алгоритм.

  • A. Gaidukov "Algoritm to derive minimum ESOPs for 6-variable function" (djvu) [370Kb]
    This paper consider the most complex functions for exclusive-or sum-of-products expressions (ESOPs). Specially, it derives the number of products required for representation such fucntions by minimal ESOPs (MESOPSs). First, an efficient algotithm to derive a minimum ESOP for an arbitrary function of 6 variables is presented. Then, by using this algorithm an algorithm to derive class of all the most complex functions of 6 variables is shown.

  • B. Steinbach, V. Yanchurkin, M. Lucas "On SNF Optimization: a functional compression of methods" (pdf) [311Kb]
    In this paper authors present a comparative study on methods calculating the special normal form (SNF) allowing an exact ESOP minimum representation. SNF [1] evaluation is shown to be highly practical and demonstrated results prove its real application in functional ESOP minimization and evaluation of the complexity and of the structure of Boolean functions.

  • B. Steinbach, A. Mishchenko "SNF: A Special Normal Form for ESOPs" (pdf) [311Kb]
    This paper introduces a new normal form for ESOPs of completely specified Boolean functions. Authors study the properties of the SNF and show its special place among canonical Reed-Muller representations.

    Каноническое представление, свойства инерции б.ф.


  • М.А.Райцин "О некоторых свойствах групп инерции булевых функций." (pdf) (131 Kb)
    В работе исследованы некоторые свойства симметрии бесповторных булевых функций. Этот вопрос представляет интерес при решении задач тестирования, эквивалентных преобразований и канонического преобразования бесповторных функций. Рассмотрены свойства симметрии собственно-бесповторных функций 4 переменных в базисе функций не более 3 переменных. Получена классификация функций 4 переменных по распределению мощностей классов эквивалентности. Сформулирован ряд утверждений о симметрии булевых функций произвольного числа переменных.

    Задача Штейнера


  • М.А.Райцин П.С.Сухотюк "Программная система для исследования задачи Штейнера на плоскости" (pdf)
    Статья, посвященная исследованию задачи Штейнера на плоскости. Авторы статьи приводят описание программы, позволяющей визуализировать области возможных точек Штейнера, а также найти оптимальную точку для введенного множества вершин. Программа, описанная в статье доступна в разделе программы

  • Joseph L Ganley and James P Cohoon "Optimal Rectilinear Steiner Minimal Trees in O(nn2.62n) time" (165 Kb) (pdf)
    This paper presents an algorithm that computes an optimal rectilinear Steiner minimal tree of n points in at most O(n^2 * 2.62^n)time. For instances small enough to solve in practice this time bound is provably faster than any previous algorithm and improves the previous best bound for practically solvable instances which is O(n * 3^n).

  • Simonel L. Martins, Panos M. Pardalos, Mauricio G.C. Resende "GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES" (165 Kb) (pdf)
    We describe four versions of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions of general instances of the Steiner Problem in Graphs. Different construction and local search algorithms are presented. Preliminary computational results with one of the versions on a variety of test problems are reported. On the majority of instances from the OR-Library, a set of standard test problems, the GRASP produced optimal solutions. On those that optimal solutions were not found, the GRASP found good quality approximate solutions.

  • Weiping Shi Chen Su "The Rectilinear Steiner Arborescence Problem is NP-Complete" (315 Kb) (pdf)
    Given a set P of points in the 1st quadrant, a Rectilinear Steiner Arborescence (RSA) is a directed tree rooted at the origin, containing all points in P, and composed solely of horizontal and vertical edges oriented from left to right, or from bottom to top. The complexity of finding an RSA with the minimum total edge length for general planar point sets has been a major open problem, and has important applications in VLSI. In this paper, we prove the problem is strongly NP-complete. The proof also shows the Euclidean version of the Steiner Arborescence problem is NP-hard.

  • "Задача Штейнера и большие массы." (244 Kb) (pdf)
    Авторов статьи итересуют механические аналогии задачи Штейнера, когда минимум длины интерпретируется как некий экстремальный энергетический принцип для механической системы. В качестве "заданных" точек дерева Штейнера выступают очень массивные звезды, а в качестве добавочных, или точек Штейнера фигурируют звезды масса которых несколько меньше. Тогда положение с максимальной потенциальной энергией будет отличаться тем, что звезды средней массы или "точки Штейнера" расположатся так, что каждая будет лежать в плоскости трех своих ближайших соседей. Авторами ставится вопрос: можно ли получить информацию о местонахождении планет или баз отправителей зонда используя помощи гравитационной аналогии.

    Разное


  • С.Ф. Винокуров, А.С. Казимиров "Верхняя оценка сложности булевых функций в классе ПНФ. (pdf)"
    В работе рассматривается сложность L(n) представления булевых функций в классе полиномиальных нормальных форм. Показано, что для любой функции 7 переменных минимальная ПНФ содержит не более 28 слагаемых. Эта оценка также обобщена для большего числа переменных.

  • А.С. Казимиров "Оценка числа классов LP-эквивалентности булевых функций. (pdf)"
    В работе рассматривается LP-эквивалентность булевых функций, сохраняющая сложность в полиномиальных нормальных формах. Получена асимптотическая оценка для числа классов LP-эквивалентности.

  • П.С.Сухотюк "Оптимизация доступа к данным." (pdf)
    В данной статье описывается метод оптимизации организации и доступа к иерархическим данным. Автор предлагает использовать многоуровневое хеширование данных в B-дереве. Обсуждение данной темы ведется на LJ-ленте по адресу http://infodepot.livejournal.com

На главную | Статьи | Книги | Программы | Ссылки | Гостевая | Регистрация| Авторы

Allbest.ru : поиск по научно-образовательным ресурсам


return_links(1); ?>

return_links(1); ?>

return_links(1); ?>
Copyright © 2006 Михаил Райцин
Последнее обновление: