Dissertation Abstracts 1969-1973 For any information, please contact bib-di@inf.puc-rio.br 1969 69_MSc_furtado Antonio Luz FURTADO. Calculo automatico de distancias em ferrovias. M.Sc.Diss. Presentation: 01/69 Port. 71 p. Advisor: Antonio Cesar Olinto de Oliveira Abstract: Most applications of computers to railway problems use the distances between stations data. In some cases the distance must be broken down for statistical purposes and for the same reason the upward or downward traffic must be discriminated. The present work suggests a method for obtaining such information directly in core storage, without requiring therefore a time consuming access to disk or tape files. Two applications are in operation: a. in the Viacao Ferrea Centro Oeste - by Drs. Geraldo Siqueira, Paulo Mazoni and the author; b. in the Estrada de Ferro Central do Brasil by an IBM team. 69_MSc_staa Arndt von STAA. Um modelo de aprendizado para jogos em computadores. M.Sc.Diss. Presentation: 09/69 Port. 46 p. Advisor: Antonio Cesar Olinto de Oliveira Abstract: Some models of artificial intelligence will be presented in this text. All the models concern games. Simple games have been chosen to reduce coding and rule analysis. The games analyzed will be two and three dimensional tic-tac-toe. Different models of learning will be given and their behavior will be analyzed. Also the programs will enable the computer to play against one person, or against itself. All models concerning these two games are the result of my own work, independent of any texts. Perhaps some or all components of the procedures presented have been developed before. 69_MSc_silva Raphael Chrisostomo Barbosa da SILVA. Sistema integrado de administracao academica. M.Sc.Diss. Presentation: 01/69 Port. 95 p. Advisor: Antonio Cesar Olinto de Oliveira Abstract: In the Universities that adopt the credit system, as a rule for the evaluation of academic performance, the processing and follow-up of the students academic life becomes a complex task. The integrated System for Academic Administration enables the Admissions and Register office to process mechanically the jobs that have a large volume of data, and creates the possibility of obtaining statistics and analysis report on the students academic life. The system is composed of subsystems, that work upon two files, the student file and the subject file, and executes the processing functions of the Registrar office from registration to the end of the course. This system was implemented at the Pontifical Catholic University of Rio de Janeiro, in 1968, by the author. 69_MSc_carvalho Roberto Lins de CARVALHO. Simplificacoes em gramaticas "context-free" reducao a forma normal de Chomsky: reconhecimento e analise de palavras. M.Sc.Diss. Port. Presentation: 11/69 64 [+42] p. Advisor: Carlos Jose Pereira de Lucena Abstract: The purpose of this work is to demonstrate results about simplifications of context-free languages, reduction to Chomsky's normal form and construction of a general algorithm for expression recognition and analysis. All theorems are demonstrated constructively and are followed by the corresponding algorithms. Originality lies solely in the presentation that makes evident the application of theorems whose practical aspects are frequently not considered. 69_MSc_carvalho Sergio Eduardo Rodrigues de CARVALHO. Implementacao do sistema COMASS. M.Sc.Diss. Port. Presentation: 09/69 39 [+138] p. Advisor: Arndt von Staa Abstract: COMASS (COMpiler ASSembler) is the name given to a programming system capable of generating other systems, such as operating systems and compilers. The works described here is referred to the COMASS implementations as a high level language compiler. It contains descriptions of the programs which constitutes the basic structure of the system (the translator, the recognizer and the generator) as well as descriptions of the languages involved (the COMASS meta-language, the source language and the intermediate code). 69_MSc_toscani Simao Sirineo TOSCANI. Recursividade em FORTRAN. M.Sc.Diss. Port. Presentation: 11/69 48 p. Advisor: Raphael Chrisostomo Barbosa da Silva Abstract: This work was developed with the purpose of allowing the use of recursive subprograms in the FORTRAN language. Changes were made on the FORTRAN IV Compiler of the IBM 7044 Computer and an auxiliary subroutine was inserted into the operating system subroutine library, to accomplish the necessary stack manipulation. ---------------------------------------------- 1970 70_MSc_tanabe Akeo TANABE. Caminhamento em grafos simetricos. M.Sc.Diss. Port. Presentation: 12/70 44 [+20] p. Advisor: Antonio Luz Furtado Abstract: Given the incidence matrix and two edges of a symmetric graph the algorithm presented in this work finds all paths joining them. An information structure is one of the possible outcomes of the algorithm. Once it has been generated, it can be used in any application involving traversing a network, thus allowing a fast processing that avoids the use of auxiliary storage. 70_MSc_salim Cesar Simoes SALIM. Metodos numericos para solucao de sistemas lineares e estudo de autovalores e autovetores. M.Sc.Diss. Port. Presentation: 06/70 100 [+139] p. Advisor: Jose Roberto Ribeiro dos Santos Abstract: This work consists of a study of linear systems involving matrix inversion and evaluation or determinants and the obtention of the eigenvalues and eigenvectors from any real or complex matrix. Each given method has its description and mathematical discussion in the text and also a subroutine and sample program in the appendix, both written in FORTRAN language. It is given special emphasis to elementary and similar transformations in the mathematical approach and both exact and iterative methods are presented. In the chapter about the solution of linear systems it is studied the classical methods of Gauss, Gauss-Jordan and its optimization, special procedures as Cholesky's, conjugate directions and conjugate gradients (for symmetric and general matrices) and iterative processes as Jacobi's, Gauss-Seidel and Relaxation. In the second section, the eigenvalues and eigenvectors of real symmetric matrices are obtained by the methods of Jacobi and Givens-Housenholder, while those of general complex matrices are calculated by the method of Francis. It may be used either for a first course in numerical analysis or a second one in numerical calculus. Some knowledge of linear analysis and FORTRAN programming is required for its total understanding. 70_MSc_dias Donaldo de Souza DIAS. Analise e projeto de sistemas de processamento de informacoes. M.Sc.Diss. Port. Presentation: 11/70 106 p. Advisor: Carlos Jose Pereira de Lucena Abstract: The present work suggests an outline for a course in Computer Information Systems: Analysis and Design. The basic Systems Analysis topics are presented along with some usual business Data-Processing applications. With this approach the subject becomes more attractive to the student. The course may be given as an elective in a Post-Graduate Program in Computer or Management Science or as a compulsory course in a Systems Analysis Program. 70_MSc_carvalho Frederico Guilherme de CARVALHO. NAP - Um montador de linguagem Assembler para o computador IBM 1130. M.Sc.Diss. Port. Presentation: 12/70 42 [+ 99] p. Advisor: Mario Aloysio Telles Ribeiro Abstract: The new Assembler Program (NAP) for the IBM 1130 Computing System was developed as a fulfillment of the requirements to the Master degree in Computer Sciences (PUC-1970). The main objective we had, during NAP's development, was to provide the IBM 1130 with a language that could: have better efficiency, giving shorter assembling time; present new features, to minimize programming effort; be easily expanded with other features; be used as an intermediate language to new compilers for the IBM 1130. So, the Assembler Program described in the following text has these main features: assembling time is 15% faster that that of the Assembler Program of IBM 1130; the assembled language may contain literal and some pre-defined macros; program modularity permits to introduce new phases to assemble new instructions; the availability of the source deck to make it easy to link NAP with new compilers for the IBM 1130. 70_MSc_quintella Heitor Luiz Murat de Meirelles QUINTELLA. Um enfoque computacional de teoria dos numeros e resolucao das equacoes diofantinas lineares. M.Sc.Diss. Port. Presentation: 20/12/70 94 p. Advisor: Roberto Lins de Carvalho Abstract: In this work the necessary foundations of number theory are presented for the solution of linear diophantine equations by means of a computational approach. Moreover, techniques are described for the solution of the linear diophantine equations, the linear diophantine inequalities and systems of simultaneous linear diophantine equations. From a didactic point of view the development of algorithms of number theory is an excellent opportunity to reformulate the constant of the introduction to Computer Science course. This has the advantage of focusing the difficulty of this course in the techniques of programming rather than in methods and applications. The interdisciplinary nature of this work provides a bridge for several disciplines, for the mathematician the algorithms provide an efficient tool for equations manipulation, thereby making his work easier and stimulating research in this field. In a practical way this work gives an alternative to the solution of linear integer programming problems. Perhaps the methods herein presented are more efficient than those traditionally used. Even if the diophantine methods were less efficient they could still be useful in teaching linear integer programming without the need for linear algebra, and the number theory as a whole could help for a formal approach to simulation. 70_MSc_salim Helene Kleinberger SALIM. Metodos numericos aplicados a interpolacao e aproximacao de funcoes e raizes de sistemas nao lineares. M.Sc.Diss. Port. Presentation: 06/70 151 [+100] p. Advisor: Jose Roberto Ribeiro dos Santos Abstract: This work is about specific topics of Numerical Analysis, applied to scientific computation. The articles presented are, generally, the following: a) The study of the determination of roots of real general functions. In this chapter we see at first the separation of real or complex roots of a general function, particularizing for algebraic polynomials. In order to determine the roots we show iterative methods such as linear iteration and procedures of higher order of convergence, the Aitken's sequence and Newton Raphson's method for simple or multiple, real or complex roots. In the part dedicated to the polynomials, we see a procedure to obtain simultaneously approximations to all its real zeros, the particularization of Newton - Raphson's method for the refinement of the approximations for the roots and a process of factorization of the polynomial in order to find pairs of complex roots. b ) The resolution of systems of nonlinear equations. We see the methods iteration, Seidel's and Newton's. c) The problem of polynomial interpolation. We develop formulae to obtain the interpolating polynomial through a finite set of points and osculating polynomials. d) Numerical differentiation. At this point we derive the polynomial approximations to the function and we see the method of extrapolation to the limit. e) Numerical integration. In this section we study the Newton Cotes formulae, obtained from the interpolating polynomials and the process of extrapolation to the limit applied to integration. We also have the problem of double integrals. f) Approximation to functions. This chapter presents an introduction linear analysis which is necessary to the study of Fourier's, Legendre's, Hermite's and Languerre's series, the method of least squares applied to functions given analytically or by points, and the study of Gauss' quadrature. We searched for simple and programmable methods, and we present their mathematical justification. We studied the error and order of convergence of the several methods presented. Some algorithms are followed by tested subroutines, in appendices, written in FORTRAN, and processed at the installation of the National Spatial Activities Commission (B- 3 500). The objective of this thesis is to serve as a textbook for a first, one semester course in Numerical Analysis, requiring knowledge of programming and linear algebra. 70_MSc_martins Luiz de Castro MARTINS. Programa de manutencao preventiva de um equipamento. M.Sc.Diss. Port. Presentation: 01/70 37 [+42] p. Advisor: Antonio Cesar Olinto de Oliveira Abstract: The problem of preventative maintenance planning for a system becomes more difficult as the number of system components increases. This study presents a computational solution to the problem of minimizing the weekly work load fluctuations of a maintenance department over a one year period. Three algorithms are developed which provide adequate solutions to different formulations of the planning problem. These algorithms are: simulation by random solutions; load sorting; partial solutions. The results obtained by means of the algorithm were excellent. In the ten cases studied, the weekly load profiles over a one year period exhibited small fluctuations. Also, a theoretical formulation of the problem is presented by means of Fourier Series expansions. 70_MSc_brown Marcelo Prado BROWN. Estudo comparativo de tabelas de simbolos. M.Sc.Diss. Port. Presentation: 12/70 81 p. Advisor: Arndt von Staa Abstract: This work presents a comparison among several techniques for searching through symbol tables. Processing time and storage space are independent variables. The techniques compared are: binary search and hash code of the type linear, quadratic and with overflow tables. Algorithms for these techniques are presented, including a few extensions of these. The processing time variables are measured for construction and search, each of these actions listed separately. Also presented is a chapter discussing the code generation' processes (hash code), showing a comparison among some of them. 70_MSc_santos Sueli Mendes dos SANTOS. Gramatica Transformacional - discussao sobre um modelo para as linguagens naturais. M.Sc.Diss. Port. Presentation: 11/70 64 p. Advisor: Roberto Lins de Carvalho Abstract: The aim of this paper is to present Transformational Grammars as possible models for natural languages. To this end, there is an attempt at showing that such Transformational Grammars can satisfy some of the required conditions of the said models. The criterion of recursiveness is particularly discussed. To make the discussion possible a mathematical model for the Transformational Grammars is minutely presented, this model was elaborated by Barbara Partee and Seymour Ginsburg. ------------------------------------------ 1971 71_MSc_vieira Alfredo Carlos VIEIRA. Uma introducao a construcao automatica de "Reconhecedores" sintaticos para certas classes de linguagens. M.Sc.Diss. Port. Presentation: 08/71 58 [+ 43] p. Advisor: Roberto Lins de Carvalho Abstract: The objective of this work is the automatic construction of parsing algorithms for certain classes of grammars, known as context-sensitive, context-free and regular. These algorithms seem to be very efficient in relation of primitive steps executed as well as the number of storage locations used. Some more recent results like the parsing algorithm for c. f. g. developed by J. EARLEY were not present because the articles were not available when this work was finished. 71_MSc_coutinhofilho Flavio COUTINHO FILHO. Analise do desempenho de sistemas de computacao - metodologia. M.Sc.Diss. Port. Presentation: 10/71 123 p. Advisor: Luiz de Castro Martins Abstract: This work has the purpose of doing an exposition about the researches that are being made in the filed of computer systems performance evaluation. To allow a better understanding through the work a chapter about operating systems, multi-programming, multiprocessing and time-sharing systems were included, where are clarified some concept for the paper. Specified, this an analysis of general purposes of the evaluation methods and of the systems components that require an examination, is included an explanation about some simulation languages like SIMSCRIPT, ECSS, CSS and SCERT are used for systems evaluation, techniques employed in design, selection and analysis of benchmarks and the analysis of processes used in monitoring hardware and software elements of computers actually available. 71_MSc_crignis Darci de CRIGNIS. Simulacao e avaliacao de uma frota pesqueira. M.Sc. Diss. Port. Presentation: 12/71 87 [+50] p. Advisor: Luiz de Castro Martins Abstract: The purpose of this work is to simulate a fishing fleet with a program written in the GPSS III (General Purpose System Simulation) language. The program is compatible with the IBM 7044 system with 32 k works. It simulates the vehicle flow considering the main operational phases developed at the port, sea, pier and shipyards. The input data are provided by definition cards, which are standardized by the GPSS III. The output listings provide the elapsed time of each operational phase, percentage of equipment usage, costs, losses and quantity fished besides other information. Among the objectives we can mention the dimensioning of the pier, fleet, shipyards and scheduling of the pier. 71_MSc_passos Emmanuel Piseces Lopes PASSOS. Introducao a demonstracao automatica de teoremas. M.Sc.Diss. Port. Presentation: 07/71 110 p. Advisor: Antonio Luz Furtado Abstract: The aim of this paper is to provide an introduction to theorem proving in Formal Theories. It is based on a work by Newell, Shaw and Simon, "The Logic Theory Machine", where the authors present a program in IPL for proving The Theorems of Propositional Calculus of Principia Mathematica. This paper presents a program for proving the above theorems using a new programming module "PUCMAT" compiled in FORTRAN IV of IBM/7044. 71_MSc_lima Fernando Luiz Faria LIMA. Sistema de controle academico. M.Sc.Diss. Port. Presentation: 10/71 108 [+81] p. Advisor: Antonio Luz Furtado Abstract: The purpose of this work is to provide a part of the necessary toll to the "education council" and to the adviser professor aiming the improvement of the teaching in the university. We can divide our system in three parts: 1. Student's master file - in this part, we create a file containing information about the student; 2 . Correction - in this second part we present a report, containing the correction of multiple-choice or conventional test; 3. Evaluation and control - in this last part we present statistical values, which able us to determine a guidance for full-filling the objectives. 71_MSc_campos Ivan Moura CAMPOS. PRTC - Um sistema integrado de programas para analise de dados. M.Sc.Diss. Port. Presentation: 06/71 106 p. Advisor: Carlos Jose Pereira de Lucena Abstract: The aim of this work is to present an integrated set of programs for the IBM-1130 computer, which gives a basic support for the analysis of survey-collected data. The System furnishes contingency tables with up to six simultaneous variables, frequency distributions of either the original code values or data grouped in user defined classes, association measures, correlation co-efficient, and, in order to allow the construction of derived measures, permits a user-written routine. The set-up of the whole System is done by means of its own control cards, producing fully labeled print-out and user-oriented diagnostic messages. 71_MSc_faco Joao Dorneles FACO. Otimizacao do programa de manutencao preventiva de um sistema. M.Sc.Diss. Port. Presentation: 09/71 [irr.] p. Advisor: Antonio Cesar Olinto de Oliveira Abstract: This study presents the optimal solution to the preventive maintenance scheduling of a system trying to minimize the fluctuations around the mean value of the total quality of resources along a fixed planning horizon. We find a mathematical model for this practical problem in which we try to minimize the variance of a finite set of periodical square waves. This way we made it possible to apply Nonlinear programming techniques and could even construct an algorithm based on the Kuhn-Tucker theorem. 71_MSc_barbosa Jose Carlos BARBOSA. Graficos estatisticos. M.Sc.Diss. Port. Presentation: 12/71 90 p. Advisor: Antonio Luz Furtado Abstract: The purpose of the present work is to give the researcher an instrument for the visual presentation of statistical material. Drawing statistical graphs is a burdensome work, requiring personnel of some qualification. Automating such work allows the prompt obtention of the graphs and guarantees their accuracy. Our efforts have taken the form of a system of sub-programs, written in basic FORTRAN, for an IBM-1130 with the usual configuration of 8 k. The choice of language and equipment reflects the convenience of the university environment in Brazil, and also the needs of specially important research agencies such as the IBRE-FGV. 71_MSc_macedo Lucas Tofolo de MACEDO. Manipulacao de gramaticas livres do contexto e reconhecimento de LL (K). M.Sc.Diss. Port. Presentation: 09/71 99 [+88] p. Advisor: Roberto Lins de Carvalho Abstract: The purpose of this work is to bring together, on an organized fashion, the best known results in the areas of Formal Languages and Automata which are important toward an understanding of syntax directed compilers today and for future research in this field. This work is composed of four chapters in which the following topics are presented: chapter 1 - initial definitions - (Grammars, Languages, Derivation Trees, Finite Automata, Push-down Automata, etc.); chapter 2 - Regular Languages and Finite Automata; chapter 3 - Context-Free Languages and Push-down Automata; chapter 4 - LL(k) Languages, The Test for the LL(k) Condition and the Construction of a Recognizer for LL(k) Languages. 71_MSc_cunha Luiz Ferrara de Almeida CUNHA. Um metodo de representacao de estruturas de informacao: estrutura modular. M.Sc.Diss. Port. Presentation: 04/71 44 [+ 50] p. Advisor: Carlos Jose Pereira de Lucena Abstract: The aim of this work is to suggest a method for representing any arbitrary information structure, through a programming system which automatically provides for storage allocation of the abstract structure's component. This automation, which guarantees adequate storage allocation to information, allows for the mapping of concrete or abstract models into storage with minimum programming effort. The proposed system includes a set of elementary routines and a set of primitive functions. The elementary routines which perform bit manipulation and updating of available space areas, are defined implicitly by the system implementation. These routines are internal to the system, and are used only within the primitive functions. The primitive functions are elementary operations which can be combined into more powerful ones, which in turn may be written to describe a specific model. 71_MSc_sette Maria Alice SETTE. Aritmetica de precisao ilimitada sobre o corpo dos racionais. M.Sc.Diss. Port. Presentation: 12/71 135 p. Advisor: Joao Bosco Pitombeira de Carvalho Abstract: This work presents a set of subprograms which allow the arithmetic operations over the rational numbers which range can be taught as unlimited under certain considerations. The rational numbers can be represented as integers or as ordinary fractions; a list structure is used to represent them in the computer memory. The set of subprograms is written in FORTRAN IV language, based upon a small number of primitive, machine oriented subroutines. Those were written for the IBM 7044 where the system has been implemented. The system can be adapted, with small modifications, to any other machine with enough storage capacity to keep the set of subprogram plus work area to develop the lists. In the IBM 7044, the system occupies close to 8k. The text presents some examples to clarify the utilization of the system, storage requirements and evaluation of execution time for many operations. Further experience with the system will be necessary to better evaluate its efficiency and to suggest future improvement and system expansion. 71_MSc_millan Marilia Rosa MILLAN. Expressoes regulares - sintese e minimizacao dos automatos finitos. M.Sc.Diss. Port. Presentation: 04/71 75 [+63] p. Advisor: Roberto Lins de Carvalho Abstract: One of the best known results of Automata Theory is that the finite state automata are the recognizing device for the regular language. Such languages are sometimes represented by regular expressions. However, the process used to obtain the automaton, from the regular expression is not presented in the literature as a algorithm. The aim of this work is precisely to present the usual way of obtaining the minimum automaton in a thoroughly algorithmic form. 71_MSc_silva Nelson do Valle SILVA. Um sistema interpretador de comandos estatisticos. M.Sc.Diss. Port. Presentation: 03/71 130 p. Advisor: Carlos Jose Pereira de Lucena Abstract: The present work proposes an interpretative system of statistical commands as an approach to the problem of data analysis for the behavioral and social sciences. The main characteristics of this system are ease of utilization and its modularity. 71_MSc_martins Paulo Silveira MARTINS. Administracao academica centralizada - uma analise sobre aplicacao de computadores. M.Sc.Diss. Port. Presentation: 12/71 80 p. Advisor: Pe. Antonio Geraldo Amaral Rosas, SJ Abstract: The objective of the thesis is the analysis of centralized academic administration with the aid of computers. The study is divided in five parts: definition and implications of centralized administration; analysis of a computational system; programming of a computational system; simulation of the entire control procedure; final conclusions. 71_MSc_chaves Therezinha da Costa Ferreira CHAVES. Preditores: experiencia para obtencao de melhores formulas. M.Sc.Diss. Port. Presentation: 12/71 51 p. Advisor: Peter Albrecht Abstract: Not provided. 71_MSc_santos Vitoriano Ruas de Barros SANTOS. Tratamento geral dos metodos de extrapolacao para o limite. M.Sc.Diss. Port. Presentation: 07/71 74 p. Advisor: Peter Albrecht Abstract: The subject of this work is a general treatment of the approximations of the solution (formula) of a numerical problem, obtained by extrapolation to the limit of initial approximations T (h) given by an algorithm depending on a positive parameter h, such that (formula). The error of T(h) was assumed to be expressed by a real power series in h. A matricial treatment was used in order to enable the generalization for any sequence (formula) used in the calculation of the initial approximations (formula), and for any real power series in h representing its error. The correspondence to the particular cases usually found in the literature was verified. By using an extension of Lagrangian interpolation to a linear combination of real powers of the free variable function, formulae for the estimation of the maximal error of the extrapolation to the limit approximations were obtained. It was found that this estimate is approximately twice the actual error in the normal calculations cases. -------------------------------------------- 1972 72_MSc_pfeffer Adalberto Santos PFEFFER. P/PL/I Uma extensao de PL/I em pattern matching. M.Sc.Diss. Port. Presentation: 12/72 54 p. Advisor: Antonio Luz Furtado Abstract: This work expands the facilities of PL/I language to allow string processing facilities with similar capabilities of the high level language SNOBOL, version 4. Three new statement were added to PL/I with the follow functions: declare the variables needed for string processing; build the pattern; execution of the matching. Internally to the pattern statement the user has two additional facilities: he can call the functions defined by himself or perform assignments. The statements that allow to make a pattern matching are transformed at pre-processor stage in valid PL/I statements and then normally compiled by the PL/I compiler. 72_MSc_medeiros Adilson Tadeu de MEDEIROS. Uma extensao de PL/I para o processamento de listas. M.Sc.Diss. Port. Presentation: 15/08/72 64 p. Advisor: Antonio Luz Furtado Abstract: This work expands the facilities of PL/I language, to allow list processing facilities with similar capabilities of the high level language LISP 1.5 including an automatic garbage collection. Based on this language, new commands where added to PL/I with the following functions: declare list structures; assign to variable, any list structure; assign to a variable, the value of a conditional expression; input/output of list structures; assignment, retrieval and deletion of properties of atoms; iterative command (DO) for list structures; extraction of any element of a list. Besides, functions of LISP 1.5, such as, car, cdr, cons, eq, quote, list, value, atom and null and some others normally defined by the user as append, equal, subst etc, where added to PL/I. The list processing facilities presented in this work, being a high level language are easier to use than those implemented by PL/I itself. With respect to LISP 1.5 language, these facilities simply the input/output and the writing of the program. The statements that use these additional facilities are transformed at pre processor stage in valid PL/I statements and then normally compiled by the PL/I compiler. 72_MSc_sampaio Antonio Benedito Coimbra SAMPAIO. Geracao de um codigo otimo para expressoes aritmeticas com variaveis subscritas. M.Sc.Diss. Port. Presentation: 06/11/72 59 p. Advisor: Sergio Roberto Pinto Teixeira Abstract: This thesis studies the problem of generating minimal cost (time) code for arithmetic expression with subscript variables. It is not initially considered any algebraic law applied to the operators and operands, and an algorithm is introduced. Two algorithms are presented when we consider that certain operators are commutative or both commutative and associative. The three algorithms proposed generate optimal code under their suppositions for arithmetic expressions with subscript variables, and for a model of computer with N(N>1) general registers that may be both accumulators and index registers (like the IBM/360). Besides these algorithms are of complexity of time proportional to the number of arithmetic expressions elements. 72_MSc_aguilarquevedo Carlos Rafael AGUILAR QUEVEDO. Sistema cooperacional da UFMG: montador e macro-montador. M.Sc.Diss. Port. Presentation: 12/72 122 p. Advisor: Carlos Jose Pereira de Lucena Abstract: This work describes the MASC, a Macro Assembly System for a Cooperating System developed by the MINAS GERAIS FEDERAL UNIVERSITY. The MASC is a powerful version of the Extended Assembly for the 2100-A Hewlett-Packard computer, which accepts arithmetic statements, subscripted variables, and has macro facilities and with the difference that it is executed in a Data Processing Machine and their object program runs in the 2100-A HP computer, maintaining in this way the concept of a Cooperating System. 72_MSc_santos Clesio Saraiva dos SANTOS. Uma extensao da linguagem PL/I para processamento de grafos. M.Sc.Diss. Port. Presentation: 03/08/72 84 p. Advisor: Antonio Luz Furtado Abstract: This dissertation, a PL/I extension for graph processing is presented. This extension allows for the representation and manipulation of direct and indirect graphs and multigraphs. An arbitrary number of attribute-value pairs can be associated with the graph itself and with its nodes and edges. The representation of graphs is made by means of an heterogeneous linked structure; it easily enables the operations of creation, deletion and referencing on graphs and their elements. Provision is made for the use of special kinds sets, related to graphs, with correspondent and pertaining operations. Initialization, input/output of graphs and control statements were included along with some auxiliary procedures. This extension provides the user with a natural and concise notation, suited to the description of graph algorithms. 72_MSc_nunes Daltro Jose NUNES. Gerador de macro dirigido por sintaxe. M.Sc.Diss. Port. Presentation: 21/08/72 47 p. Advisor: Sergio Roberto Pinto Teixeira Abstract: This paper describes a language to aiming at the definition and expansion of syntactic macros. The basic structure of the language was defined by B. M. Leavenworth and was published in "Communication of the ACM", November, 1962. The initial section of the dissertation is a comparative study of several macro generators. For future implementation, the language was formally presented and data structures were defined to store the macros, their expansions and metavariables. 72_MSc_luna Henrique Pacca Loureiro LUNA. Jogo de acoes. M.Sc.Diss. Port. Presentation: 17/11/72 74 p. Advisor: Klaus Galda Abstract: Initially there is a discussion of the problems that are involved in modeling portfolio selection. Then we present an algorithm and program for finding optimal solutions in Pye's model. This model is used for short-term planning because of its sensitivity to current prices. After that we examine some models that attempt to optimize portfolios for longer periods of time. One of them attempts to use all the available information, and the other is the well-known Markowitz model. An analysis of the practical application of these models concludes the paper. 72_MSc_belloc Joao Afonso Ayrosa BELLOC. Simulacao estocastica de modelos macro- econometricos. M.Sc.Diss. Port. Presentation: 18/07/72 58 p. Advisor: Jorge Viana Monteiro Abstract: No English abstract provided. 72_MSc_bauer Joao Carlos Pires BAUER. Ampliacao da estrutura de controle e extensao modular de PL/I. M.Sc.Diss. Port. Presentation: 15/12/72 p. Advisor: Antonio Luz Furtado Note: Not available. 72_MSc_tanaka Kotaro TANAKA. Simulacao de um sistema time-sharing. M.Sc.Diss. Port. Presentation: 03/72 80 p. Advisor: Lucio Valerio Morsch Goelzer Abstract: No English abstract provided. 72_MSc_terry Leslie Afranio TERRY. Alguns algoritmos sobre a solucao de problemas nao-lineares esparsos. M.Sc.Diss. Port. Presentation: 12/12/72 72 p. Advisor: Peter Albrecht Abstract: Not provided. 72_MSc_centeno Luis Fernando Ramos CENTENO. Um sistema de recuperaco de informacoes para computadores de pequeno porte. M.Sc.Diss. Port. Presentation: 03/72 55 + [65] p. Advisor: Carlos Jose Pereira de Lucena Abstract: This work was developed with the purpose of offering to users of mini computers a data retrieval system. The system was written in FORTRAN IV language and allows for easy and fast implementation. No significant previous experience in computers is necessary to run the system. The system was implemented for the IBM's 1130 computer. 72_MSc_aguiar Marcia Barros de AGUIAR. Gerador de numeros aleatorios para o sistema IBM/1130. M.Sc.Diss. Port. Presentation: 06/72 54 p. Advisor: Lucio Valerio Morsch Goelzer Abstract: This paper analyzes the development of random number generators having a period above 8192, corresponding to the RANDU generator which is part of the IBM scientific - subroutine package. The generators were codified in IBM-1130 ASSEMBLER. Their execution times were evaluated and their behavior was statistically analyzed in a comparative manner. 72_MSc_azeredo Paulo Alberto AZEREDO. Tecnicas de otimizacao de codigo objeto e suas aplicacoes em um compilador para linguagem basic, usando um compilador de compiladores. M.Sc.Diss. Port. Presentation: 03/72 106 p. Advisor: Antonio Luz Furtado Abstract: The purpose of this work is to develop a compiler for the BASIC (Beginner's All-purpose Symbolic Instruction Code) language, under the IBM-7044 system. At the same time, some techniques of object code optimization are presented. The compiler, generated by the COMCOM (COMpiler-COMpiler) system, uses some of these techniques, in order to produce an efficient code. 72_MSc_faria Paulo Oscar de FARIA. Programacao quadratica, estudo comparativo dos algoritmos: uma aplicacao e sua implementacao. M.Sc.Diss. Port. Presentation: 06/72 2 vols.. Advisor: Larry Kerschberg Abstract: The objective of this thesis is the preparation of a computer program to solve optimization problems using concave quadratic functions, with linear constraints. The program was written in FORTRAN and can be used in any computer that accepts this compiler. The report has a resume of the historical evolution of the methods used in the solution of that problem. The input data are read from punched cards. The program may be stored in disk file or it may be read from punched cards. The printout report is divided in three sections: one for data, one for error messages, and the third one for the results. The quadratic programming can be applied in the direct solution of physical models or as a mathematical tool in the solution of more general problems. 72_MSc_bianchi Paulo Tolosa BIANCHI. Uma rotina de reconhecimento de unidades sintaticas. M.Sc.Diss. Port. Presentation: 01/08/72 144 p. Advisor: Mario Aloysio Telles Ribeiro Abstract: SCAN - examination of a succession of characters from left to right, character by character - is necessary in one or more steps by compilers. Each compiler has its own particular manner to scan. Some compilers, after recognizing a command, re-scans part of it, to verify the syntax, while others use special procedures to avoid re-scanning. In either case, the efficiency of a compiler will depend in large part on the efficiency of its scanning routine. A routine which scans and recognizes syntax units is proposed in this paper. Its principal characteristics are written in Assembler, very fast (recognizes approximately an average of 2000 syntax units per second in a /360 model 65) and, occupies only about half of a control section. 72_MSc_catunda Raimundo Haroldo do Carmo CATUNDA. Contribuicao ao estudo computacional sobre a associatividade parcial da simetrizacao de um semi-grupo. M.Sc.Diss. Port. Presentation: 29/09/72 99 p. Advisor: Joao Bosco Pitombeira de Carvalho Abstract: The purpose of this work is to bring a problem of abstract algebra into the area of information structures. Using FORTRAN IV for a IBM-7044 computer, were developed programs that generate monomios and study associative laws. When studying each case, we used binary trees structures and several recursive subroutines which handle such trees. 72_MSc_chaves Raimundo Nonato de Miranda CHAVES. Processo adaptativo no calculo da solucao de uma classe de jogos com informacao incompleta. M.Sc.Diss. Port. Presentation: 22/11/72 58 p. Advisor: Klaus Galda Abstract: This paper deals with the problem of two-person, zero-sum games in the case that one of the player is using a strategy different from the usual von Neumann minimax strategy. The method is to use a learning algorithm which are based on one player's estimate of the other's strategy after various repetitions of the game. The algorithms attempt to let the first player take full advantage of the other's weaknesses. Suppose at the k-th repetition of the game the first and second player have apparent strategies of X[k] and Y[k] respectively. Then the strategy of the first player for the next repetition is determined by the different equation. X[k+1]=X[k]-.(formula)..[k+1]{X[k]-f (Y[k])}.F (Y[k] ) represents the optimal pure response of the first player to the strategy Y[k] (formula) [k+1] is a parameter to be chosen to assign weights to different strategies. Various models of this situation are studied by varying the different parameters of the equation. Empirical tests of the results are made using a 3 x 3 payoff matrix which has no saddle point and a unique mixed minimax solution. 72_MSc_rabuske Renato Antonio RABUSKE. Sistema LISP-FORTRAN para o computador IBM/1130. M.Sc.Diss. Port. Presentation: 06/72 107 p. Advisor: Simao Sirineo Toscani Abstract: The main purpose of this paper is to make the basic LISP-FORTRAN System routines available to the users of the IBM 1130 computer. As secondary purposes it is proposed: a) to show the basic structure, the recursivity and the use of the subroutines that compose the system. b) to provide software subsidies referring to reading and printing, as well as to show the readers that are somehow advanced in computation some more - sophisticated techniques that simplify the programming of complex or tiresome problems. 72_MSc_roschke Sergio Ivan ROSCHKE. Um algoritmo para determinar o numero cromatico e um colorido otimo de um grafo finito nao dirigido. M.Sc.Diss. Port. Presentation: 17/08/72 47 p. Advisor: Antonio Luz Furtado Abstract: The problem of finding the chromatic number of a graph and exhibiting one or all optimal colorings has a several practical applications. It is equivalent to partitioning a set of objects, some of which are pairwise "incompatible", into the minimum number of cells, so that no two incompatible objects are assigned to the same cell. Situations where this applies are production scheduling, construction of examination timetables, storage of goods, etc. Heuristic procedures for the described problem have been developed by Berge [1], Welsh and Powell [2], and Wood [3]. More recently Christofides [4] has presented a deterministic algorithm that is based on the concept of maximal internally stable sets. This thesis also employs this concept to develop an algorithm that determines the chromatic number and one optimal coloring. A partitioning technique is used allowing the processing of large graphs. ------------------------------------------- 1973 73_MSc_lucena Alfredo Jose Pereira de LUCENA. Sistema para analise automatica de programas FORTRAN. M.Sc.Diss. Port. Presentation: 21/09/73 55 p. Advisor: Sergio Roberto Pinto Teixeira Abstract: This work was developed with the purpose of creating a System that could be used as a tool in the determination of the critical points of the execution time of FORTRAN programs. 73_MSc_carvalho Alfredo Veiga de CARVALHO. Um sistema conversacional de consulta para artigos de periodicos. M.Sc.Diss. Port. Presentation: 21/12/73 94 p. Advisor: Flavio Pereira de Souza Abstract: SCAP (Periodical Article on-line Retrieval System) is a system designed for retrieval via remote terminal of bibliographical references to articles in periodicals. On-line operations is handled by TSO (Time Sharing Option), which performs the interface with the Operating System. The retrieval of information is controlled through on-line dialogue between the user and the system using a SCAP conversational language which is easy to learn without prior knowledge of computational techniques. The creation and maintenance of the Data Base is carried out in batch mode, independent of the on-line retrieval operation; the system is designed to maintain large collections of periodicals. 73_MSc_albuquerquefilho Alonso Duarte de ALBUQUERQUE FILHO. Um Sistema de Traducao Semi-Automatica de Linguagens Naturais . M.Sc.Diss. Port. Presentation: 20/02/73 58 p. Advisor: Luiz Edmundo Soares Abstract: The purpose of the CATS system developed in this work is to aid humans in translating texts. A teleprocessing terminal establishes a conversational mode with the user, exhibiting synonymous options of some words, requesting translations of unknown words, and allowing the arrangement of the sentences. It consists of a set of routines which comprise several modules. This permit CATS to perform a translation in real time with an iteration between the user and the system. 73_MSc_nascimento Alvaro Alberto NASCIMENTO. Uma implementacao de um provador automatico de teoremas baseado na teoria de resolucao. M.Sc.Diss. Port. Presentation: 20/06/73 101 [+50] p. Advisor: Sueli Mendes dos Santo Abstract: The present work presents an interactive automatic theorem prover and some experimental results obtained with it. The theoretical bases used in the construction of this prover are briefly presented on the initial chapters. They are the Resolution Theory and a basic set of strategies. 73_MSc_thomaz Antonio Clecio Fontenelles THOMAZ. Aplicacao dos computadores a pesquisa da homologia da algebra de Steenrod. M.Sc.Diss. Port. Presentation: 20/03/73 82 p. Advisor: Joao Bosco Pitombeira de Carvalho Abstract: Not provided. 73_MSc_santos Antonio Pedro Lima SANTOS. Um nucleo para implementacao de sistemas operacionais. M.Sc.Diss. Port. Presentation: 01/03/73 168 p. Advisor: Simao Sirineo Toscani Abstract: Initially we give description of overall systems, of which the subject of this thesis is a part. The overall system is made up of the on-line linking of a minicomputer with a large general purpose computer. The advantage and objectives of such a combined system are discussed. Then some problems of multiprogramming and their solutions are considered idea of "process" is defined and some functions for communicating between processes and for manipulation of processes are given. A hierarchical structure between processes is also defined. Some details of the implementation of the supervisor nucleus are then given, and the merits of our system and others such as BCS, RTE of Hewllet Packard are compared. Finally we consider some possibilities of diversifying and intensifying the applications of the minicomputer utilizing the supervisor-nucleus as described in this thesis. 73_MSc_pradojunior Arnaldo Correa PRADO JUNIOR. Simulacao de um sistema de perguntas e respostas. M.Sc.Diss. Port. Presentation: 21/02/73 2 vols. Advisor: Sueli Mendes dos Santos Abstract: The aim of this paper is to construct a simulator of a question-answering system by means of an interpretation of the user's question ( a specific subset of natural language) made by syntactic and semantic analysis and not only by comparison of formats or by key-words. It is used a transformational grammar with context-free base which will generate the basic questions type which will be analyzed both semantically and syntactically. The system developed in this paper allows questions within a particular subject-matter formulated in a restricted language. It was constructed a set of data-base which seems appropriated for this subject, using three index-tables in such a way that when a question is interpreted the system knows whose table search first by means of the hash-code technique. The implementation program of the system was written in PL/1. The rewriting rule of the base of the grammar and the terminals which do not belong to the base are read and stored in the memory. It was ascribed values to each terminal of the base. These values that will be necessary for the semantic analysis of theuser's question are also read and stored in the memory. The data that belong to the data-base set are read and conveniently assembled. After this, questions can be made. Of course it is possible to allow data and questions alternatively, with few modifications in the program. The program must be considered as a test-program which shows the feasibility of what is presented in this paper. However it needs improvements to make it more efficient. A possible improvement could be to add a procedure that permits to correct mistakes in the data base. The system is about the history of the "COMICS", with relation which, we define in chapter 1 the following sets: set of characters; set of artists; set of writers. We will have also one set of years and two sets of periods. 73_MSc_carvalho Carlos Alberto Picanco de CARVALHO. Automaton e particionamento de matrizes de transicao. M.Sc.Diss. Port. Presentation: 16/08/73 37 p. Advisor: Sergio Roberto Pinto Teixeira Abstract: Among the recognizer algorithms of context free languages, it has been distinguished the transition matrices by its speed. The main disadvantage consists in the space occupied by the matrices. In [4] it was observed that, partitioning the transition matrices, the occupied space would be reduced, in change of the lost in detail of error routines. The present work shows a formal model of transition matrices and algorithms to find the transfer points among the matrices obtained by the partitioning method. 73_MSc_ferreira Dulcineia de L. V. FERREIRA. Um metodo ciclico de reducao para solucao da equacao de Poisson. M.Sc.Diss. Port. Presentation: 20/06/73 45 p. Advisor: Martin Allen Diamond Abstract: A direct method is developed for solving systems of linear equations which arise in the solution of Poisson's equation over a rectangle with Dirichlet or Neumann boundary condition. This method is similar to CORF algorithm but requires less computation. Its principle application is when we have Poisson's equation with Dirichlet boundary condition on a nonrectangular region. The greatest reduction in computation occurs in this case. 73_MSc_ferreira Fabio Ceschin FERREIRA. Construcao automatica de dicionarios hierarquicos. M.Sc.Diss. Port. Presentation: 31/01/73 56 p. Advisor: Flavio Pereira de Souza Abstract: Several processes for building hierarchical arrangement of terms describing document contents are presented and discussed. Techniques for automatic implementation of one of those are also fully described. 73_MSc_gazzaneo Giosafatte GAZZANEO. Sistema de processamento de informacoes - um modelo para a administracao escolar. M.Sc.Diss. Port. Presentation: 21/09/73 105 p. Advisor: Donaldo de Souza Dias Abstract: This work presents a development in techniques of determining a model for a Information Processing System for Brazilian high School institutions. It has been divided into three stages: study and characterization of the System acting environment model definition and implementation planning. The annex gives a summary of the analytical methodology for project development. In the model characterization was used the new "Lei de Diretrizes e Bases" which rule the undergraduate teaching in the whole country. 73_MSc_ferreira Joaquim Elias de FREITAS. Minimizacao de tabelas binarias de decisao. M.Sc.Diss. Port. Presentation: 20/09/73 26 p. Advisor: Larry Kerschberg Abstract: No English abstract provided. 73_MSc_castilho Jose Mauro Volkmer de CASTILHO. Um esquema de implementacao para formulas do ALGOL 68. M.Sc.Diss. Port. Presentation: 12/09/73 65 p. Advisor: Sergio Roberto Pinto Teixeira Abstract: This work reports the result of a study of the Algol 68 programming language entertained with the purpose of utilizing its revolutionary features in other programming languages. Algol 68 like formulas, containing user defined operators and operations, is advanced. The related information structures are sketched and an algorithm for syntactic analysis of the formulas is given. 73_MSc_yamaguchi Kazue YAMAGUCHI. Algumas rotinas para o tratamento de arvores binarias no sistema IBM 1130. M.Sc.Diss. Port. Presentation: 31/01/73 160 p. Advisor: Luiz Ferrara de Almeida Cunha Abstract: A set of subprograms (subroutines and functions) written in FORTRAN for the IBM 1130 with 8k words of core storage, for representing and manipulating binary trees is presented in this work. Throughout the text an effort is made towards establishing standard symbols for representing binary tree elements and properties, so as to clarify the presentation of the algorithms implemented. 73_MSc_toscani Laira Vieira TOSCANI. Prova da correcao formal de um compilador simples. M.Sc.Diss. Port. Presentation: 02/07/73 57 p. Advisor: Sueli Mendes dos Santos Abstract: The purpose of the thesis is to prove the formal correctness of a simple compiler. The work is divided into the following sections: 1) description of a model of a machine capable of simulating the actions of a simple computer; 2) informal description of a simple programming language; 3) informal definition of a compiler for this language; 4) formal definition of the computer, of the programming language, and of the compiler; 5) proof of the formal correctness of the compiler. 73_MSc_correafilho Milton CORREA FILHO. Uma aplicacao da teoria de informacao na selecao de palavras chaves. M.Sc.Diss. Port. Presentation: 02/73 p. Advisor: Luiz Carlos Gomes Note: Not available. 73_MSc_queiroz Mucio Gomes da Silva QUEIROZ. Um estudo comparativo de processos estatisticos para obtencao automatica de resumos. M.Sc.Diss. Presentation: 16/01/73 102 p. Advisor: Luiz Edmundo Soares Abstract: The purpose of this work was to compare the abstract of a given text in English with the corresponding abstract for the same text in Portuguese, both abstracts were obtained by application of statistical experiments in automatic extracting. Two experiments in automatic abstracting were chosen, the Luhn's Experiment [2] and the experiment suggested by Edmundson and Wylls [5], both based on statistical methods. An algorithm was implemented for each experiment used here. Using the IBM/370 System, two programs were written in the PL/I Language, each representing one of the implemented algorithms. Sixteen chapters from different books were used as texts for all the experiments. 73_MSc_rosa Newton Braga ROSA. Software para programacao de micro computador destinado a orientacao por satelites artificiais. M.Sc.Diss. Port. Presentation: 21/12/73 170 p. Advisor: Mario Aloysio Telles Ribeiro Abstract: The research Institute of the Brazilian Navy (Instituto de Pesquisas da Marinha - IPqM) is developing a navigation receiver, using as a starting point, information transmitted by the artificial satellites of the transit system. An important part of this project is the construction of a fixed-program microcomputer, with large scale integration chips (MOS-LSI), to figure out the coordinates of the navigator's position, starting from data transmitted from the satellite (orbital parameters), and local information supplied by the operator. The dissertation deals with the utilization of microcomputers in data processing, their peculiarities and their main applications, as well as some important cautions to be taken in their programming and in software requirements for their proper and efficient employ. There is also a description of some of the solutions derived to establish the computer model and its appropriated configuration, following project specifications, stressing the experience acquired in developing microcomputers suited to specific needs. The computer chosen for this project, the Intel MCS-4, together with the Cross-Software to its programming, are topics treated in depth. Also, a description is offered of the general lines followed in this project by the research Institute of the Brazilian Navy (IPqM). The description of the satellite navigation method and of the transit system components summarizes a substantial amount of references on these topics. 73_MSc_leenhardt Renaud Pierre LEENHARDT. Acessibilidade, controlabilidade e observabilidade de sistemas bilineares. M.Sc.Diss. Port. Presentation: 02/03/73 61 p. Advisor: Larry Kerschberg Abstract: Within the frame of the Theory of Algebraic Systems P.A.S. Veloso obtained a decomposition for the casual Bilinear System separating the non-linearity characterized by the tensor product from the linear components. Making use of this result the present work proposes a definition for the state of the casual Bilinear System. Besides with the basis on the study by Larry Kerschberg of the concepts of accessibility, controllability and observability for linear systems, it presents a study of those concepts for the time invariant uniformly transitional causal bilinear system, in the case of continuous time and more precisely in the case of discrete time. 73_MSc_kellerfilho Thadeu KELLER FILHO. Uma extensao de um metodo de von Neumann para a geracao de variaveis aleatorias. M.Sc.Diss. Port. Presentation: 10/09/73 62 p. Advisor: Ricardo Milton Frischtak Abstract: The main purpose of the thesis is present an extension of a method conceived by Von Neumann for the exact generation of random variables with a digital computer. Von Neumann's method - named "rejection method" - has served as a basis for several important applications of discret simulation. Nevertheless, the method's field of applications is very limited, since it allows only the generation of continuous random variables with finite and bounded probability density function. The exposition of the thesis, the classical inverse transformation is first examined. It is composed of the main technique for the exact generation of random variables. Then, Von Neumann's method is studied, so as to point out critical aspect of its limitations. The purpose of the thesis is then achieved, where a more general rejection technique is conceived so as to enlarge considerably the field of its applications. The efficiency of the method is then studied and examined the possibility of adapting Butler's method of mixtures, to gradually produce a greater efficiency. Finally, some numerical examples are presented, to allow a practical evaluation of the accuracy and efficiency of the proposed method.