Övning 5

Automater, reguljära uttryck, syntax, bästaförstsökning

* diagnostiskt prov¶


* ABRAKADABRA Konstruera en KMP-automat som söker efter texten "ABRAKADABRA" Ange även den next-vektor som definierar automaten. Ungefär hur många jämförelser behövs för att automaten ska se att ordet inte finns med i "Harry Potter och Fenixorden", en bok på 1.8 Mbyte?
* a) Skriv ett regex som letar upp alla namn i en text.b) Skriv ett regex som matchar alla pythonfiler.
* a) Givet det reguljära uttrycket s(a|o)nd-?låda Skriv upp tre strängar som matchas av det reguljära uttrycket och ett som inte gör det. b) Söka efter Kronskog Skriv ett reguljärt uttryck som matchar alla tänkbara sätt att stava namnet Kronskog (Crounskog, Krohnskoog, etc).
* Syntax för kanadensare (Tildatenta 13 mars 2004) Olle sitter och rättar ett tentatal. Tentatalet går ut på att man ska skriva en grammatik för meddelanden av följande typ: Kanot 42, kanot 666, kanot 4711 och kanot 17 ska in! Kanot 1 och kanot 2 ska in! Kanot 13 ska in! Vilken eller vilka av följande fyra alternativ kan producera dessa meddelanden? Motivera med exempel varför de övriga inte kan producera dem. En del av alternativen kan producera oönskade meningar, man vill tex inte ha 'Kanot 1 och kanot 2, kanot 3 och kanot 4 ska in!' Vilket eller vilka av alternativen kan producera oönskade meningar? Ge exempel. (1) <meddelande> ::= Kanot <tal><svans> | <meddelande> kanot <tal><svans> <svans> ::= och| ska in! | , <tal> ::= 1 | 2 | 3 | ... (2) <meddelande> ::= Kanot <tal> ska in! | Kanot <tal><svans> <svans> ::= och kanot <tal> ska in! | , kanot <tal><svans> <tal> ::= 1 | 2 | 3 | ... (3) <meddelande> ::= Kanot <tal><svans> <svans> ::= ska in! | , kanot <tal> | och kanot <tal> <tal> ::= <svans> | 1 | 2 | 3 | ... (4) <meddelande> ::= Kanot <tal><svans> | kanot <tal><svans> <svans> ::= ska in! | , | och <tal> ::= 1 | 2 | 3 | ...
* Värsta webbsyntaxen (Tildatenta 31 augusti 2000) En webbfil innehåller dels webbsidans text, dels taggar för radbrytningar och indragningar. Taggen <BR> ger ny rad och för att få indragning av ett textavsnitt skriver man taggen <Q> före och taggen </Q> efter. Exempelvis ger webbfilen Organismer Organismer <BR> <Q> Djur <BR> <Q> Flugor <BR> Sillar <BR> </Q> Svamp <BR> <Q> Flugsvamp <BR> Sillkremla <BR> </Q> </Q> följande webbsideutseende: Organismer Djur Flugor Sillar Svamp Flugsvamp Sillkremla Skriv en syntax för webbfiler där endast dessa taggar och vanlig text förekommer. Du kan få använda för att beteckna godtycklig taggfri text.
* SL-tentan 2015-03-20, uppgift 2 (betyg E) Rymdvarelserna är trehövdade och kommunicerar enbart med tre tecken ’+’,’O’,’=’ (ett per huvud) så deras skrifter blir ganska långa. För att textsöka i skrifterna föreslår tildastudenten algoritmen KMP. Visa hur en KMP-automat för följande sökta text ser ut och ange även next-vektorn. + O = + O = = + O O O
* SL-tentan 2014-03-18, uppgift 8 (betyg C) Förtydligande: Skriv exempel på testfall som man kan testa syntaxen med. Se till att du får med olika sorters testfall.

7. BÅTFLYTT (Tildatenta 6 april 2002) Under en seglingstävling vill varje båt hitta den snabbaste vägen till målet. Problemet är att en segelbåt inte kan segla hur som helst och att den seglar olika snabbt beroende på vindriktning och styrka. Antag att havet förenklat består av en massa jämnt fördelade punkter med information om vindstyrka, vindriktning och vilka punkter som finns runt om. Beskriv en algoritm som på ett så effektivt sätt som möjligt tar reda på vilka punkter som ligger utefter den snabbaste seglingsvägen givet en startpunkt och en slutpunkt. Båtägaren är orolig att hans miljövänliga bottenfärg ska nötas bort och vill därför istället ta d en väg som är kortast (dvs minst antal steg). Förklara vad som behöver ändras i din föregående algoritm.¶ Använd bästaförstsökning med en prioritetskö som prioriterar på lägsta seglade totaltiden. Låt varje nod innehålla total seglingstid samt ha en faderspekare (för rekursiv utskrift av vägen då lösning hittats). Princip för genomgång av problemträdet:¶
* Lägg startpunktsnoden med totaltiden noll och tom faderspekare i prioritetskön.
* Upprepa punkterna 3-4 så länge kön inte är tom.
* Plocka ut en fadersnod ur kön. Om detta är slutpunkten, skriv ut vägen rekursivt och avsluta.
* Generera en son i taget genom att för varje punkt runt omkring fadersnoden skapa en sonnod med seglingstiden ökad beroende på vindstyrka, vindriktning och placering i förhållande till fadersnoden. Lägg in sonnoden i prioritetskön.
Om dumbarnskoll ska utnyttjas måste det ta hänsyn till både punkten och totala seglingstiden till den punkten. Alla söner med sämre tider till samma punkt är då dumsöner. På det viset slipper algoritmen besöka samma punkt flera gånger - den blir effektivare.¶ Eventuellt krävs någon snabb uppslagning av punkternas information, t ex med en hashtabell som hashar på punkternas nummer eller position. Noderna kan innehålla lägsta tid som uppnåtts för att tillåta dumbarnkoll utan att kräva extra minne.¶ För kortaste vägen, använd istället bredden först med en vanlig kö och blanda inte in totala seglingstiden i varje nod. I detta fall måste vi göra dumbarns koll för att sökningen ska bli effektiv.¶ Datastrukturer:Prioritetskö / köHashtabellNoder med seglingsdata¶ ¶ ¶ LÖSNINGAR

* A B R A K A D A B R A i 1 2 3 4 5 6 7 8 9 10 11 next(i) 0 1 1 0 2 0 2 0 1 1 0 KMP-sökning tar n+m jämförelser, där m är antal tecken i söksträngen och n är antal tecken i texten. Alltså 1.8 miljoner+11.
* a) sandlåda, sand-låda, sondlåda men inte syndlåda b) [CK]rou?h?nskoo?g [CK]ro[uh]*nskoo?g
* Syntax för kanadensare Alternativ 1 och 2 kan producera alla meningarna. Alternativ 3 och fyra kan inte producera 'Kanot 1 och kanot 2 ska in!' Alternativ 1 och 4 godkänner felaktigt 'Kanot 4 och'. Alternativ 3 godkänner felaktigt 'Kanot och kanot 2'.
* Värsta webbsyntaxen <webbfil> ::= <nothing> | <text> | <Q><webbfil></Q> | <webbfil><BR><webbfil> <Q> ::= "<Q>" </Q> ::= "</Q>" <BR> ::= "<BR>"
&#x0; ¶

¶

¶

¶

¶