Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T12:52:36Z
No. of bitstreams: 2
Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T14:10:30Z (GMT) No. of bitstreams: 2
Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-16T14:10:30Z (GMT). No. of bitstreams: 2
Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2011-08-26 / Intuitively, the basic idea of Design Theory consists of a way to select subsets, also called
blocks, of a finite set, so that some properties are satisfied. The more general case are the
blocks designs. A PBD is an ordered pair (S;B), where S is a finite set of symbols, and B
is a collection of subsets of S called blocks, such that each pair of distinct elements of S
occur together in exactly one block of B. A Steiner Triple System is a particular case of a
PBD, where every block has size only 3, being called triples. The main focus is in building
technology systems. By resolvability is discussed as a Steiner Triple Systems is resolvable,
and when it is not resolvable. This theory has several applications, eg, embeddings and
even problems related to computational complexity. / Intuitivamente, a idéia básica de um Planejamento Combinatório consiste em uma
maneira de selecionar subconjuntos, também chamados de blocos, de um conjunto finito,
de modo que algumas propriedades especificadas sejam satisfeitas. O caso mais geral são
os planejamentos balanceados. Um PBD é um par ordenado (S;B), onde S é um conjunto
finito de símbolos, e B é uma coleção de subconjuntos de S chamados blocos, tais que cada
par de elementos distintos de S ocorrem juntos em exatamente um bloco de B. Um Sistema
Triplo de Steiner é um caso particular de um PBD, em que todos os blocos tem tamanho
único 3, sendo chamados de triplas. O foco principal está nas técnicas de construção dos
sistemas. Por meio da resolubilidade se discute quando um Sistema Triplo de Steiner é
resolvível e quando não é resolvível. Esta teoria possui várias aplicações, por exemplo:
imersões e até mesmo problemas relacionados à complexidade computacional.
Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3074 |
Date | 26 August 2011 |
Creators | Barbosa, Enio Perez Rodrigues |
Contributors | Barbosa, Rommel Melgaço |
Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | English |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Format | application/pdf |
Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
Relation | -3303550325223384799, 600, 600, 600, -7712266734633644768, 3671711205811204509, [1] BILLINGTON, E.; LINDNER, C. Embedding 5-cycle systems into pentagon triple systems. Discrete Mathematics, 309(14):4828–4834, 2009. [2] BONDY, J.; MURTY, U. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008. [3] BRYANT, D.; HORSLEY, D. A proof of lindner’s conjecture on embeddings of partial steiner triple systems. Journal of Combinatorial Designs, 17(1):63–89, 2009. [4] CAMTEPE, S.; YENER, B. Combinatorial design of key distribution mechanisms for wireless sensor networks. Computer Security–ESORICS 2004, p. 293–308, 2004. [5] CHING LI, B.; VAN REES, G. Existence of non-resolvable steiner triple systems. Journal of Combinatorial Designs, 13(1):16–24, 2005. [6] COLBOURN, C. Embedding partial steiner triple systems is np-complete. Journal of Combinatorial Theory, Series A, 35(1):100–105, 1983. [7] COLBOURN, C.; DINITZ, J. Handbook of Combinatorial Designs, (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, 2007. [8] COLBOURN, C.; DINITZ, J.; STINSON, D.; OF WATERLOO. DEPT. OF COMBINATORICS, U.; OPTIMIZATION.; OF WATERLOO. FACULTY OF MATHEMATICS, U. Applications of combinatorial designs to communications, cryptography, and networking. Citeseer, 1999. [9] COLBOURN, C.; VAN OORSCHOT, P. Applications of combinatorial designs in computer science. ACM Computing Surveys (CSUR), 21(2):223–250, 1989. [10] CORMEN, T. Introduction to algorithms. The MIT press, 2001. [11] DIESTEL, R. Graph theory, Graduate Texts in Mathematics Vol. 173. Springer- Verlag, New York, 2000. Referências Bibliográficas 89 [12] DINITZ, J.; STINSON, D. Contemporary design theory: A collection of Surveys, volume 26. Wiley-Interscience, 1992. [13] DOMINGUES, H.; IEZZI, G. Álgebra moderna. Atual Editora, 2003. [14] DOYEN RICHARD M, J. Embeddings of steiner triple systems. Discrete Mathematics, 5(3):229–239, 1973. [15] DUKES, P.; LAMKEN, E.; WILSON, R. Combinatorial design theory. 2008. [16] GAREY, M.; JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman & Co., 1979. [17] GONÇALVES, A. Introdução à Álgebra. Instituto de Matemática Pura e Aplicada, 2001. [18] GRANNELL, M.; GRIGGS, T.; SIRAN, J. Surface embeddings of steiner triple systems. Journal of Combinatorial Designs, 6(5):325–336, 1998. [19] LAYWINE, C.; MULLEN, G. Discrete mathematics using Latin squares, volume 49. Wiley-Interscience, 1998. [20] LI, P.; TOULOUSE, M. Some np-completeness results on partial steiner triple systems and parallel classes. Ars Combinatoria, 80:45–52, 2006. [21] LINDNER, C.; QUATTROCCHI, G.; RODGER, C. Embedding steiner triple systems in hexagon triple systems. Discrete Mathematics, 309(2):487–490, 2009. [22] LINDNER, C.; RODGER, C. Design theory. Chapman & Hall/CRC, 2009. [23] MESZKA, M.; ROSA, A.; ZIOLO, I. Steiner almost self-complementary graphs and halving near-steiner triple systems. Discrete Mathematics, 309(18):5650–5654, 2009. [24] RAY-CHAUDHURI, D.; WILSON, R. Solution of kirkman’s schoolgirl problem. In: Proc. Symp. Pure Math, volume 19, p. 187–203, 1971. [25] ROSEN, K. Discrete mathematics and its applications. McGraw-Hill, 2003. [26] SCHEINERMAN, E. Matemática Discreta: Uma Introdução. Pioneira Thomson Learning, 2003. [27] SILVA, V. V. D. Números: Construção e Propriedades. Editora UFG, 2003. [28] SIPSER, M.; DE QUEIROZ, R. Introdução à teoria da computação. Thomson Learning, 2007. Referências Bibliográficas 90 [29] WALLIS, W. Introduction to Combinatorial Designs, (Discrete Mathematics and Applications). Chapman & Hall/CRC, 2007. [30] WEST, D.; OTHERS. Introduction to graph theory, volume 1. Prentice Hall Upper Saddle River, NJ, 2001 |
Page generated in 0.0029 seconds