Link to IST HomeLink to PSU Home

Current Offerings
Core Courses
Associate Courses
Baccalaureate Courses
Graduate Courses
Certificate Courses
Online Courses

Courses:  IST 230: Language, Logic, and Discrete Mathematics

Quick Jump to:

University Bulletin
Course Outline

A. UNIVERSITY BULLETIN:

1.  Abbreviation: IST
2.  Number: 230
3.  Title: Language, Logic, and Discrete Mathematics
4.  Abbreviated Title: Lang Log Disc Math
5.  Credits: 3
6.  Description: Introduction to formal languages, mathematical logic, and discrete mathematics, with applications to information sciences and technology.
7.  Prerequisite: IST 110

Back to top

B. COURSE OUTLINE:

1.  Brief outline

The course will consist of a number of modules, each introducing a group of mathematical concepts and presenting applications of those concepts to problems of information storage, information retrieval, information management, etc. in both computers and humans.

MODULE 1: SET, RELATIONS, FUNCTIONS, NUMBERS

  • set operations, applications of n-ary relations, equivalence
  • relations, function composition, inverse functions, logarithms,
  • exponential function, number systems, applications of number theory
  • APPLICATIONS: mathematical data types (integers, fractions, real numbers, complex numbers, tuples, function spaces); Shannon's H; exponential growth; non-feasible algorithms; public key encryption.

MODULE 2: LOGIC AND BOOLEAN ALGEBRA

  • predicates, quantifiers, formulas, interpretations, syllogisms, logical consequence, tableau method, boolean connectives, boolean functions, valuations, truth tables, logic gates.
  • APPLICATIONS: database query languages; specification languages; switching circuits; boolean search expressions; production system models of users.

MODULE 3: COMBINATORICS AND PROBABILITY

  • combination, permutation, discrete probability
  • APPLICATIONS: lexicographic ordering; combinatorial explosions; lower bounds of algorithms; reliability of computer systems; how people view probability, gambler's fallacy.

Back to top

MODULE 4: GRAPHS AND TREES

  • directed and undirected graphs, weighted graphs, walks, paths, matrix representations, graph algorithms, spanning trees, rooted and structured trees, combining trees to form new trees, inserting nodes in trees, sorting, searching.
  • APPLICATIONS: flow diagrams; task scheduling; critical paths; network connectivity; finite state machines; parsing; derivation; trees as data structures for storing information; semantic networks; Petri nets as models of systems; matrices as representations of networks.

MODULE 5: INDUCTION AND RECURSION

  • induction and recursion on the natural numbers and other structures such as trees.
  • APPLICATIONS: recursive evaluation of mathematical and boolean expressions; recursive searching and sorting algorithms; asymptotic analysis of algorithms.

MODULE 6: GRAMMARS, LANGUAGES AND FINITE STATE MACHINES

  • alphabets, strings, grammars, languages, regular languages, regular expressions, finite state machines, language recognizers.
  • APPLICATIONS: regular expression search; ATNs; efficient pattern matching using finite-state machines; task modeling languages.

    This course will incorporate collaborative and action-learning experiences wherever appropriate. Emphasis will be placed on developing and practicing writing, problem solving, and speaking skills through application of the concepts that define the course.

Back to top

2.  Listing of the major topics:

This list is a suggested order with reference to Washburn, Marlowe, Ryan. Discrete mathematics.

    Week 1:  Introduction, Simple recursion, Induction
    Week 2:  Sets, strings
    Week 3:  Recursion, Number Theory
    Week 4:  Clock arithmetic, Functions
    Week 5:  Combinations, Graphs intro
    Week 6:  Trees and Search
    Week 7:  Proof and Logic
    Week 8:  Further logic
    Week 9:  Algorithms
    Week 10:  Graph algorithms
    Week 11:  Algorithm complexity
    Week 12:  Probability
    Week 13:  Language, Grammars
    Week 14:  Grammars and Languages
    Week 15:  Entropy

Back to top

3.  Course Description:

IST 230 is one of the five introductory core courses for the Baccalaureate degree program in Information Sciences and Technology. The purpose of IST 230 is to provide students with an understanding of an array of mathematical concepts and methods which form the foundation of modern information science, in a form that will be relevant and useful for IST students. Exams and assignments will be used to assess that understanding.

IST 230 will draw some of its material from several mathematical disciplines: formal language theory, mathematical logic, and discrete mathematics. In-depth treatments of each of these subjects are offered elsewhere in the University as advanced mathematics and computer science courses. The difference is that

IST 230 will present these concepts in a more elementary way, with much more emphasis on IST applications. Understanding of these concepts will be tested through assignments and examinations.

IST 230 will be structured as a small number of modules. Each module will introduce a group of mathematical concepts and present applications of those concepts to problems of information storage, information retrieval, information management, in both humans and machines. These include: Module 1: set, relations, functions, numbers; Module 2:logic and boolean algebra; Module 3: combinatorics and probability; Module 4: graphs and trees; Module 5: induction and recursion; Module 6:grammars, languages and finite state machines.               

Back to top

 

Link to IST Home

| Students | Prospective Students | Courses |  
|
Curriculum | Faculty & Staff | Solutions Institute | IST Around PSU |
|
Partnerships | Research |
|
PSU Resources | Calendars | Contact Us |

| IST Home | Headlines | Contact Us | Help | Text Only | About Us |

Link to PSU

© Copyright 2000 The Penn State School of Information Sciences and Technology
Penn State is an Equal Opportunity Employer
Please direct all inquiries or comments to the
IST Webmaster