Este trabalho introduz uma definição para noção de inteligência de máquina, estabelece a possibilidade concreta dessa definição e fornece indicações sobre a sua necessidade - isto e, dá-lhe um conteúdo objetivo e mostra o interesse e a utilidade que a definição pode ter para a ciência da computação, em geral, e para a inteligência artificial, em particular. Especificamente, toma-se uma particular leitura da definição de inteligência dada por J. Piaget e se estabelecem as condições para que essa definição possa ser interpretada no domínio das máquinas. Para tanto, uma revisão das noções fundamentais da ciência da computação se faz necessária, a fim de explicitar os aspectos dinâmicos de variabilidade, controlabilidade e adaptabilidade subjacentes a tais conceitos (maquina, programa, computação, e organização, rege adaptação de rnáquina). Por outro lado, urna, mudança de atitude face aos objetivos da inteligência, artificial também e requerida. A definição dada supõe que se reconheça, a autonomia operacional das maquinas, e isso leva, a abandonar, ou pelo menos a colocar em segundo piano, o ponto de vista que chamamos de artificialismo - a busca da imitação do comportamento inteligente de seres humanos ou animais - e a adotar o ponto de vista que denominamos de naturalismo - a consideração da inteligência de maquina como fenômeno natural nas maquinas, digno de ser estudado em si próprio. 0 trabalho apresenta os resultados da reflexão através da qual se tentou realizar tais objetivos. / This work introduces a definition for the notion of machine intelligence, establishes the concrete possibility of that definition and gives indications on its necessity - that is, it gives that notion an objective content and shows the interest and utility that the definition may have to computer science, in general, and artificial intelligence, in particular. Specifically, we take a particular reading of the definition of intelligence given by J. Piaget, and we establish the conditions under which that definition can be interpreted in the domain of machines. To achieve this, a revision of the fundamental notions of computer science was necessary, in order to make explicit the dynamical aspects of variability, controlability and adaptability that are underlying those concepts (machine, program, computation, and machine organization, regulation and adaptation). On the other hand, a change in the attitude toward the objetives of artificial intelligence was also required. The given definition pressuposes that one recognizes the operational autonomy of machines, and this implies abandonning the point of view we call artificialism - the search for the imitation of the intelligent behavior of human beings and animals - and adopting the point of view that we call naturalism - which considers that machine intelligence is a natural phenomenon in machines, that should be studied by its own. The work presents the results of the reflexion through which we tried to realize those goals.

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

Os números naturais parciais são informações parciais sobre números naturais e w. As propriedades matemáticas do domínio de números naturais parciais e de funções que envolvem este domínio são estudadas via o use da teoria dos domínios de Scott. A manipulação formal de naturais parciais é estudada mediante a utilização de um calculo-ג tipado com constantes. Relações com a teoria da recursão são estudadas. É mostrado como funções continuas entre naturais parciais podem representar processos interativos, possivelmente perpétuos. / Partial natural numbers are informations about natural numbers and w. Mathematical properties of the domain of partial natural numbers and functions involving this domain are investigated with the aid of Scott domain theory. A typed ג-calculus is introduced for investigating formal manipulation of partial natural numbers. Relations with recursion theory are investigated. It is shown how continuous functions on natural numbers can represent (possibly perpetual) interactive processes.

