Store ideer i Computer Science and Engineering

Original: http://www.seas.upenn.edu/~andre/general/computer_science.html

André Dehon
Startet: 31 juli 1999
Seneste opdatering: August 21, 1999

[Et par ord om min hensigt med at indsamle disse ideer]

Mekaniske procedurer for at finde løsninger på problemer. Det er, for mange spørgsmål / problemer, kan vi skrive ned en række trin og simple prædikater som definerer præcis, hvordan at finde den rigtige løsning. Denne proces er helt mekanisk, som ikke kræver nogen “menneskelige” dom at fuldføre.
Vi kan bygge fysiske maskiner, der gennemfører disse procedurer og udføre beregningerne for os.
Der er enkle og universelle modeller af computing som fange de grundlæggende funktioner i disse maskiner (fx automater, pushdown automater, Turing-maskiner).
Turing Machine model er “robust” i den forstand, at “fornuftige” tilføjelser til det, eller alternative formuleringer af edb-modeller har den samme asymptotiske magt beregnelighed (Kirkens speciale).
“rimelige” betyder, at de, for det meste, svarer til ting, vi forestille os en reel maskine kunne støtte. Især er der stærkere modeller, når maskinen får lov til at gøre “urimelig” ting som konsultere et orakel.
Deterministiske / garanteret procedurer findes ikke på alle problemer (Stop Problem, uncomputability). En vigtig del af CS teori er at klassificere problemer som beregnelige eller uncomputable.
Af de problemer, der er beregnelige, opgaver har forskellige beregningsmæssige vanskeligheder (kompleksitet). Et andet vigtigt element i CS teori giver os mulighed for at analysere algoritmer og vurdere deres kompleksitet. (kompleksitetsklasser [P, NP, PSPACE, IP, …] orden analyse [O (), Omega (), Theta ()])
teknikker til analyse af worst-case kompleksiteten af ​​særlige algoritmer
teknikker til analyse forventes case kompleksitet
teknikker til “beviser” grænser på kompleksiteten af en beregning (nedskæringer)
klassificering af et væld af velkendte problemstillinger arketyper
kendte gode algoritmer for velkendte problem arketyper
fælles idiomer / løsningsmetoder (fx del-og-hersk, lineær programmering, dynamisk programmering, grafalgoritmer)
Der er alternativer til direkte at løse vanskelige problemer optimalt. CS teori også fortæller os, hvad vi kan give op i garantien opløsning kvalitet for at reducere beregningsmæssige kompleksitet.
approksimationsalgoritmer – kan finde løsning på kortere tid, inden nogle bundet af den optimale løsning
online algoritmer – konsekvenserne af at modtage problem oplysninger trinvist i stedet for alle på én gang
polynomiel heuristiske løsninger – algoritmer med kortere runtime som ikke nødvendigvis vil finde den optimale løsning
randomiserede algoritmer – algoritmer der finde en løsning på et givet tidspunkt kompleksitet inden for en bestemt grænse for optimal eller med en vis sandsynlighed for at være korrekte. (omfatter simuleret annealing)
Kontrol af, om du har et gyldigt (acceptabel) løsning er typisk meget nemmere end computing selve løsningen.
Når det ikke er klart, hvordan man deterministisk finde en god (eller optimalt) løsning, dette faktum, at kontrol er moderat let giver os mulighed for at finde en god løsning ved at generere kandidater, og teste for gyldighed. En vigtig komponent i CS kunst og praksis er, hvordan man bedst “søg” et rum af løsninger.
branch-and-bound
beskæring (videnbaseret, induktion)
bestilling heuristik – (her heuristisk er tid optimering)
alpha-beta-søgning
Kompleksiteten af ​​beregninger kan bruges til godkendelse og privatliv. Det vil sige, vi kan vælge beregninger til at indkode / afkode data, der er “medgørlig”, når alle oplysninger er tilgængelige, men untractable når der mangler vigtige oplysninger.
Beregninger kan fordeles blandt mange kommunikerende agenter, ofte reducerer den nødvendige tid til at beregne et resultat.
form af parallelitet tidskurven
grænser for parallelizability
teknikker til parallelisering (tænker og styring parallelitet)
pipeline / samlebånd (stream)
CSP / coroutines
dataflow (herunder regneark)
SPMD / vektor
flertrådede
funktionelle enheder (VLIW)
BSP (grovkornet, barriere synkronisering)
synligt atomare
sekventielle semantik med spekulative samtidighed
antage får ingen afhængigheder, eller kan forudsige de ændringer, der vil blive foretaget af “tidligere” operationer, check antagelser før “begå” drift.
fx spekulative belastninger, amtmand, instruktion problem, optimistisk databasetransaktion concurrency, virtuel tid
Kommunikation mellem agenter er dyrt og er ofte en stor flaskehals begrænsende praktisk muligt parallelitet.
algoritmer / teknikker til at mindske behovet for kommunikation
kommunikation omkostninger og effekter
En simpel foranstaltning af denne meddelelse flaskehals er gennemskæring båndbredde på et netværk. Det lægger en øvre grænse på mængden af ​​data, en maskine kan overføre og dermed mængden af ​​kommunikation mulig.
Da ledninger typisk tage op finite plads, gennemskæring båndbredde indebærer også en nedre grænse på det fysiske område / ressourcer, der kræves af en maskine
netværk design
VLSI teori
Store systemer har en øget sandsynlighed for at støde på defekte komponenter. Distribuerede systemer kan sætte den kontrol og styring af ressourcer ud af hænderne på en enkelt enhed eller organisation. CS beskæftiger sig med, hvordan vi bygger pålidelige edb-systemer i lyset af upålidelige komponenter.
fejl afsløring og korrektion
defekt hukommelse
støjende / defekte kommunikation
støjende / defekte beregnings knudepunkter
Den ønskede beregning kan indfanges præcist og utvetydigt. Datalogi handler om, hvordan vi konstruerer sprog til at beskrive beregninger, og hvordan vi gør dem praktisk for human brug.
sprog
syntaks (grammatik)
semantik (denotational, operationel)
En beskrivelse, som er bekvem for brugeren, er ikke nødvendigvis effektive til implementering på en fysisk maskine.
verbose symboler og syntaks (minimere fejl)
abstraktion (skjul gennemførelse detaljer, også muligheder for optimering)
generalitet (skrevet til at håndtere almindelig (dyrere) tilfælde)
forsætlig redundans (fangstopgørelser fejl tidligt)
Vi behøver ikke at efterligne brugerens beskrivelse af en beregning til at gennemføre den korrekt. Vi er simpelthen nødt til at gennemføre en beregning, som giver den samme synlige resultat (har samme betydning), som brugerens beregning (udarbejdelse, CAD).
semantiske transformationer
anvende alle kendte oplysninger på transformation tid – efterlader kun rester af beregning ukendt data
fjerne redundans
sammenbrud på tværs af brugergrupper abstraktioner
genbestille / omformulere operation for at skræddersy til maskinomkostninger
Repræsentationen anvendes til data i en beregning kan have en stor virkning på effektiviteten i driften og lethed af den menneskelige fatteevne
virkninger på beregningsmæssige og opbevaring effektivitet (f.eks arrays og faste strukturer vs mærkede lister, rød-sorte træer; sparsomme vs tætte repræsentationer af data)
lempelse menneskelig forståelse (f.eks rige datastrukturer)
Vores fysiske verden giver os mulighed for at bygge meget store edb-systemer. Den praktiske grænse for anvendelige størrelse af et edb-system (eller i det mindste, størrelsen af ​​den funktion effektivt understøttes af et edb-system) er næsten altid menneskelig forståelse, ikke den fysiske kapacitet, der kræves. Derfor er et vigtigt anliggende for datalogi teknikker til at styre og reducere kompleksitet.
abstraktioner / oplysning skjule
modularitet
Problemet nedbrydning hierarki
komponent isolation
invarianter
fælles idiomer / paradigmer for organisationen (f.eks procedurer, rammer, vandløb, objekter, API’er, servere)
En computing maskine kan implementeres af X.
X = mekaniske interaktioner, relæer, rør, transistorer, DNA, molekyler …
fælles / nyttige abstraktioner (fx digital abstraktion, flops, hukommelse, kommunikationskanaler)
discipliner opnår korrekthed over for støj / usikkerhed (f.eks spændingsniveauer, timing modeller og discipliner)
Vi kan udvide vores opfattelse af abstraktion / oplysning gemmer til maskinens design. Især maskinkode og driftsmiljø for en maskine repræsenterer abstrakt grænseflade det giver til omverdenen. Enhver implementering, som giver de samme semantik til maskinen kode er levedygtig.
Derfor har vi begrebet ISA eller arkitektur familier, der alle kører samme maskinkode, men som indrømmer, at en række implementeringer (f.eks IBM 360, VAX, MIPS, SPARC, x86).
forskellig implementering kan være billigere / langsommere versus dyrere / hurtigere
implementeringer kan udvikle sig til at udnytte ny teknologi uden at ændre interfacet (maskinen kode)
Machine kode er bare et andet sprog med angivelse netop beregning, der skal udføres.
en beregningsmæssige motor behøver kun give de tilsigtede semantik, der forlader det masser af frihed med hensyn til, hvordan den gennemfører semantik.
ligesom ethvert andet sprog, kan det oversættes fra input format til et andet native format (måske en anden maskines native maskine format), så længe det giver de oprindelige semantik (f.eks softPC, binær oversættelse)
Ingeniørpraktikken side af datalogi handler om: Hvordan vi minimere de ressourcer, vi bruger for at udføre en beregning (sæt af beregninger).
minimere: tid, energi, areal (hardware: hukommelse, ledninger, beregne)
Fysiske maskiner har finite / begrænsede reelle ressourcer.
Typisk kan tilstanden af ​​en fysisk ressource lagres i hukommelsen mere kompakt (i færre fysiske ressourcer) end den fysiske ressource selv. (dette er en pragmatisk bemærkning om typiske implementering teknologier i fælles brug.)
Vi kan levere indvinding af flere fysiske ressourcer ved at virtualisere de fysiske ressourcer. Det vil sige, at dele den fysisk ressource blandt flere anvendelser over tid. For at opnå dette, gemmer vi tilstanden af ​​en bestemt anvendelse af de fysiske ressourcer i billigere opbevaring.
fx virtuel hukommelse, virtuelle kanaler, multitasking, time-sharing
Typisk abstraktion nemmeste for en bruger til at ræsonnere om, er, at der findes “uendelige” virtuelle ressourcer (dvs. almindelig aforisme er, at arkitekturer burde have 0, 1, eller et uendeligt antal af en bestemt ressource type)
Pragmatisk, da vi skal spare staten for hver virtuel eksempel er vi begrænset af endelighed af den fysiske hukommelse lagermediet holde staten. (Dette er naturligvis, er også den måde, som vores fysiske maskiner ikke virkelig være så stærke som Turing-maskiner.)
Forskellige logiske opgaver, der kører på den samme hardware kan isoleres fra hinanden. (fx virtuel hukommelse, proces isolation)
Usikkerhed eller variationer i køretiden for dele af samtidige (eller næsten samtidige) opgaver kan føre til forskellige sekvenser af hændelser for det samme program (og i nogle tilfælde endda det samme datainput). dvs detaljeret operationel adfærd er ikke praecise.
kilder til ikke-determinisme: fx
variabel responstid på grund af variabel belastning fra andre opgaver dele nogle / eller alle de nødvendige ressourcer
variabel interleaving / planlægning af aktivering på grund af planlægning politik, historie i planlægningsprocessen, eller endda bevidst tilfældighed i planlægning beslutninger
data afhængig køre tider for dele af opgaven
variabel latens af drift på grund af statslige / historie effekter (fx caching, personsøgning)
non-determinisme kan være svært at håndtere og styre kompleksiteten, så ofte det er en effekt, vi forsøger at minimere eller eliminere.
programmering konstruktioner, vagter, invarianter, der gør ikke-determineret planlægning usynlig for den funktionelle opførsel af programmer.
Specialized procedure / maskine kan generelt være billigere / hurtigere end almindelig maskine. dvs tidligt bundet data / oplysninger kan foldes ind i formuleringen af ​​udregning til at reducere nødvendige arbejde.
der er plads til at kortlægge en nyttig teori og grundlæggende principper her.
mange pragmatiske eksempler på
specielle formål versus generelle formål hardware, komponenter
særlige tilfælde optimeringer
partiel evaluering / program specialisering
run-time kodegenerering (fx syntese)
arbejdshypotese: omkostninger implementering er en funktion af kendte oplysninger og indfødte kompleksitet
Beregninger opstår på forskellige tidsskalaer (satser). For at minimere arbejde, når det er muligt, hejser en beregning ud fra en høj regionen i et langsommere region.
trivielt eksempel: loop invarianter / hejse
bindende identificere og udnytte tid
kompilering vs fortolkning; dvs tage tid op foran at beregne mere effektive beregningsmæssige rest til at udføre under kørslen
install-tid, run-time specialisering
De data, vi har brug for at gemme eller overføre kun behøver at stå i forhold til indholdet af oplysningerne.
kompression (minimere lagring / transmission) -> informationsteori
Der er beregning involveret i kompression / dekompression, så der er normalt en afvejning mellem beregningsmæssige omkostninger og oplagring / transmissionsomkostninger.
De problemer, vi typisk ser, indeholde struktur. At udnytte denne struktur giver os mulighed for at bygge billigere (typisk tilfælde) byggeklodser, end vi ellers ville. fx
lokalitet i hukommelsen reference (tid og rum) -> caching
lokalitet i kommunikation -> Leje Rule (grænse nødvendig gennemskæring båndbredde)
fælles deludtryk -> multi-level logik, udnytte struktur
Sættet af begivenheder eller sager, hvor en beregning eller delsystem håndtag er ofte meget lokal. Typisk eller gennemsnitlig tilfælde kan forbedres betydeligt ved at udnytte denne lokalisering.
Alternativt kan en god gennemsnitlige tilfælde ydeevne opretholdes på betydeligt lavere omkostninger.
Aforisme: gøre fælles sag hurtigt (hurtig sag almindelig)
Worst-case ydeevne kan lide som en konsekvens, så sådanne optimeringer kan være uhensigtsmæssigt, når garanteret / afgrænset ydeevne er påkrævet for alle tilfælde.
I nogle tilfælde det værst tænkelige adfærd en algoritme eller et problem instans for en maskine kan undgås (med meget høj sandsynlighed) ved at tilføje forsætlig randomisering. Dette giver os mulighed for at vende worst-case scenarier i gennemsnit case-scenarier. (f.eks bedste eksempler er i routing og prøv scenarier for networking. Enhver deterministisk algoritme ville have dårlig worst case (hot-spot) ydeevne, hvorimod randomisering kan undgå dette problem uden at kræve global viden om systemets tilstand.)
Feedback er nøglen til at diagnosticere uoverensstemmelser mellem en model af verden og virkeligheden. Dette er egentlig bare hjertet af den videnskabelige metode. Det skal bruges af udviklere til at forbedre programmer (debug funktionelle problemer, identificere og forbedre performance problemer). Desuden kan det være indlejret i programmer, så de tilpasser sig til deres data og miljø.
A-systemer er bygget af et fast sæt af ressourcer af forskellige typer skal give dem i et fast forhold. Men opgaver kræver ofte ressourcer i forskellige proportioner. Derfor vil nogle ressourcer nødvendigvis gå underudnyttet eller spildt. Det trick er normalt at sørge for, at de dyreste ressource udnyttes effektivt.
En datastruktur eller beregning kan enten være dynamisk eller statisk.
Faste strukturer og beregninger kan være meget effektiv, når størrelsen og formen af beregningen er konstant eller har ringe varians.
Dynamiske strukturer / beregninger er nødvendige, når størrelse eller omfang af problemet er ubegrænset. De koster mere per element eller element, men de har kun at være så stort (som kompleks) som et særligt problem f.eks.
mere …
Aforisme: systemer kan gøres mere generelt ved tilsætning af et niveau af indirektion; dette unbounds det sæt af ting, der kan gøres, men tilføjer en omkostning for indirection.