Tentamen (uitwerkingen)
Documents for NLP
- Vak
- Instelling
A collection of exam questions and summary notes for the course that will be helpful for students
[Meer zien]Voorbeeld 3 van de 18 pagina's
Voorbeeld 3 van de 18 pagina's
In winkelwagen
In winkelwagen
gesponsord bericht van onze partner
Verkoper
Volgen
mohamedsaleh
Voorbeeld van de inhoud
Chair of Robotics, Artificial Intelligence and Real-time SystemsDepartment of Informatics
Technical University of Munich
Note:
Ecorrection • During the attendance check a sticker containing a unique code will be put on this exam.
Place student sticker here • This code contains a unique number that associates this exam with your registration number.
• This number is printed both next to the code and to the signature field in the attendance check list.
Grundlagen der künstlichen Intelligenz
n
Exam: IN2062 / Endterm Date: Monday 1st March, 2021
Prof. Dr.-Ing. Matthias Althoff 18:15 – 19:45
tio
Examiner: Time:
P1 P2 P3 P4 P5 P6 P7 P8 P9 P 10
I
Working instructions
• This exam consists of 18 pages with a total of 10 problems.
lu
So
Please make sure that you received a complete copy of the exam.
• The total amount of achievable credits in this exam is 61.5 credits.
• Detaching pages from the exam is prohibited.
es
• Allowed resources:
e
– a pen or PDF editor (do not write with red or green colors nor use pencils)
ot
– a non-programmable pocket calculator
N
l
– the provided formula sheet
p
– empty scratch paper (do not submit)
on
• Please write answers on the exam booklet only. If you run out of space, write on the additional pages provided.
m
Notes on other paper will be disregarded.
i
ct
• You must hand in all pages of the exam.
• Answers are only accepted if the solution approach is documented. Give a reason for each answer
re
Sa
unless explicitly stated otherwise in the respective subproblem.
or
• All subproblems are solvable independently from each other if not explicitly stated differently.
• Multiple-Choice questions are evaluated automatically. Use a cross to select your answer:
C
Answer A
Answer B
If you want to correct your answer, fill out the checkbox, and cross your new answer:
Answer A
Answer B
Notes next to the checkboxes cannot be evaluated.
Left room from to / Early submission at
– Page –
, Problem 1 Search (10.5 credits)
In the following tasks we search for a path from node A to node G , if not stated otherwise. If multiple nodes can be
explored next, alphabetic ordering should be used as the tie breaker, e.g., if B and C are added to the frontier, B is
added first.
On each of the following graphs we apply breadth-first (BFS) and depth-first (DFS) Graph-Search. Find out which
graphs are explored by each algorithm in the order A , B, C, D .
1 2 3
A B A B A B
C D C D C D
n
tio
E G E G E G
a) Tick all graphs that are explored in the order A , B, C, D by BFS:
3 ×1 ×2
×3 lu
b) Tick all graphs that are explored in the order A , B, C, D by DFS:
×2
So
1
0 c) Name another uninformed search algorithm that explores the nodes in graph 1 in the same order as BFS:
1
es
Iterative Deepening Search, Uniform-cost search / Dijktstra with unitary cost
e
ot
N
l
d) Does Depth-First Tree-Search terminate for graph 2 (0.5 points)?
p
on
Yes × No
m
i
e) State the first four nodes visited by DFS Tree-Search searching from A to G on graph 2.
ct
0
½
re
A - right neighbor - A - right neighbor
Sa
or
C
– Page –
, A 3 E
f) Tick the third node visited by Uniform Cost Search on the graph to the left
5 4 (once more starting at A and searching for G ). The start node A is the first visited
node. The numbers on each edge indicate the path costs between nodes (1
8 B C point).
6 7 A B D
D G E ×C G
g) Alter as few edge costs as possible on the graph from 1.f) such that B is visited third. You may either do so in the 0
printed graph or by writing the changed edge costs, i.e., if you change the cost between node X and Y to Z , write
d(X , Y ) = Z . 1
n
In the end d(topright, middleright) > d(topright, middleleft). X
-.5 if more than one changed cost but still
middle-left visited third. If more changed also make sure d(A , bottomleft) > d(A , topright)+d(topright, middleleft)
tio
must hold
For another search problem, the following two heuristics h1 and h2 are used for searching from A to G . We want to
lu
construct an optimal meta heuristic h ∗ taking into account information from both h1 and h2 .
h) Fill in the values for an admissible heuristic h ∗ dominating h1 and h2 assuming h1 and h2 are admissible. 0
So
1
Node n A B C D E F G
2
h1 (n) 4 3 10 11 9 5 8
h2 (n) 7 11 7 8 4 8 9
es
h ∗ (n)
h ∗ (n) = max {h1 (n), h2 (n)}, so always the bigger of the two should be chosen -0.5 for each wrong value
e
ot
i) Use the heuristic h1 from 1.h) for greedy best-first graph search on 0
E A B
the graph to the left starting from A and searching for G . State the
N
l
nodes in the order they are explored before completing the search. 1
C
p
on
F D G Depends on graph (encoded by two left nodes, first one top
left)
m
BF - A - B - E - F - G (1)
i
BD - A - B - F - E - G (6)
ct
EF - A - B - E - C - G (13)
j) Would A ∗ Tree-Search be optimal when using h2 as a heuristic (0.5 points)?
EB - A - F - E - C - G (18)
re
×
Sa
Yes FB - A - F - E - No
B - G (22)
-0.5 if single mistake, otherwise 0
or
k) Give a reason why (not)? 0
C
1
Not admissible / not underestimate / h2 (G) > 0 / cost of goal bigger 0
– Page –
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper mohamedsaleh. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €7,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 77333 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen