CS 480 Final Exam Terms and Concepts

Chapter 1

• What is AI?
• thinking vs acting, humanly vs rationally
• a little bit of history

Chapter 2 Intelligent Agents

• Terms: agent, environment, sensors, actuators, percept, agent function, agent program, rational agent, performance measure, information gathering, learning
• Describing task environments (PEAS)
• Properties of task environments:
  1. fully observable vs partially observable
  2. single agent vs multiagent
  3. deterministic vs stochastic
  4. episodic vs sequential
  5. static vs dynamic
  6. discrete vs continuous
• kinds of agent programs:
  1. table-driven agents
  2. simple reflex agents
  3. model-based reflex agents
  4. goal-based agents
  5. utility-based agents
  6. learning agents
• representational complexity: atomic, factored, structured

Chapter 3 Search

• problem-solving agents
• formulating problems, consisting of:
1. initial state
2. actions
3. transition model
4. goal test
5. path cost function
• basic tree search and graph search algorithms
• measuring performance:
  1. completeness
  2. optimality
  3. time complexity
  4. space complexity
• Uninformed search strategies:
  1. breadth-first search
  2. uniform-cost search
  3. depth-first search
  4. depth-limited search
  5. iterative deepening depth-first search
• Informed search strategies:
  1. greedy best-first search
  2. A* search
  3. what heuristics are, where they come from, what makes a heuristic admissible

Chapter 4 Local Search and Optimization

• hill climbing search
• simulated annealing
• genetic algorithms

Chapter 5 Adversarial Search

• basic organization of adversarial search: initial state, transition model, terminal test, utility function
• minimax algorithm
• minimax with alphabeta pruning
• effect of adding chance to adversarial search

Chapter 6 Constraint Satisfaction Problems

• Basic idea that a CSP consists of a set of variables, domains for each variable and a set of constraints on the values of the variables.
• Basic idea of the backtracking search algorithm.
• Some notion of the heuristics for doing effective search.
• Idea of using local search (on complete problem instances) to solve CSP problems

Chapter 7 Propositional Logic

• terms: knowledge base, sentence, inference, entailment, syntax, semantics
• knowledge level, logical level, implementation level
• issues that arise in the Wumpus World
• understand and be able to explain Figure 7.6
• soundness and completeness
• converting to CNF and doing resolution in propositional logic

Chapter 8 and a bit from 9 First Order Logic

• terms: objects, relations, functions, quantifiers
• expressing simple English sentences in FOL
• converting FOL sentences into CNF
• unification
• proving and answering questions using resolution in FOL

Chapter 10 Classic Planning

• states, actions and goals
• preconditions and effects (add list and delete list)
• partial-order planning, search through plan space

Chapter 13 Uncertainty

• reasons why uncertainty exists
• Boolean random variables, discrete random variables
• prior probability, probability distribution, full joint probability distribution
• product rule P(a and b) = P(a|b)P(b) = P(b|a)P(a)
• independence (absolute and conditional)
• Bayes' Rule

Chapter 18 Inductive Learning

• kinds of learning: supervised, unsupervised, reinforcement
• terms: induction, Occam's razor
• learning decision trees
• basic idea of how it works
• training set vs. test set
• how attributes are chosen

Section 18.7 Neural Networks

• basic model of a neuron, what the parts are
• terms: activation, units, weight, bias weight, threshold function, feed-forward vs. recurrent networks, hidden units, linearly separable, back-propagation algorithm, cluster analysis
• Build simple networks "by hand"

Section 23.5 Speech Recognition

• terms: speech recognition, speech understanding, phones, coarticulation, bigram model, hidden Markov models

Chapter 22 and a bit of 23 Communication (Language)

• terms: natural language vs. programming language, grammar, formal language, parse trees, syntax, semantics, speech acts
• stages in communication and ways they can go wrong
• issues in "real" language
  • ambiguity (be able to give different kinds of examples)
  • indexicality, metonymy, metaphor, noncompositionality
• information retrieval
  • basic idea of how IR systems work
  • precision vs. recall and the tradeoffs
  • stopping and stemming
• information extraction: basic idea of what it is

Chapter 25 Philosophical Foundations

• weak vs. strong AI
• thought experiments: Searle's Chinese room, Turing test