Samenvatting
Samenvatting - Inleiding adaptieve systemen (INFOB2IAS)
Samenvatting van alle hoorcolleges van Inleding adaptieve systemen!
[Meer zien]Voorbeeld 4 van de 40 pagina's
Voorbeeld 4 van de 40 pagina's
In winkelwagengesponsord bericht van onze partner
1 beoordeling
Door: jayjay8 • 8 maanden geleden
Voorbeeld van de inhoud
Inleiding Adap eve SystemenHC1 - Oneindigheid
The Computa onal Beauty of Nature
• Uitgangspunt: de natuur is een samenstelsel van kleine deeltjes die zelfstandig heel
gemakkelijk zijn geprogrammeerd maar samen heel complex en interessant gedrag
vertonen
• Simple rules make complex systems
• We moeten ze bekijken, niet simuleren -> typisch KI: a ijken wat je kunt gebruiken
en de rest laten zoals het is
• Opzet van het college: elke keer een ander onderwerp
Oneindigheid
• Er zijn oneindig veel verschillende oneindigheden. “Aleph nul/één/twee/…/omega”
• Aleph zijn kardinale getallen: geven groo e van verzamelingen aan
• Alleen maar a elbare verzamelingen in deze cursus
• Een verzameling heet a elbaar als deze op een rij kan worden gezet
• Typische a elbare verzameling: N (natuurlijke getallen), Q (breuken)
• A elbare verzamelingen zijn alomtegenwoordig in de wiskunde en exclusief
vertegenwoordigd in de informa ca
• Discreet (alles wat a elbaar is) vs con nu (alles wat gelijkma g is met R)
• Maakt het mogelijk elementen 1 voor 1 te bekijken/bewerken
• A elbare rij is van a elbare verzameling: a elbare vereniging (U) is ook a elbaar
• Een verzameling A heet a elbaar als er een injec e f: A -> N bestaat. Elk element A
moet genummerd worden en dat nummer moet uniek zijn. Niet alle nummers uit N
hoeven worden gebruikt.
• Belangrijke voorbeelden van over-a elbare verzamelingen zijn: de reeële getallen R,
alle deelverzamelingen van N, de verzameling van alle eindige en oneindige bitstrings
Aleph
• Aleph 0 is de kleinste oneindigheid, namelijk hoeveel
natuurlijke getallen, even nummers, oneven nummers,
ra onele nummers er zijn.
• Labeling things in order is di erent than coun ng them ->
• Line 0 does not contribute to the number of lines, but it
does when labeling the order the lines
• The rst ordinal number is omega: the next label you’ll
need a er using up the in nite collec on of every single
coun ng number rst
• A er omega comes omega + 1, etc. It is not bigger than omega, it just comes a er.
• The order type of Aleph 0 is omega, as long as it is well ordered.
, • But what is then bigger than aleph 0? The power set of aleph 0. Set of all the
di erent subsets. Aka 2 to the power of aleph 0
• Aleph 1:
• Dat gaat zo door, aleph 2 is omega 2 etc….
Diagonaal-argument
• Bewering [0,1] is niet a elbaar (= niet op een rij te ze en)
• Over-a elbaar: ontkenning van a elbaarheid
• Gelijkmach gheid van twee verzamelingen: als een bi-jec e tussen deze twee
bestaat -> “even groot”
• (0,1) en R zijn gelijkmach g -> ronde haken betekenen dat 0 en 1 er niet bij horen.
• h ps://libraryo abel.info/ laat een oneindige bibliotheek zien met 3200 characters
• Er bestaan ook machtsverzamelingen: 2^A.
Berekenbaarheid
• Gödel nummering: het redeneren van teksten/boeken/programma’s kan je
reduceren over redeneren over getallen (niet per se heel e cient)
• Maakt gebruik van het feit van de wiskunde: priem-ontbinding is uniek (hoofdstelling
van de rekenkunde)
• Voorbeelden: 12 = 4 x 3 = 2^2 x 3^1 = (2, 1), 20 = 4 X 5 = 2^2 X 3^0 X 5^1 = (2, 0, 1)
• ASCII tabel (char <-> 7 bits): alle characters krijgen een uniek getal
• Met Gödel nummering kunnen we dus vragen over strings, i.h.b. computer
programma’s, vertaald worden naar vragen over getallen. Het is een manier om een
berekenbare bi-jec e te de niëren tussen N en Strings
• Priem-ontbinding is uniek: dus elk natuurlijk getal correspondeert met ten hoogste 1
string
• Church-Turing
• Alle programmeertalen zijn even krach g (bijv. in het geval van invoer en uitvoer).
• Het is niet zo dat alle programmeertalen even handig ( jd en geheugen) & sterk zijn
in toepassingen (bijv. interac viteit).
• Turing-volledigheid: als een no e van berekening B (bijv C#) minstens even krach g is
als andere berekening, is B Turing-volledig. Minstens even krach g -> niet krach ger.
• De register-machine:
• Bewering: de register-machine is even sterk als Java: beiden kanten op bewijzen.
• Je schrij Macro’s op: variabelen
• Basis van berekening-concepten; Turing-machine.
,HC2 - Beslisbaarheid, berekenbaarheid
De Turing machine is even sterk als bv Java. Je kan de Turing machine simuleren in Java. Ook
andersom. Idee: kom met een rekenvoorschri die berekeningen in een iets minder primi ef
berekeningsmodel, waarvan we al weren dat de Turing compleet is, omzet naar
berekeningen op een Turing machine.
These van Church-Turing
Aanname: wat wij intuï ef onder berekenbaarheid verstaan, wordt vertegenwoordigd door
de klasse van (proefondervindelijk even sterke) berekening-mechanismen op N^N.
- Deze klasse is heel groot. Bevat alle Turing-equivalente berekening-mechanismen
- Dit is een aanname/afspraak. Niet een stelling.
Berekenbaarheid
- Als je problemen hebt zijn er verschillende soorten: vraag-typen
- Vaag of subjec ef (wat is het lekkerst)
- Voldoende precies geformuleerd: kortste pad
- Meest belangrijke vraagstuk
- Welke vragen zijn wel en niet met de computer te beantwoorden?
- Bestaan er vraagstukken die computers principieel (aannemende dat alle
programmeertalen die we nu kennen samen de no e berekenbaarheid
representeren)niet kunnen oplossen? - Ja
- We houden ons bezig met de berekenbaarheidstheorie
Onbeslisbaarheid
- Carcassonne puzzel
- Er bestaat geen algoritme, er kan ook geen algoritme bestaan, en zal ook nooit zo zijn dat
voor alle niet-royeerbare Carcassonne-tegelsets kan bepalen of deze het vlak kunnen
vullen
- Turing maakte kennis met het Entscheidungsprolem: niet alle problemen kunnen
mechanisch worden opgelost -> Turing-machine (WW2)
Het stop-probleem is onbeslisbaar
, Stelling: Zij J een programmeertaal. Als J voldoende expressie is (Turing-compleet), dan kan
er geen programma h (element van) J bestaan dat voor elke programma/input-combina e
(j,i) (element van) J x I kan uitmaken of j met input i stopt.
- Merk op: h is 2-plaatsig en de j’s zijn 1-plaatsig (h moet dus 2 teruggeven en j 1)
- Bewijs (van het ongerijmde). Stel h bestaat wel. Dus: h(j, i) = 1 j(i) stopt.
- Mbv h/2 is makkelijk een programma te schrijven voor de onberekenbare q/1: 1(i): if
h(i, i) = 1, then loop forever.
- Tegenspraak: dus een hal ng func e h/2 kan niet bestaan.
Het invoer loze stop-probleem
Problemen al jd hetzelfde aanpakken: reduc e van het probleem dat je onbeslisbaar wil
bewijzen. Je neemt aan dat het probleem wel beslisbaar is, en bewijs de tegenspraak.
H/1 betekent 1 input
Begrippen in berekenbaarheidstheorie:
- Berekenbaar computable (func e)
- Opsombaar enumerable (verzameling)
- Complementair opsombaar
- Beslisbaar decidable (verzameling)
- Semi-beslisbaar
Een (mogelijk par ële) func e f: N -> N heet berekenbaar als er een computerprogramma
bestaat dat f kan berekenen voor precies alle getallen waarvoor f gede nieerd is.
Een verzameling getallen heet opsombaar/enumereerbaar als er een computerprogramma
bestaat dat alle elementen van X (vroeg of laat) afdrukt.
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 diede26. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €9,69. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 66579 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen
