Finan Exam Practice Flashcards
In class, various definitions of AI were given. It was argued that AI should be defined as “systems that act rationally”. Give another example definition of AI that was discussed in class, and in no more than two sentences, explain why the \acting rationally” definition is to be preferred.
Example: AI is a system that acts like human. The problem with this definition is that humans not always act rationally. And usually we prefer the system to be rational, if you build a rational system you can always tweak it to be irrational.
Describe the difference between a deterministic representation and stochastic representation of an AI system.
A system is stochastic if one of the following is true:
- Sensing uncertainty - agent cannot fully observe the current state of the world
- Effect uncertainty - agent does not fully know the effects of its actions.
Explain why the following statement is true or false: In order to pass the Turing test, a computer would have to behave at least as rationally as human.
It is false, because to pass the Tuting test an agent must behave like human including cases where human acts irrational. The system doesn’t need to be more rational than human.
Compare and contrast an AI system that thinks and acts humanly with one that thinks and acts rationally.
AI system that thinks and act rationally behaves rationally in all cases, while system that thinks and acts humanly will behave rationally only when human would do that. Rationality is the best abstraction of intelligence.
State the five elements that characterize a search problem instance/search algorithm.
1) The way search the frontier is expanded
2) Completeness
3) Optimality
4) Time complexity
5) Space complexity
What is meant by search algorithm completeness?
An algorithm is complete if it is guaranteed to find a solution to a problem, if one exists, in finite amount of time.
What is meant by search algorithm optimality?
An algorithm is optimal if when the algorithm finds the solution it is the best possible.
Explain the distinction between optimality and optimal efficiency for search algorithms.
An algorithm is optimally efficient if there is no algorithm that finds an optimal solution better (less number of nodes expanded for example) that it does. Algorithms is optimal if the solution found is the best one.
What are advantages of breadth-first search (BFS) over depth-first search (DFS)? What is the advantage of DFS over BFS?
BFS is optimal and complete, while DFS is not optimal and gets stuck in cycles. BFS is better when there are many solution and the goal is to find the best solution possible. Or when solution lies close to the start node. DFS in it’s turn has better space complexity and works better when there is only one solution and it lies far from the start node.
Explain what the frontier is in a graph-search problem, and what it is used for.
Frontier is a set of paths which could be explored next.
What node(s) is/are in the frontier of a depth-first search.
DFS keeps expanding one path until it reaches the leaf. All nodes that were expanded and their childs were added to the frontier. The frontier contains every child of the one single node expanded at each level of the tree.
Where b is the maximum branching factor and d is the maximum depth of the serach characterize the maximum size of a DFS frontier.
In a DFS, the frontier contains every child of the one
single node expanded at each level of the tree. Thus, the frontier contains a maximum of bd nodes.
Is the worst-time complexity different for DFS and BFS? Why or why not?
No, it is the same. Because in the worst case, both DFS and BFS must explore all nodes in the graph.
What is the disctinction between informed and uninformed search?
Uninformed search strategies are those that do not consider any inforamtion about the states and the goals to decide which path to expand first on the frontier. They are blind to the goal and do not take into the account the specific nature of the problem.
What is heuristic?
A search heuristic h(n) is an estimate of the distance/cost of the optimal (cheapest) path from node n to a goal node. It can be used to guide the search.
