Grafentheorie
-
Hallo allemaal,
Wij doen samen ons pws over de grafentheorie. Voor een pws is het natuurlijk niet genoeg om alleen de grafentheorie te beschrijven. Wij willen ook een probleem oplossen met behulp van een graaf. Weten jullie zo'n probleem dat niet te moeilijk is voor een 6vwo leerling, maar wel uitdaging biedt?
Groet Geert
-
Hoi Geert, @Geertvdk
Excuses voor de late reactie; De student die jullie het beste zou kunnen helpen is tot eind deze week helaas niet beschikbaar. Ik kan jullie helaas ook niet op weg helpen, maar volgende week kunnen jullie een antwoord van onze informatica student verwachten.
Groetjes,
Juul -
Hey @Geertvdk
Weer terug van weg geweest kan ik jullie hopelijk goed verder helpen. Met grafen kun je namelijk ontzettend veel! Ik weet niet welke studie richting jullie willen gaan kiezen maar als dat Informatica wordt is dit als PWS onderwerp een goede voorsprong.
Met grafen kun je ontzettend veel problemen oplossen. Lees die vooral door voor wat achtergrond informatie. Maar om een probleem uit te zoeken wat jullie gegandeerd kunnen oplossen lijkt het me het beste om naar 1 van de volgende twee te kijken. Dijkstra's algoritme en "The Travelling Salesman Problem". Dit zijn beide best bekende problemen die ook heel goed zijn uitgewerkt in de informatica wereld. Er zal dus een hoop over te vinden zijn. Hopelijk vinden jullie de problemen die hier voorkomen ook 'echt' genoeg, en niet te abstract zoals sommige andere problemen die je kan oplossen met grafen.
Ik hoop jullie op deze manier goed verder te hebben geholpen, als er nog andere vragen zijn, hoor ik die graag!
Jip -
Hallo Jip Rietveld
Ook ik sorry voor het late reageren.
Alleen wij zoeken meer naar een onderwerp waar we niet al te ingewikkelde computerprogramma's hoeven te gebruiken. Wij zijn er al achter gekomen dat we Python gaan gebruiken.
We dachten zelf al aan een probleem als een studentenflat waar je een douche, woonkamer, slaapkamers e.d. hebt en dat je dan een database hebt met wie het meest naar de wc gaat of wie het vroegst gaat slapen e.d. en dat je aan de hand daarvan de slaapkamers op gaat stellen.
Dat is een probleem dat we kunnen doen, alleen weten we niet hoe je zoiets kunt oplossen. Heb jij daar een idee van?
Een ander soort probleem zou iets kunnen zijn met het social network zoals bijvoorbeeld op Linkedin, hoe kun je met de meeste mensen in contact komen.
Of we hebben een database met allerlei mensen met bepaalde eigenschappen (zo'n database staat dan misschien ergens op internet, dat weten we nog niet) en aan de hand daarvan ga je groepjes selecteren of iets anders ermee doen. Maar dan nog blijft de vraag, hoe ga je dat aanpakken. Heb jij misschien een ideetje? Het zou ons toch weer wat verder helpen. We lopen een klein beetje vast :(
Geert en Josephine -
Okay @Geertvdk
Het klinkt heel leuk. Het probleem van zelf zo'n probleem opstellen kan af en toe heel moeilijk zijn. Misschien is er geen optimale opstelling, misschien vergeten je zelf verzonnen parameters iets wat van levens belang is etc.
Dat gezegd hebbende denk ik wel dat er meer dan genoeg bestaande problemen zijn waar jullie naar kunnen kijken. Deze is bijvoorbeeld heel makkelijk te begrijpen, maar uiteindelijk komt er veel bij kijken. Waar ik aan denk als ik zo jullie verhaal lees is dat jullie misschien je PWS over "Greedy Algorithms" moeten doen.
Deze zogenaamde "Greedy Algorithms" heten zo omdat zij met een greedy (gretige) keuze wel bij een optimum komen. Kijk maar naar de greedy oplossing van het het probleem hierboven. Deze Greedy Algorithms zijn het meest simpele soort algoritmes die informatici gebruiken om veel problemen (en misschien die van jullie die jullie hierboven noemen) op te lossen.
Ik weet dat dat niet perse grafen theorie is. Misschien is een simpel probleem met grafen het maximum flow problem maar ook daar komen veel Informatica termen bij kijken.
Ik hoop dat ik jullie zo weer een beetje op weg help.
Succes!
Jip -
Wij zijn nu met het plan gekomen om het kortste pad te berekenen om je producten te pakken. We willen hierbij de Python gebruiken. We hebben ons nog niet in de taal verdiept. Misschien dat jij er meer over weet en wat opties voor ons hebt, over hoe wij Python hierbij het beste kunnen toepassen? Hoe wij misschien een soort plattegrond/graaf kunnen maken met de producten o.i.d.
Heb jij misschien ook wat literatuur voor ons over de grafentheorie? Zodat we ook ons meer kunnen verdiepen in de grafentheorie op zich.
Geert en Josephine
-
Ik bedoelde het kortste pad in een supermarkt. Hoe pak je het snelst alle producten zonder al teveel om te lopen.
-
Hey @Geertvdk
Ik heb zelf niet veel ervaring in Python. Zelf ken ik Java als programmeertaal heel goed en kan ik daarin ook jullie het beste helpen. Wel is deze taal wat ingewikkelder dan Python. Dat gezegd hebbende zijn beide goeie keuzes.
Het eerste wat je moet realiseren is dat als je dit probleem gaat oplossen met programmeren is dat je niet perse iets visueels gaat hebben (behalve als je dat programeert natuurlijk!) maar dat het merendeel van de 'magie' van het oplossen zal gebeuren achter de schermen van jullie code.
Nu even over het programmeren zelf (dit zal gelden voor Python, Java en elke andere programmeer taal). Het eerste wat je moet doen is een manier vinden om de supermarkt plekken te vertalen naar een taal die de computer snapt. Het schap broodbeleg en het schap snoepgoed ga je niet zo in je programma verwerken. Nee dat worden schap 1 en 2 die je vervolgens extern (of intern kan ook) van je programma linkt aan de goede naam. Die graaf in een taal die de computer kan lezen zal er ongeveer zo uit zien gok ik.
1 2 20Dat vertaalt zich dan naar: "Van schap 1 naar schap 2 is 20 meter"
Vervolgens moet je een manier bedenken om dat op te slaan, en vervolgens op wat voor manier je je algoritme daarop kan uitvoeren, maar dat kunnen jullie allemaal zelf uitzoeken in jullie PWS.Het probleem wat jullie hebben uitgezocht lijkt veel op deze: The Traveling Salesman Problem in een combinatie met Dijkstra's algoritme. Lees je daar lekker op in en kwa het programmeren van deze problemen zal er ook veel op het internet staan.
Kwa grafentheorie kan ik jullie wel wat ingewikkelde links sturen maar ik denk dat als je de basics snapt en die kan inzien in de problemen die ik hierboven heb genoemd dat dat voldoende is.
Veel succes ermee!
Groetjes,
Jip -
Hallo,
Wij doen ons profielwerkstuk over de theorie Six degrees of Separation. Wij onderzoeken of deze theorie wiskundig te bewijzen is dmv een graaf. Hierbij lopen wij een beetje vast omdat wij niet weten welke graaf we moeten gebruiken. Kunt u ons misschien helpen?
Groetjes,
Janne Heslenfeld, Marlinne van Roessel, Laura Smulders 6VWO Odulphuslyceum Tilburg -
Hoi @laurasmulders
De soort graaf zal niet heel veel uitmaken verwacht ik, na wat basis onderzoek naar het probleem zal de graaf "undirected" (ongericht) zijn en "cycles" (cyclussen) bevatten. Maar voor de rest weet ik niet zeker of je die eigenschappen nodig hebt bij het bewijs van de stelling. Op de wikipedia pagina ziet het bewijs er namelijk niet al te lastig uit.
Maarja, ik hoop dat dit je verder helpt.
Jip
