View in EDS

Topics in Computational Learning Theory and Graph Algorithms.

Saved in:
Bibliographic Details
Title: Topics in Computational Learning Theory and Graph Algorithms.
Language: English
Authors: Board, Raymond Acton, Illinois Univ., Urbana. Dept. of Computer Science.
Peer Reviewed: N
Page Count: 147
Publication Date: 1990
Sponsoring Agency: National Science Foundation, Washington, DC.
Document Type: Dissertations/Theses - Doctoral Dissertations
Descriptors: Algorithms, Computer Science, Computer Science Education, Higher Education, Learning Theories, Mathematical Models, Mathematics Education, Problem Solving
Abstract: This thesis addresses problems from two areas of theoretical computer science. The first area is that of computational learning theory, which is the study of the phenomenon of concept learning using formal mathematical models. The goal of computational learning theory is to investigate learning in a rigorous manner through the use of techniques from theoretical computer science. Much of the work in this field is in the context of "probably approximately correct" (PAC) model of learning, which is carried out in a probabilistic environment. Of particular interest are the questions of determining for which classes of concepts the PAC-learning problem is tractable and discovering efficient learning algorithms for such classes. The second area from which topics are drawn is that of online algorithms for graph-theoretic problems. Many problems in such fields as communications, transportation, scheduling, and networking can be reduced to that of finding a good graph algorithm. After an introduction in Chapter 1, some background information is provided in Chapter 2 on the field of computational learning theory. In Chapter 3 it is shown that for any concept class having a particular closure property, the existence of a graph algorithm implies that the class is PAC-learnable. Chapter 4 defines a variation on the standard PAC model of learning called semi-supervised learning, a model which permits the rigorous study of learning situations where the teacher plays only a limited role. Chapter 5 deals with the problem of prediction as performed by deterministic finite automata, counter machines, and deterministic pushdown automata. Chapter 6 investigates the power and the performance of online algorithms for a certain class of graph problems, referred to as vertex labeling problems. (77 references) (JJK)
Entry Date: 1992
Accession Number: ED342665
Database: ERIC
FullText Text:
  Availability: 0
CustomLinks:
  – Url: https://eric.ed.gov/contentdelivery/servlet/ERICServlet?accno=ED342665
    Name: ERIC Full Text
    Category: fullText
    Text: Full Text from ERIC
Header DbId: eric
DbLabel: ERIC
An: ED342665
AccessLevel: 3
PubType: Dissertation/ Thesis
PubTypeId: dissertation
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Topics in Computational Learning Theory and Graph Algorithms.
– Name: Language
  Label: Language
  Group: Lang
  Data: English
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Board%2C+Raymond+Acton%22">Board, Raymond Acton</searchLink><br /><searchLink fieldCode="AR" term="%22Illinois+Univ%2E%2C+Urbana%2E+Dept%2E+of+Computer+Science%2E%22">Illinois Univ., Urbana. Dept. of Computer Science.</searchLink>
– Name: PeerReviewed
  Label: Peer Reviewed
  Group: SrcInfo
  Data: N
– Name: Pages
  Label: Page Count
  Group: Src
  Data: 147
– Name: DatePubCY
  Label: Publication Date
  Group: Date
  Data: 1990
– Name: SourceSuprt
  Label: Sponsoring Agency
  Group: SrcSuprt
  Data: National Science Foundation, Washington, DC.
– Name: TypeDocument
  Label: Document Type
  Group: TypDoc
  Data: Dissertations/Theses - Doctoral Dissertations
– Name: Subject
  Label: Descriptors
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science%22">Computer Science</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+Education%22">Computer Science Education</searchLink><br /><searchLink fieldCode="DE" term="%22Higher+Education%22">Higher Education</searchLink><br /><searchLink fieldCode="DE" term="%22Learning+Theories%22">Learning Theories</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Models%22">Mathematical Models</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+Education%22">Mathematics Education</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+Solving%22">Problem Solving</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: This thesis addresses problems from two areas of theoretical computer science. The first area is that of computational learning theory, which is the study of the phenomenon of concept learning using formal mathematical models. The goal of computational learning theory is to investigate learning in a rigorous manner through the use of techniques from theoretical computer science. Much of the work in this field is in the context of "probably approximately correct" (PAC) model of learning, which is carried out in a probabilistic environment. Of particular interest are the questions of determining for which classes of concepts the PAC-learning problem is tractable and discovering efficient learning algorithms for such classes. The second area from which topics are drawn is that of online algorithms for graph-theoretic problems. Many problems in such fields as communications, transportation, scheduling, and networking can be reduced to that of finding a good graph algorithm. After an introduction in Chapter 1, some background information is provided in Chapter 2 on the field of computational learning theory. In Chapter 3 it is shown that for any concept class having a particular closure property, the existence of a graph algorithm implies that the class is PAC-learnable. Chapter 4 defines a variation on the standard PAC model of learning called semi-supervised learning, a model which permits the rigorous study of learning situations where the teacher plays only a limited role. Chapter 5 deals with the problem of prediction as performed by deterministic finite automata, counter machines, and deterministic pushdown automata. Chapter 6 investigates the power and the performance of online algorithms for a certain class of graph problems, referred to as vertex labeling problems. (77 references) (JJK)
– Name: DateEntry
  Label: Entry Date
  Group: Date
  Data: 1992
– Name: AN
  Label: Accession Number
  Group: ID
  Data: ED342665
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=eric&AN=ED342665
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 147
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Computer Science
        Type: general
      – SubjectFull: Computer Science Education
        Type: general
      – SubjectFull: Higher Education
        Type: general
      – SubjectFull: Learning Theories
        Type: general
      – SubjectFull: Mathematical Models
        Type: general
      – SubjectFull: Mathematics Education
        Type: general
      – SubjectFull: Problem Solving
        Type: general
    Titles:
      – TitleFull: Topics in Computational Learning Theory and Graph Algorithms.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Illinois Univ., Urbana. Dept. of Computer Science.
      – PersonEntity:
          Name:
            NameFull: Board, Raymond Acton
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Type: published
              Y: 1990
ResultId 1