- Briefly define, in the context of this course, each of the
following terms.
- nonfeasible - a problem which can be specified and
solved, but the resources (i.e., time) needed to solve the
problem increases much faster than the size of the problem
(e.g., exponentially), meaning we can only solve small problems
with little impact, more meaningful problems could not be
solved for any practical purposes (e.g., TSP)
- unsolvable (a.k.a., undecidable) - a problem which
can be specified but not solved (e.g., Halting Problem).
- TSP - Traveling Salesperson Problem, given a set of
cities to visit, find a tour which visits each city only one
time, ends at the start city, and completes the tour for
minimal cost.
- expert system - a field in AI which concentrates on
a narrrowly defined problem with a limited set of rules and
tokens which works like an expert in that problem.
- analog - measuring, as oppossed to discrete, which
counts.
- multiplexor/decoder - a multiway switch to select
one of N lines; since the machine is binary, lg N select lines
are needed to select among N lines.
- Explain why searching the phone book for a given phone number
is a more difficult problem than searching for a given name. For
extra credit, provide the time complexity (i.e., the function of N
which describes how much time it takes to solve the problem) for
each of these searching problems, where N is defined as the number
of names - phone numbers in the phone book.
- The names are ordered so we can use binary search (O(lg
N)), while the numbers are not sorted, requiring sequential
search (O(N)).
- Discuss why a deterministic "intelligent" machine would find
it difficult to resolve the following statement as either true of
false: "There are no absolute rules -- one should never say
never."
- A contradiction arises when this statement is applied to
itself, since it explicitly does what it professes should not
be done.
- Provide at least three features generally agreed to determine
if an entity is "intelligent".
- ability to learn, reconcile inconsistent statements, guess
when needed, perform as an expert in certain areas.
- Briefly discuss the distinction(s) between reasoning and
behavior pertaining to the definition of intelligence. Into which
camp does the "Turing Test" fall?
- Reasoning looks at the very processes that result in
intelligent behavior, while behavior only looks at the external
result of an intelligent agent.
- The Turing Test would fall in the latter category, defining
intelligence as looking for behaviors attributed to intelligent
humans.
- Add in binary:
0 1 0 1 + 0 1 1 1 = 1 1 0 0
- Name the two actions that a register can perform with data,
and give a brief description of each action.
- reading - copying the value without changing it
- writing - changing the value
- What is the name of the component responsible for
interconnecting the processor and memory (as well as other
devices)?
- Consider the circuit from the sample exam ...
- provide the corresponding truth table
- a b c
- 0 0 0
- 0 1 1
- 1 0 1
- 1 1 0
- b. provide an equivalent symbolic expression (i.e., boolean
function)
- c. what common function is this circuit equivalent to?
XOR
Page maintained by John
Dougherty,
Computer
Science, Haverford
College