Kapitel 1 upprinelsen
Hur beskriver Janlert datavetenskap?
Studiet av beräkningar och beräkningsmekanismer.
Ge tre vitt skilda exempel på symbolsystem.
Aritmetiska uttryck, musiknoter, svenska språket, morsekod
Vilka komponenter består von Neumann-arkitekturen av och hur är de relaterade? Illustrera med en figur.
rita
En Turingmaskin är en extremt primitiv beräkningsmekanism. Vad var Turings syfte med att definiera en sådan klen konstruktion?
Att göra det lättare att matematiskt analysera maskinerna och deras kapacitet.
Beskriv det berömda “stopproblemet”
Att/om en exekvering(alogritm) kommer att uppfylla termineringskravet. Enligt Turings uppsats från 1936 så bevisades att det inte finns någon äkta algoritm som kan avgöra frågan om en given algoritm med givna indata kommer att terminera eller inte. Detta är då en icke beräkningsbar uppgift.
Varför anses Alan Turing (1912–1954) vara en av pionjärerna inom datavetenskapen?
Alan skrev den banbrytande artikeln “Computing machinery and intelligence” år 1936 där han bevisade att det fanns icke beräkningsbara problem och la grunden till den moderna datorn med Turingmaskinen.
Janlert menar att en beräkning har två väsentliga egenskaper. Vilka?
Den använder symboler.
Symbolerna manipuleras formellt genom formella procedurer.
Vad menar Janlert med att en processor bör vara generell och ett program bör vara portabelt?
En processor ska kunna exekvera flera olika program. Programmet kan bytas ut eller ändras men processorn kommer att förbli densamma.
Att ett program ska vara portabelt innebär att det kan exekveras av flera olika processorer, det kan förflyttas mellan flera olika maskiner.
Återge Church–Turings tes
Allt som effektivt kan beräknas kan beräknas av någon turingmaskin.
Vad måste ske för att ett beräkningsproblem som idag är ohanterbart ska bli hanterbart?
Hitta bättre algoritm
Formulera om problemet, modifiera uppgiften
Bygga snabbare dator
Vad kännetecknar det framväxande postindustriella samhället?
Det är ett samhälle som kännetecknas av information, idéer, kunskap och kommunikation. De flesta idag är “knowledge workers” istället för att jobba i fabriker.
Hur skiljer Janlert på begreppen data och information?
Data = syntaktiska nivån, (rå data)
Information = semantiska nivån, (tolkning utav data)
Tjetitje är data, tjetitje äpplen är information (Äpplen finns inte om inte tjetitje finns).
Vad menar Janlert med datorn är en universell symbolmaskin?
Det visar sig att med en mycket begränsad uppsättning av elementära symboliska
mekanismer, kan man i princip åstadkomma vilket symboliskt samband som helst.
Vad menas med en universell Turingmaskin?
Den har en möjlighet att interagera med sin egen symbolmanipulerande verksamhet. Den kan placera symboler på bandet, och dessa symboler kan senare komma att påverka maskinens fortsatta beteende.
Vad säger en algoritms tidskomplexitet om algoritmen?
Hur lång tid det tar innan algoritmen terminerar
Vilken roll spelade andra världskriget (och det efterföljande kalla kriget) för datavetenskapens upprinnelse?
De samlade många av världens ledande forskare och gav dom ett enormt kapital. De började med ett militärt ändamål, eftersom det fanns ett behov att göra mycket beräkningar särskilt angående hur man ska skicka missiler, men det spillde över på civila ändamål och la grunden för modern datavetenskap.
Förklara varför ett digitalt symbolsystem är mindre störningskänsligt än ett analogt. Illustrera med ett exempel.
Datan är otvetydig, alltså exakt och bestämd i ett digitalt symbolsystem. Därför är det mindre störningskänsligt än något analogt (som inte har bestämd, exakt och otvetydig data).
Vilka är de tre huvudsakliga programmeringsparadigmerna?
Ïmperativa språk: Dataobjekten bearbetas och manipuleras steg för steg i kronologisk ordning -C, basic, pascal, cobol
funktionella och relationella: Använder matematiska funktioner för att beskriva symboliska samband.- lisp, APL, WL
objektorienterade och agentorienterade: Man beskriver objekten med både egenskaper och kapaciteter (metoder). - JAVA, C++
Beskriv hur en Turingmaskin är uppbyggd och fungerar. Ditt svar ska inkludera maskinens beståndsdelar, hur indata presenteras för maskinen, hur maskinen arbetar, hur maskinen terminerar, samt hur maskinen presenterar utdata.
Beståndsdelar:
Består av en centralenhet kopplad till en bandspelare. I bandspelaren finns ett band med obegränsad utsträckning både framåt och bakåt. Bandet är indelat i celler som kan lagra information av en valfri "bokstav" (symbol).
Indata:
Bandet kan betraktas som maskinens minne. När avspelningshuvudet kommer över en cell på bandet (den aktuella cellen) så läses informationen av.
Hur den arbetar:
Den arbetar på följande sätt. I varje ögonblick så befinner sig centralenheten i ett bestämt tillstånd, state, det aktuella tillståndet, ett av ett ändligt antal tillstånd. Tillståndet START är där den befinner sig vid start, och tillståndet STOP i slutet som innebär att exekveringen har stannat.
Hur den terminerar:
Den terminerar när den når tillståndet STOP. Det kan hända att den aldrig når det tillståndet och på så sätt aldrig terminerar.
Hur den presenterar utdata:
Utdata presenteras på samma band som indatan. När maskinen exekverat klart så ska sekvensen av bokstäver hanteras som utdata.
Förklara varför det finns ett uppräkneligt antal Turingmaskiner.
Turingmaskinerna är ju i vart fall inte fler än alla de uppräkneligt många textsträngar som kan bildas av den givna turingsprogramsyntaxen.
Varför började matematiker under första halvan av 1900-talet att intressera sig för mekaniserad symbolisk manipulation?
Det var kris bland matematikerna när de skulle övergå till att behöva bevisa sina beräkningar enligt formella regler. Innan dess räckte det att en matematisk auktoritet gav ett godkännande för beräkningen. Ett matematiskt bevis behövde nu kunna mekaniskt (utan insikt eller krav på förståelse) följa en strikt uppsättning härledningsregler.
Förklara utifrån symbolers mediumoberoende varför det är principiellt möjligt att bygga till exempel mekaniska, pneumatiska eller optiska datorer.
Så länge symbolerna och hur de hanteras är konstant så spelar det ingen roll hur eller av vad datorn är konstruerad.
Vad menar Janlert med att ett program orsakar det avsedda beteendet?
Det som sker mellan start och stopp av programmet är inte nödvändigtvis det avsedda beteendet, det enda som är det avsedda beteendet är det som programmet beskriver.
Det är en ändlig uppsättning regler som bestämmer en följd av operationer som löser en specifik typ av uppgift, och som har följande fem kännetecken:
Ändlighet - finiteness. Algoritmen måste kunna garanteras bli färdig efter ett ändligt antal steg (oavsett vilken indata är). Den tekniska termen är terminera.
Bestämdhet - definiteness Varje steg i algoritmen måste vara entydig och precist definerat.
Indata - input. En algoritm har noll eller flera indata, det vill säga värden som man ger algoritmen innan den startas. Andra vanliga ord för indata är argument och (in)parameter.
Utdata - output. En algoritm har ett eller flera utdata, det vill säga värden som produceras av algoritmen. Andra vanliga benämningar av utdata är resultat och utparameter.
Effektivitet - effectiveness.. Varje steg i algoritmen måste vara så elementär att det i princip kan utföras exakt, och inom en ändlig tidrymd, av en människa som arbetar med papper och penna.
Hur är det faktum att de beräkningsbara funktionerna är uppräkneligt många relaterat till begreppet “beräkningsbarhet”?
De flesta funktioner från naturliga tal till naturliga tal kan inte beräknas av någon turingmaskin och är således inte beräkningsbara.
Funktioner som är beräkningsbara kan beräknas av en turingmaskin. En turingmaskin har alltid ett ändligt tillstånd. Går att lista alla turingmaskiner på ett band, kan vara oändligt många men de är fortfarande uppräkneligt många. Till skillnad från matematiska funktioner som kan vara oändliga.