Resumo: Este relatório técnico contém os resumos de 07 trabalhos autorizados a serem publicados de um total de 34 trabalhos apresentados no XII Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica (WTD), do Instituto de Computação (IC) da Universidade Estadual de Campinas (Unicamp) do ano de 2017. O Workshop ocorreu entre os dias 31 de Julho e 2 de Agosto de 2017 e contou com cerca de 210 participantes, entre ouvintes, apresentadores de trabalhos e organizadores. Na ocasião foram realizadas 28 apresentações orais e uma sessão de Pôsteres com 06 trabalhos. Aos alunos foi dada a possibilidade de escolher a forma de apresentação (oral, pôster), bem como escolher se desejasse publicar o seu trabalho nos anais do evento. A publicação dos resumos, sob forma de relatório técnico, tem por objetivo divulgar os trabalhos em andamento e registrar, de forma sucinta, o estado da arte da pesquisa do Instituto de Computação no ano de 2017.
Abstract: Model based testing is a well-established approach to test reactive systems. One of the challenges stemming from model based testing is the generation of test suites, specially when completeness is a required property these test suites. In order to check whether an implementation under test is in compliance with its respective specification model one resorts to some form of a conformance relation that guarantees some expected behavior of the implementations, given the behavior of the specification. The ioco conformance relation is an example of such a relation, specially suited for reactive and asynchronous models. In this work we study a more general conformance relation for such models. We also describe a method to generate finite and complete test suites which are complete in general, and we also discuss the complexity of the generation mechanism, as well as the complexity of testing implementations under this more general conformance relation. We show that ioco conformance is a special case of this new conformance relation, for two classes of fault models, and we also investigate the complexity of generating complete test suites for these fault models, and also the complexity of running verification experiments using the test suites so generated.
Abstract: This work is a partial report related to the development and assessment of a Concept Inventory to Introductory Programming Courses. A Concept Inventory is a set of multiple-choice questions that address specific misunderstandings and misconceptions of the students. In previous works, through instructor interviews, exam analysis, an online pilot test and interviews with students, we identified a list of 33 misconceptions related to 7 programming topics in C language. On this report we describe each one of these misconceptions, following an antipattern template composed by: code (a label to identify the misconception); name; description; rationale (the reason why we hypothesise the misconception happens); consequences; detection (where and how the misconception appears); and improvement (how to prevent the misconception).
-labellings of lobsters and
trees with a perfect matching.
Abstract: A graceful labelling of a tree
is an injective function
such that
. An
with the additional property that there exists an integer
such that, for each edge
, either
or
. In this work, we prove that the following families of trees with maximum degree three have
-legs and with at most one forbidden ending; trees
such that the contraction
has a balanced bipartition and an
Abstract: A graceful labelling of a tree
is an injective function
such that
. A tree
, there exists a graceful labelling
of
. In this work, it is proved that if
and, for every non-leaf vertex
is at least
, then
-rotatable. This result reinforces the conjecture that every caterpillar with diameter at least five is 0-rotatable.
Abstract: A graceful labelling of a tree
is an injective function
such that
. A tree
, there exists a graceful labelling
of
. In this work, it is proved that the following families of caterpillars are 0-rotatable: caterpillars with a perfect matching; caterpillars obtained by identifying a central vertex of a path
with a vertex of
; caterpillars obtained by linking one leaf of the star
to a leaf of a path
and
; and caterpillars with diameter five or six. These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable.
Resumo: Começamos a reestruturar estas notas em 2016, quando Meidanis esteve em licença sabática na Universidade de Ottawa, no laboratório de David Sankoff. Usamos o termo “reestruturar” porque os principais resultados exibidos aqui, sobre genomas minimax sob a distância de posto, apareceram primeiro no texto apresentado por Biller em seu exame de qualificação para o doutorado, escrito em 2014. O conteúdo é dividido em seis capítulos, como segue. No Capítulo 1 introduzimos as primeiras definições, incluindo matrizes genômicas, distância, e órbitas. Também derivamos uma importante fórmula para a distância com base em órbitas. No Capítulo 2 definimos operações em genomas, com foco naquelas de posto pequeno. O capítulo se encerra com a definição de operações básicas, a saber, cortes, junções, e duplas trocas. No Capítulo 3 estudamos cenários de ordenação indo de um genoma para outro através de operações básicas. Mostramos que a partir de cada genoma podemos alcançar qualquer outro com tais cenários. Isto fornece ademais uma forma alternativa de calcular a distância. Genomas intermediários são o tópico do Capítulo 4. Eles podem ser caracterizados como membros de cenários ótimos, ou como genomas para os quais se verifica igualdade na desigualdade triangular. Eles são também as medianas de dois genomas. Uma noção relacionada é a noção de genomas minimax, explorada no Capítulo 5. Estabelecemos um limite inferior para a pontuação minimax, e mostramos exatamente os casos onde é possível atingir este limite. Em qualquer caso, é sempre possível encontrar um genoma a menos de uma unidade do limite inferior. Finalmente, o Capítulo 6 lida com uma interessante propriedade de paridade da distância de posto.
Abstract: We started the work of reshaping these notes in 2016, when Meidanis was on sabbatical at the University of Ottawa, in David Sankoff's lab. We use the term “reshaping” because the main results shown here, on minimax genomes under the rank distance, were first presented in Biller's text for her PhD qualifying exam, written in 2014. The contents are divided in six chapters, as follows. In Chapter 1 we introduce the first definitions, including genome matrices, distance, and orbits. We also derive an important formula for the distance based on orbits. In Chapter 2 we define operations on genomes, with focus on those with small rank. The chapter closes with the definition of basic operations, namely, cuts, joins, and double swaps. In Chapter 3 we study sorting scenarios going from a genome to another by basic operations. We show that from every genome we can reach any other with such scenarios. This also provides an alternative way of computing the distance. Intermediate genomes are the topic of Chapter 4. They can be characterized both as optimal scenario members, and as genomes for which the triangle inequality becomes an equality. They are also the medians of two genomes. A related notion is that of a minimax genome, explored in Chapter 5. We establish a lower bound for the minimax score, and show exactly the cases where it is possible to achieve such a score. In any case, it is always possible to find a genome within 1 unit of the lower bound. Finally, Chapter 6 deals with an interesting parity property of the rank distance.
Abstract: Model based testing is a well-established approach to test reactive systems described by formal models. In this paper we look at the problem of generating complete test suite for reactive systems formally described as Input Output Labeled Transition Systems (IOLTSs). In this work we propose a new notion of conformance relation for IOLTS models based on formal languages and automata. We show that this new conformance relation is more general than the well-studied ioco conformance relation. We then describe how to generate test suites that are sound and exhaustive for a given specification model, according to the new conformance relation. We impose no restrictions on the structure of the specification model, a distinct advantage when compared to other recent works.
Resumo: This technical report proposes a Routing, Core and Spectrum Assignment (RCSA) algorithm based on image processing Inscribed rectangle algorithm. The solution aims at discovering portions of spectrum capable of accommodating requests with low computational complexity. Advanced fitting policies are proposed to chose which portion of the spectrum to reduce of blocking and crosstalk. Results show that the proposed algorithm can reduce the blocking ratio under low loads and crosstalk under all loads, when compared to other RCSA algorithms in the literature.
Resumo: This technical report introduces a novel Routing, Core and Spectrum Assignment (RCSA) algorithm based on the Connected Component Labelling (CCL) algorithm. The RCSA algorithm represents the spectrum of multicore fibers as matrices and the CCL algorithm discovers with low computational complexity the available spectrum to allocate to a connection request. Spectrum fitting policies are also proposed to be jointly employed with the CCL algorithm. Results show the feasibility of utilizing image processing algorithms such as the CCL in RCSA algorithms, given that they demand low computational complexity and yet produce low blocking ratio.
Resumo: Information and Communication Technology activities consumed 4% of the world energy in 2009, and such consumption will continue to increase due to the traffic growth of the Internet predicted for the next years. Techniques to make the core of the network more energy efficient has been proposed, among them, green routing has been considered a promising technique. This technical report proposes a novel Routing, Modulation Level and Spectrum Assignment (RMLSA) algorithm for elastic optical networks that considers the energy consumption of potential routes. Results indicate that this algorithm can save up to 34% energy and produce bandwidth blocking ratio two orders of magnitude lower than existing energy aware RMLSA algorithms.
Resumo: This technical report introduces a novel traffic grooming algorithm for the connection establishment of deadline-driven requests in elastic optical networks, named Elastic Batch Grooming Algorithm. The algorithm grooms batches of requests to establish lightpaths with diverse bandwidth demands with deadline requirements. Results show that the algorithm significantly reduces the blocking ratio and the number of demanded transponder when compared to traditional non-batch algorithms.
Abstract: Modern systems need to able to self-adapt to changing user needs and system environments. Examples of systems that demand self-adaptive capabilities include mobile devices applications that should deal with environmental changes and service-oriented systems that should replace unreliable services on-the-fly. In this context, dynamic software product line (DSPL) is an engineering approach for developing adaptive systems based on commonalities and variabilities for a family of similar systems. However, researchers have reported that many DSPL solutions fail to meet all the system’s adaptability requirements, and in many cases, they are developed in ad hoc manner. This paper surveys various DSPL solutions, evaluates and compares their different design strategies. A two-dimension taxonomy is specified to address basic technical issues for a given DSPL proposal. The DSPL dimension classifies the different design choices for implementing variability schemes, and for creating different kinds of feature models. The Self-adaptation dimension classifies the different design choices for the adaptation requirements and for the MAPE-K control loop implementation. Practical issues and difficulties are summarized, major trends in actual DSPL proposals are identified, and directions for future work are suggested.
Abstract: In optical networks, failures can imply in great loss of data due to high transmission rates, leading to the need of employment of protection mechanisms. This paper introduces a novel algorithm to provide Failure-independent path protecting p-cycle with minimum interference for path protection in elastic optical networks using space division multiplexing. The proposed protection algorithm reduces rejections of future requests and make no assumption about specific patterns of arrival of requests. The algorithm is compared to FIPPMC algorithm and a algorithm based on methods of []. Results indicate that the 100% protection for single failures can be provided by the proposed algorithm.
Abstract: In recent years, elastic optical networks have emerged as a solution for dealing with the diversity of the bandwidth demands of network applications. The use of only two multiplexing dimensions has limited the network capacity. To ameliorate this problem, a third dimension has been added in space-division multiplexing (SDM). As transmission rates increase so does the need for protection against network failures. Among the protection schemes, those protecting paths are of great interest due to their end-to- end solutions. This paper introduces a novel algorithm based on p-cycle to provide failure-independent path protection in elastic optical networks with SDM.
Abstract: Informally, total order broadcast protocols allow processes to send messages with the guarantee that all processes eventually deliver the messages in the same order. In this paper, we investigate the efficiency and performance of On-Time Fast Paxos a synchronous total order broadcast protocol for the crash-recover failure model that is built atop a broadcast-based asynchronous distributed system. On-Time Fast Paxos combines an asynchronous consensus protocol, Fast Paxos, with a synchronous communication protocol while guaranteeing the original safety and liveness properties of Fast Paxos. The synchronous communication protocol relies on virtual global time to create the synchronicity necessary to make Fast Paxos work at its theoretical optimum, two communication steps. Experimental results allow us to conclude that On-Time Fast Paxos performs very well both in terms of throughput and latency, reaches 960mbps in a 1Gbps network with an average latency of 2ms. Finally, its novel hybrid design, asynchronous layer driven by a synchronous layer, shows that, time and synchrony be used to improve the performance of total order broadcast protocols.
Resumo: Aplicamos o algoritmo geral top-down para a aproximação adaptativa em multinível HApp, descrito na Parte I deste artigo, para um tipo específico de bases de função de aproximação que chamamos de bases regulares em multinível. O algoritmo garante um erro máximo de aproximação especificado em cada ponto de amostragem. Embora a base adaptativa resultante não seja necessariamente mínima, esta pode ser muito menor do que a base completa, para as funções a ser aproximadas com detalhes locais em várias escalas de resolução espacial. Os elementos da base são splines tensoriais com suporte compacto. Estas bases são semelhantes à bases wavelet padrão, exceto que elas fornecem fórmulas analíticas para a função de aproximação; que podem ser utilizados, por exemplo, para diferenciação e interpolação entre os pontos de amostragem. Nesta parte do artigo, assumimos uma grade regular de Pontos de amostragem e um domínio tipo caixa com topológia toroidal. Estas escolhas permitem economias consideráveis de tempo de computação. Também utilizamos em cada nível um operador modificados de mínimo quadrados com rejeição Bayesiana de outlier.
|
Instituto de Computação ::
Universidade Estadual de Campinas
Av. Albert Einstein, 1251 - Cidade Universitária Zeferino Vaz • 13083-852 Campinas, SP - Brasil • Fone: [19] 3521-5838 |