Skip Navigation
search: People Opens New Window | Departments Opens New Window | Penn State Opens New Window | Web Opens New Window
Penn State mark
Penn State mark

University Bulletin

Undergraduate Degree Programs

Information Sciences And Technology (IST)

IST 230 Language, Logic, and Discrete Mathematics (3) Introduction to formal languages, mathematical logic, and discrete mathematics, with applications to information sciences and technology.

IST 230 Language, Logic, and Discrete Mathematics (3)

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, 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, and in a more eclectic, web-based format. 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, etc. These include: MODULE 1: SET, RELATIONS, FUNCTIONS, NUMBERS set operations, applications of relations, equivalence relations, function composition, inverse functions, logarithms, exponential function, number systems, applications of number theory. APPLICATIONS: mathematical data types (integers, fractions, real numbers, tuples, function spaces); 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. MODULE 3: COMBINATORICS AND PROBABILITY combination, permutation, discrete probability APPLICATIONS: lexicographic ordering; combinatorial explosions; lower bouncs of algorithms; reliability of computer systems 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. 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; efficient pattern matching using finite-state machines.


General Education: None
Diversity: None
Bachelor of Arts: None
Effective: Spring 2004
Prerequisite: MATH 110 orMATH 140

Note : Class size, frequency of offering, and evaluation methods will vary by location and instructor. For these details check the specific course syllabus.