Zeroability patterns of monomials in the sign-representation of boolean functions
Boolean fonksiyonların işaret gösterimindeki terimlerin sıfırlanma düzenleri
- Tez No: 463006
- Danışmanlar: DOÇ. DR. ERHAN ÖZTOP
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Boolean fonksiyonları, Boolean functions
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Boolean fonksiyonlar (BF) ayrık matematik alanındaki temel konulardan biridir. 1'i Yanlış ve -1'i Doğru olarak kabul edersek, bir BF'i tek bir polinomla ifade edebiliriz. Verilen BF'in katsayıları Lagrange interpolasyonu ile bulunabilir. Ne zaman tam interpolasyon işaret eşleşme kriteri ile değiştirilirse, verilen bir gerçeklik tablosu için sonsuz tane işaret temsili polinomu bulunabilir. Bir BF'i temsil etmek için yeterli, minimum sayıda terim içeren bir küme bulmak zor bir matematik problemidir. Bu tez bu problemin çözümüne, terimlerin BF'i temsil ederken sıfırlanabilme düzenlerini araştırarak katkı sunmayı hedeflemektedir. Bu amaçla, hangi terimler minimum işaret temsili polinomda olmak zorundadır sorusunu sorduk. Bu soru bizi küçük boyutlarda numerik araştırmalar yapmaya itti. Tüm üç ve dört değişkenli BF'ler için, elemanları bir arada sıfırlanabilen tüm alt kümeleri bulduk ve hangi monomial çiftlerinin birlikte herhangi bir işaret temsilinden eksik olup olamayacağını belirten, bir graf tanımı yaptık. Numerik araştırmalara ek olarak, üç elemanlı bir terim kümesi S, tüm elemanları bir arada bir BF'in işaret temsilinden çıkarılamıyorsa, S'in iki elemanlı alt kümelerinden en az bir tanesinin bu BF'in işaret temsilinden çıkarılamaz olduğunu ispatladık. Bu sonuçların bize, minimum terim sayısına yakın sayıda terim bulunduran, BF'lerin işaret temsili polinomlarını bulmamızı sağlayacak buluşsal bir algoritma bulma konusunda destek olmasını bekliyoruz.
Özet (Çeviri)
Boolean functions (BF) are one of the fundamental concepts in discrete mathematics. It is possible to represent any BF by a unique polynomial when one takes -1 as True and 1 as False. Coefficients of the polynomial representing the given BF can be found with Lagrange interpolation. When the exact interpolation criterion is replaced with the signmatch criterion, one can find infinitely many sign representing polynomials for a given truth table. The problem of finding a minimum number of monomial set that is sufficient to represent a BF is a difficult mathematical problem. This thesis aims to contribute to its solution by investigating the zeroability patterns of monomials. To this end, we asked which monomials must be in a minimum sign representing polynomial. This question drove us to make numerical investigations on the BFs in lower dimensions. For all 3- and 4-variable BFs, we found all the monomial subsets, whose elements can be zeroed and we introduced a graph representation indicating whether particular pairs of monomials could be absent from any sign representation. In addition to the numerical investigations, we have also proved that if a three-element monomial set S, could not be absent altogether from the sign representation of a BF, then there must be at least a two element subset of S which could not be absent in any sign representation of that BF. We expect these results will give support to the development of heuristic algorithms to construct close-to-minimum number of monomial sign representing polynomials for BFs.
Benzer Tezler
- Exploiting clustering patterns in training sets to improve classification performance of fully connected layers
Tam bağlantılı katmanların sınıflandırma performansını iyileştirmek için eğitim setlerindeki kümeleme örüntülerinden faydalanma
TOLGA AHMET KALAYCI
Doktora
İngilizce
2023
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. UMUT ASAN
- Generation of quantum emitters by introducing color centers inside diamond
Elmas içerisinde renk merkezleri oluşturularak kuantum emiterlerin üretilmesi
SEVİL BERRAK IRMAK ŞENTÜRK
Yüksek Lisans
İngilizce
2025
Fizik ve Fizik Mühendisliğiİstanbul Teknik ÜniversitesiMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ONUR ERGEN
- Modeling the dynamics of intergroup processes under social pressures of majority
Çoğunluğun sosyal baskıları altında gruplar arası süreçlerin dinamiklerinin modellenmesi
DOLUNAY UĞUR
Yüksek Lisans
İngilizce
2014
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. YAMAN BARLAS
- Analysis of slotted sectoral waveguide antenna arrays embedded in cylindrically stratified media
Silindirik katmanlı ortamlarda sektörel yarıklı dalga kılavuzu dizi antenlerin analizi
MERT KALFA
Yüksek Lisans
İngilizce
2013
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. VAKUR BEHÇET ERTÜRK
- Investigating the effects of hydrogen enrichment in a partially premixed methane-air flame
Kısmi karışımlı metan-hava alevinde hidrojen zenginleştirmesinin etkilerinin incelenmesi
MEHMET KAĞAN ADIGÜZEL
Yüksek Lisans
İngilizce
2025
Havacılık ve Uzay Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE GÜL GÜNGÖR