|
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 |