Submitted by Francisco Neto (frc.neto@gmail.com) on 2018-11-12T18:35:20Z No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FranciscoNeto_VersãoFinal.pdf: 3580723 bytes, checksum: ab050a3f59a7cd9dc40bf2abd259448c (MD5) 33 ATA de Defesa - Francisco Neto (Digitalizada).pdf: 674001 bytes, checksum: 9e15e8338add9d9e1950b27fa1f138da (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-11-12T19:14:20Z (GMT) No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FranciscoNeto_VersãoFinal.pdf: 3580723 bytes, checksum: ab050a3f59a7cd9dc40bf2abd259448c (MD5) 33 ATA de Defesa - Francisco Neto (Digitalizada).pdf: 674001 bytes, checksum: 9e15e8338add9d9e1950b27fa1f138da (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-11-12T20:39:29Z (GMT) No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FranciscoNeto_VersãoFinal.pdf: 3580723 bytes, checksum: ab050a3f59a7cd9dc40bf2abd259448c (MD5) 33 ATA de Defesa - Francisco Neto (Digitalizada).pdf: 674001 bytes, checksum: 9e15e8338add9d9e1950b27fa1f138da (MD5) / Made available in DSpace on 2018-11-12T20:39:29Z (GMT). No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FranciscoNeto_VersãoFinal.pdf: 3580723 bytes, checksum: ab050a3f59a7cd9dc40bf2abd259448c (MD5) 33 ATA de Defesa - Francisco Neto (Digitalizada).pdf: 674001 bytes, checksum: 9e15e8338add9d9e1950b27fa1f138da (MD5) Previous issue date: 2017-11-24 / Internet flexible environments need a more formal process to provide intelligent services to their users. This process should define protocols, specification languages and schemes for generation and integration of such intelligent services. In the project reported here, we show the design and development of a framework that solves this problem in a generic way. The validation of this framework proposal involved an implementation of an instance of the formal elements described in this work. We have studied and classified how intelligent services are currently implemented in CSCW environments in the web and we proposed a differentiated interpretation for the types of tasks intelligent based on the point of view of its functionalities. This classification was later used in the creation of a reference model for a layer of intelligent services. From the reference model a reference architecture was assembled in which we describe its elements as well as a description of their behaviors and relationships. Finally, an implementation was produced for the proposed architecture. / Ambientes flexíveis na internet precisam de um meio de prover serviços inteligentes a seus usuários, o que envolve a definição de protocolos, linguagens de especificação, esquemas para a geração e integração de tais serviços. No projeto aqui descrito, mostramos a concepção e desenvolvimento de um framework que resolve esse problema de forma genérica. A validação da proposta envolveu a implementação das instâncias dos elementos formalizados. Identificamos como serviços inteligentes são implementados atualmente em ambientes colaborativos na web e propusemos uma classificação diferenciada para os tipos de tarefas inteligentes sob o ponto de vista de suas funcionalidades, o que foi posteriormente utilizado na criação de um modelo de referência para uma camada de serviços inteligentes. A partir do modelo de referência foi construído uma arquitetura na qual descrevemos os principais componentes necessários bem como fazemos uma descrição de seus comporta- mentos e relacionamentos. Por fim, foi desenvolvido uma implementação para a arquitetura proposta.

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

Os números naturais parciais são informações parciais sobre números naturais e w. As propriedades matemáticas do domínio de números naturais parciais e de funções que envolvem este domínio são estudadas via o use da teoria dos domínios de Scott. A manipulação formal de naturais parciais é estudada mediante a utilização de um calculo-ג tipado com constantes. Relações com a teoria da recursão são estudadas. É mostrado como funções continuas entre naturais parciais podem representar processos interativos, possivelmente perpétuos. / Partial natural numbers are informations about natural numbers and w. Mathematical properties of the domain of partial natural numbers and functions involving this domain are investigated with the aid of Scott domain theory. A typed ג-calculus is introduced for investigating formal manipulation of partial natural numbers. Relations with recursion theory are investigated. It is shown how continuous functions on natural numbers can represent (possibly perpetual) interactive processes.

Os números naturais parciais são informações parciais sobre números naturais e w. As propriedades matemáticas do domínio de números naturais parciais e de funções que envolvem este domínio são estudadas via o use da teoria dos domínios de Scott. A manipulação formal de naturais parciais é estudada mediante a utilização de um calculo-ג tipado com constantes. Relações com a teoria da recursão são estudadas. É mostrado como funções continuas entre naturais parciais podem representar processos interativos, possivelmente perpétuos. / Partial natural numbers are informations about natural numbers and w. Mathematical properties of the domain of partial natural numbers and functions involving this domain are investigated with the aid of Scott domain theory. A typed ג-calculus is introduced for investigating formal manipulation of partial natural numbers. Relations with recursion theory are investigated. It is shown how continuous functions on natural numbers can represent (possibly perpetual) interactive processes.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.