TILDA, ÖVNING 3 TILDA, EXERCISE 3 ______________________________________________________________________ ______________________________________________________________________ ********************************************************************** ************************************************** ******************** Problemträd, breddenförst, djupetförst, hashning Problem Tree, breadth first, depth first, hashing 1 STRYKORD 1 STRYKORD Ordet orkan är ett strykord eftersom man kan stryka sista The word hurricane is a strykord because you can delete the last bokstaven om och om igen och bara få riktiga ord. the letter over and over again and just get real words. orkan - orka - ork - or - o hurricane - hurricane - strength - or - o Uppgiften är att finna det längsta strykordet i svenska The task is to find the longest word in the Swedish Coffee språket. language. Ordlistan finns på fil. The glossary is on file. Rita problemträdet och Draw tree problems and jämför olika tänkbara algoritmer. compare different possible algorithms. ______________________________________________________________________ ______________________________________________________________________ Tomt ord är stamfar, barnen får man genom att lägga på en Empty words, the progenitor, the children may be by adding a bokstav och kolla i ordlistan. letter and check the dictionary. Eftersom man inte är ute Since you are not out there efter kortaste strykord utan tvärtom längsta är breddenförst after the shortest strykord but rather the longest width is only inte nödvändigt. not necessary. Rekursiv djupetförst som går igenom hela trädet Recursive depth first going through the whole tree och noterar längdrekord är kanske bäst, särskilt eftersom and notes the length of the record is perhaps best, especially because letandet i ordlistan då hela tiden går framåt! searching the dictionary, then constantly moving forward! Här har jag Here I lagt alla svenska ord i ett binärträd - det tar förstås mycket put all the Swedish words in a binary tree - of course it takes much minne och är onödigt. memory and is unnecessary. Man kan i stället läsa filen ord för ord One can instead read the file word for word eftersom man aldrig behöver backa. because you never have to go back. # coding:iso-8859-1 # Coding: iso-8859-1 def byggut(ord): def byggut (words): """ Rekursiv djupetförst""" "" "Recursive depth first" "" global rekord world record if len(ord) > len(rekord): If Len (word)> len (record): rekord = ord record = words for tkn in alfabet: TKN for the alphabet: if svenska.exists(ord+tkn): f svenska.exists (TKN + words): byggut(ord+tkn) byggut (word + TKN) from bintree import Bintree imports from bintree Bintree alfabet="abcdefghijklmnopqrstuvwxyzåäö" alphabet = "abcdefghijklmnopqrstuvwxyzåäö" rekord="" record = "" svenska=Bintree() Swedish Bintree = () svenskfil = open("words.txt") svenskfil = open ("words.txt") for rad in svenskfil.readlines(): for row in svenskfil.readlines (): svenska.put(rad.strip()) #Ta bort returtecknet svenska.put (rad.strip ()) # Remove the return character byggut("") byggut ("") print "Längsta strykord: ", rekord print "Longest strykord:", record ______________________________________________________________________ ______________________________________________________________________ ********************************************************************** ************************************************** ******************** 2 SJUOR TILL HUNDRA 2 Sevens TO ONE HUNDRED Det gäller att skriva talet 100 med enbart sjuor och dom You have to leave the 100 with only sevens and Judgement fyra räknesätten, till exempel så här. subtraction, multiplication, such as this. 7 +7 /7 *7 *7 =98 7 +7 / 7 * 7 * 7 = 98 Det var ett gott försök som inte nådde ända fram. It was a good attempt that failed to live up. För att To man ska få använda / måste divisionen gå jämnt ut. you should use / division must break even. Rita Rita problemträdet och diskutera bästa algoritm för att avgöra problem tree and discuss the best algorithm for determining OM problemet är lösbart. If the problem is lösbart. Om man dessutom vill veta hur lösningen ser ut krävs en If you also want to know what the solution looks like, a mer komplicerad datastruktur. more complicated data structure. Beskriv den och skissa ett Please describe the sketch and a program. programs. ______________________________________________________________________ ______________________________________________________________________ Som gjort för breddenförst med heltalskö. As done for the width of the first heltalskö. # coding:iso-8859-1 # Coding: iso-8859-1 from queue import Queue from Queue import Queue q = Queue() q = Queue () def makesons(tal): def husband, son (number): if tal==100: ' f number == 100: ' print "Hundra!" print "A hundred!" q.put(tal+7) q.put (voice +7) q.put(tal-7) q.put (voice-7) q.put(tal*7) q.put (number * 7) if(tal%7==0): if (number% 7 == 0): q.put(tal/7) q.put (voice / 7) q.put(0) q.put (0) while not q.isempty(): While note q.isempty (): makesons(q.get()) husband, son (q.get ()) Om man ska skriva ut lösningen: If you are printing solution: class Node: class Node: def __init__(tal = 0, far = None): def __init__ (Number = 0, father = None): self.tal = tal self.tal = speech self.far = far self.far = father from queue import Queue from Queue import Queue from sys import exit from sys import exit q=Queue() q = Queue () def insert(tal,far): def insert (speech, father): nod=Node(tal, far) node = Node (speech, father) q.put(nod) q.put (node) def makesons(far): def husband's son (father): tal = far.tal speech = far.tal if tal == 100: f number == 100: writechain(far) write chain (father) exit() exit () insert(tal+7, far) insert (+7 speech, father) insert(tal-7, far) insert (number-seven, father) insert(tal*7, far) insert (* 7 speech, father) if(tal%7==0): if (number% 7 == 0): insert(tal/7, far) insert (voice / 7, father) def writechain(p): def write chain (p): if p != None: If P! = None: writechain(p.far) write chain (p.far) print p.tal print p.tal q.put(Node()) q.put (Node ()) while not q.isempty(): While note q.isempty (): makesons(q.get()) husband, son (q.get ()) ______________________________________________________________________ ______________________________________________________________________ ********************************************************************** ************************************************** ******************** 3 PERFEKT HASHFUNKTION 3 PERFECT hash function Hitta på en perfekt hashfunktion för atomer. Find the perfect hash function for atoms. Hur stor blir How much will hashtabellen? hash tables? ______________________________________________________________________ ______________________________________________________________________ Låt a=1, b=2, ..., z=26 och A=0, B=27, ..., Z=675 (25*27) Let a = 1, b = 2, ..., z = 26 and A = 0, B = 27, ..., Z = 675 (25 * 27) Då blir hash("A")=0 och hash("Zz")=701, så det behövs Then hash ('A') = 0 and hash ("Zz") = 701, so it is necessary 702 platser i hashtabellen (dvs ca sex gånger mer än antalet element). 702 locations in the hash tables (ie, approximately six times more than the number of elements). Ingen extra luft - det blir inga krockar! No extra air - there are no crashes! I labb 5 ska ni inte göra en så här stor tabell utan istället In lab 5, you shall not make such a large table, but instead använda kvadratisk probning. use quadratic probing. ______________________________________________________________________ ______________________________________________________________________ ********************************************************************** ************************************************** ******************** 4 HÅLL REDA PÅ MEDIA (Tildatenta 030308) 4 WAY OUT MEDIA (Tilda Exam 030 308) Under gulfkriget var det väldigt svårt för armestaben att hålla reda During the Gulf War, it was very difficult for the Army Staff to keep track på alla TV-bolag som for omkring och rapporterade i öknen. on all broadcasters who went around and reported in the desert. För att To hålla reda på dem användes en hashvektor. keep track of them used a hashvektor. Koden fungerade inte som The code did not work as avsett och man har nu gett i uppdrag åt en fd tildastudent att intended and has now given a mandate to a former student to tilda titta på en misstänkt del av koden: look at a suspicious part of the code: from string import find from string import find p = 100; p = 100; hashvektor = [0]*p hashvektor = [0] * p alfabet = "abcdefghijklmnopqrstuvxyz" alphabet = "abcdefghijklmnopqrstuvxyz" def put(tvbolagsnamn, tvbolag): def put (tvbolagsnamn, tvbolag): hashcode = 0 hashcode = 0 for i in range(len(tvbolagsnamn)): for i in range (len (tvbolagsnamn)): alfanum = find(alfabet, tvbolagsnamn[i])+1 alfanum = find (alphabet, tvbolagsnamn [i]) +1 hashcode += alfanum hashcode + = alfanum hashcode = hashcode % p hashcode = hashcode% p hashvektor[hashcode] = tvbolag hashvektor [hashcode] = tvbolag Vad är det för fel på koden? What is wrong with the code? Beskriv hur man kan förbättra den. Describe how to improve it. Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. The names of the TV companies can be composed of up to three letters. Det kommer inte att förekomma mer än 75 TV-bolag. There will be no more than 75 television stations. ______________________________________________________________________ ______________________________________________________________________ Det som gör att koden inte fungerar är att det inte finns någon What makes the code does not work is that there is no krockhantering. collision handling. hashvektor[hashcode] = tvbolag; hashvektor [hashcode] = tvbolag; För att lösa det kan man använda t.ex. To solve it, you can use eg krocklistor eller linjär collision lists or linear probning. probing. Linjär probning fungerar så att om det är upptaget på Linear probing works so that if it is on the den givna positionen så söker man tills man antingen hittar the given position will search until we either find nyckeln (den var redan instoppad sedan tidigare) eller tills key (it was already visible, stuffed already) or until man hittar ett tomt element i vektorn. you'll find an empty element in the vector. Hashkoden är ganska korkat implementerad. Hashkoden is pretty stupid implemented. Strängarna "AB" och The strings "AB" and "BA" får samma värde. "BA" has the same value. alfanum = find(alfabet, tvbolagsnamn[i])+1 alfanum = find (alphabet, tvbolagsnamn [i]) +1 hashcode += alfanum hashcode + = alfanum För att lösa det kan man vikta genom att multiplicera med In order to solve it can be folded by multiplying by t.ex. eg 1, 100 och 10000. 1, 100 and 10000th Längden på hashvektorn är lite för liten och dessutom inget The length of hashvektorn is a bit too small and also no primtal. primes. Välj istället hashvektorns storlek till exempelvis 151 Choose instead hashvektorns size, for example, 151 (dubbelt så stor som förväntade antalet element). (Twice the expected number of elements). ______________________________________________________________________ ______________________________________________________________________ ********************************************************************** ************************************************** ******************** 5 Nix till telefonförsäljning (TILDA-tenta 000603) 5 Nix to telemarketing (TILDA-exam 000 603) Föreningen för konsumentskydd vid marknadsföring per telefon Association for Consumer Protection in marketing by telephone har startat ett register dit den som inte vill bli uppringd av has started a register in which the person does not want a call from telefonförsäljare kan anmäla sig. Telemarketers may register. Till att börja kommer kontrollen att ske genom att företaget sänder To begin the verification will be done by the company sends sin telefonlista till nix och får tillbaka en lista där de nixade their phone list to nix and get back a list showing the nixade numren markerats. numbers selected. Vilka av följande metoder kan föreningen använda sig av? Which of the following means the club can use? Vilken är bäst? Which is best? Binärträd, bloomfilter, hashtabell. Binary Tree, Bloom filters, hash tables. Ett framtida mål är att kontroll också skall kunna ske över internet. A future goal is to control also can be provided over the Internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att Then, the inspection done quickly but you also want to ensure that ingen ska kunna få ut en lista över alla nixade telefonnummer. nobody can get a list of all nixade phone. Vilken metod passar bäst för internet-kontrollen? Which method is best suited for Internet control? ______________________________________________________________________ ______________________________________________________________________ Just nu ringer många och anmäler sig till NIX-registret så det måste Right now many are calling and joining of the NIX code so it must gå lätt att lägga till nya. be easy to add new. Binärträd går snabbt att söka i men man måste se till att Binary Tree is quick to look at but you have to ensure that det inte blir obalanserat när nya telefonnummer läggs till. it does not become unbalanced when the new numbers are added. Bloomfilter är besvärligt att stoppa in nya nummer i. Bloom filters are cumbersome to put new code in. Hashtabell se bloomfilter ovan. Bloom filter hash tables see above. Bloomfilter är det bästa alternativet för den framtida internet- Bloom Filters are the best option for the future internet kontrollen. control. Man kan räkna med att många har registrerat sig så One can expect that many have registered so snabb sökning är nödvändig. Quick search is necessary. Dessutom har bloomfilter fördelen att ingen användare kan få ut Furthermore, Bloom filters advantage that no user can get telefonnummerlistan. phone list.