Index

Symbole

Ω -Notation, 433Θ -Notation, 433χ2-Test, 449λ -Übergang, siehe ε-Übergangμ-Operator, 429μ-rekursive Funktion, 192, 418, 428, 429, 462ε-Übergang, 3793-FÄRBBARKEIT, 4433SAT, 4434-FÄRBBARKEIT, 4432-FÄRBBARKEIT, 4432SAT, 443k-FÄRBBARKEIT, 443k-SAT, 443127-Exzess-Code, siehe Exzess-Code1G, 2G, 3G, 4G, 2833DES, 151, 1594-Farben Problem, 443

A

A∗-Algorithmus, siehe Graphsuche, A∗-AlgorithmusA/D-Wandler, 46, 115, 259Abakus, 3, 4, 12Abbrechfehler, 17Abgeschlossenheit (formale Sprachen), 400Ableitung, 404Ableitungsbaum, 410Ableitungsregel, 393Ableitungsrelation, 394Ableitungsstruktur, 394absolute Adressierung, 211Absorption, 178abstrakter Datentyp, siehe ADTAbtastfrequenz, 44Abtastrate, 44Abtasttheorem, 43

Abtastung, 43abzählbar unendlich, 389, 403, 419Access Point, 277Achtersystem, siehe OktalsystemACID, siehe Transaktion

Ackermannfunktion, 425, 428, 460Acknowledge, 286ADA, 601, 602, 631Addierwerk, 189Addition (binäre), siehe binäre Arithmetik, AdditionAddress Strobe, 196Adjazenzmatrix, siehe Graph, AdjazenzmatrixAdressbus, 14, 15, 194, 195, 199Adressierungsart, 208, 210Adressraum, 210ADSL, siehe DSLADT, 624, 659, 669Advanced Encryption Standard, siehe AESÄquivalenz, 179Äquivalenzproblem, 422, 423AES, 139, 151, 159, 274, 278, 297Aggregation, 681, 771Agil, 758AIC, 450Aiken, Howard A., 8AJAX, 733Akkumulator, 30, 202, 231AKS Primzahltest, 456Aktivitätsdiagramm, 768, 774akzeptierender Zustand, siehe Endzustandakzeptierte Sprache, 376, 387Akzeptor, 377, 387ALGOL, 9, 599, 616Algorithmierung, 416algorithmische Komprimierbarkeit, 449algorithmischer Informationsgehalt, 449Algorithmus

Analyse, siehe Analyse von AlgorithmenDefinition, 415determiniert, 415deterministisch, 415effektiv, 415, 431effizient, 415, 431handhabbarer, 430, 435, 439probabilistischer, 416, 448

stochastischer, 416tractable, siehe Algorithmus, handhabbarer

allgemeine Grammatik, 394

© Springer Fachmedien Wiesbaden 2016H. Ernst et al., Grundkurs Informatik,DOI 10.1007/978-3-658-14634-4

786 Index

allgemeine Sprache, 387, 389, 396, 409Alphabet, 37, 62, 91, 372, 376, 386, 393, 607ALU, 199, 201, 231Amdahl, Gene, 9Amdahls Gesetz, 242Amiga, 9Analog/Digital-Wandler, siehe A/D-WandlerAnalogrechner, 12Analyse von Algorithmen, 435, 439

Divide and Conquer, 437Rekursion, 436Schleifen, 436

Analytical Engine, 6AND, siehe logische Operationen, 24, 92, 99, 175,

186Andreessen, M., 708Android, 328, 670Anfangszustand, 376Anforderungsanalyse, 751Anforderungsvalidierung, 751angewandte Informatik, siehe Informatik, angewandteAnode, 169ANSI C, siehe C90Antisymmetrie, 584Antivalenz, 179Anwendungsfalldiagramm, 768Anwendungsschicht, 266Apache Cordova, 723APL, 9Apobetik, 604Apple, 9Applet, 670Arbeitsverzeichnis, 323Architekturentwurf, 752Arduino, 260Aristoteles, 4Arithmetik-Logik-Einheit, siehe ALUarithmetische Codierung, 116, 117arithmetisches Mittel, siehe MittelwertARM-Prozessor, 234ARPANET, 287Artificial Intelligence, siehe KIAS, 196ASCII, 72, 74Assembler, 9, 213, 409, 411, 597, 617Assoziation, 681, 770assoziatives Array, 693, 737Assoziativität, 178Ast, siehe Baum, Ast

asymmetrische Verschlüsselung, siehe Verschlüsse-lung, asymmetrisch

asynchrone Bussteuerung, 195Asynchronous JavaScript And XML, siehe AJAXATA-Festplatte, 249Atomarität, siehe TransaktionAttributgrammatik, 411Audio-CD, 85, 100, 111aufzählbare Sprache, siehe allgemeine Sprache, 394Ausgabefunktion, 373Ausnahme, 204, 251, 694Aussagenlogik, 177, 178Auszeichnungsbefehl, siehe Markup-TagAuthenticity, siehe AuthentizitätAuthentizität, 138, 160, 165Autoboxing, 677Automat

Darstellung, 374deterministischer, siehe deterministischer Automatendlicher, siehe endlicher Automat, determi-

nistischer Automat, nichtdeterministischerAutomat

erkennender, siehe erkennender AutomatFangzustand, siehe Fangzustandlinear beschränkter, siehe linear beschränkter

AutomatMealy-, siehe Mealy-Automatminimaler, 382mit Ausgabe, 373Moore-, siehe Moore-Automatnichtdeterministischer, siehe nichtdeterministischer

AutomatTransformation NEA–DEA, 380übersetzender, siehe übersetzender Automat

Autovektor-Interrupt, 197Average-case Laufzeit, 431AVL-Baum, 539, 541, 550, 554Aztec-Code, 106

B

B-Baum, 549, 551B+-Baum, 554BB-Baum, 554einfügen, 552Hecke, 554löschen, 553Suche, 552

Babbage, Ch., 5, 7, 602Backtracking, 464, 582

Index 787

Backus, John, 9, 598Backus-Naur Form, siehe BNF

erweiterte, siehe EBNFBad Character Heuristics, 477Bandzeichen, 386Barcode, 106bash, 322BASIC, 9, 409, 598, 603Basis (Transistor), 173Basisklasse, 687, 771Basispolynom, 99Batch-Programm, 325Bauer, F. L., 8, 747Baum, 523, 560

(a,b)-Baum, siehe Vielwegbaum, (a,b)-BaumAst, 524ausgeglichener, 537, 539AVL-, siehe AVL-BaumB-Baum, siehe B-BaumBinärbaum, siehe BinärbaumBlatt, 524gewichteter, 526Höhe, 524identisch, 524isomorph, 524Knoten, 524Nachfolger, 524Niveau, 524Nullbaum, 524spannender, 587Tiefe, 524Vater, 524Vielwegbaum, siehe VielwegbaumVorgänger, 524Wurzel, 524

baumartiger Graph, 376Bayes-Netz, 359Bayessche Erkenntnisformel, siehe Wahrscheinlich-

keit, BayesBCD, 24, 31, 71, 82, 219BCH-Codes, 99, 100, 107Beck, K., 697, 764bedingte Wahrscheinlichkeit, siehe Wahrscheinlich-

keit, bedingteBedingungscode, 222Befehlsausführung, 206Befehlsdecoder, 200Befehlsregister, 200Befehlssatz, 234Befehlszähler, 199, 200

Befehlszyklus, 200Belegungsfaktor, siehe Hashing, BelegungsfaktorBell, A. G., 7Benutzer-Modus, 204, 307, 333Berechenbarkeit, 387, 391, 395, 418, 418, 427, 428,

430Berlekamp-Massey Algorithmus, 111Berners-Lee, T., 297, 708BERR, 198Best-case Laufzeit, 431Best-Effort-Strategie, 290Betriebsart, 304Betriebsmittel, 308, 309Betriebssystemkern, siehe KernelBeziehung (1:1, 1:n, n:m), 343Binärbaum, 524, 541, 548

Adresse Nachfolger/Vorgänger (Array), 525Durchsuchen, 527

Hauptreihenfolge, siehe Binärbaum, Durchsu-chen, Preorder

Inorder, 527–529, 536, 571Nebenreihenfolge, siehe Binärbaum, Durchsu-

chen, PostorderPostorder, 527Preorder, 527, 528symmetrische Reihenfolge, siehe Binärbaum,

Durchsuchen, Inordererweiterter, 525externer Knoten, 525interner Knoten, 525Speicherung, 525, 526vollständiger, 524, 525, 541

Binärcodierung, 69, 269binäre Addition, siehe binäre Arithmetik, Additionbinäre Arithmetik, 5, 17, 24

Addition, 25

Division, 28

Gleitkommazahlen, siehe Gleitkommazahlenlogische Operationen, siehe logische OperationenMultiplikation, 28

Subtraktion, siehe binäre Arithmetik, Subtraktion(direkte), siehe Komplement

Subtraktion (direkte), 25binäre Subtraktion, siehe binäre Arithmetik,

Subtraktion (direkte), siehe Komplement,Zweier-

binäre Suche, siehe Suchverfahren, binäre Suchebinärer Suchbaum, 530

aufbauen, 531einfügen, 531

788 Index

löschen, 534sortieren, 534suchen, 531

Binärsystem, 17, 18Binary Coded Decimal, siehe BCDBinder, siehe LinkerBinomialkoeffizient, 55, 56binomischer Satz, 56Bionik, 40bison, 413Bit, 61, 65Bitübertragungsschicht, 264, 267Blatt, siehe Baum, BlattBlockcode, 70, 79, 115, 268blockorientierter Datentransfer, 510Blu-Ray, 85, 111Bluetooth, 101, 103, 274BNF, 393, 411, 607, 608, 611Booch, G., 766Boole, George, 5boolesche Algebra, 177, 179, 180, 186boolescher Körper, 91, 98, 107boolescher Raum, 91boolescher Verband, 179

Bootstrap, 718Bottom-Up Parser, 410, 609Bourne-Shell, 322Boyer-Moore, siehe Pattern Matching, Boyer-MooreBreadth First Search, siehe Graphsuche, BreitensucheBreitensuche, siehe Graphsuche, BreitensucheBridge, 265, 290Broadcast, 272, 292Bubblesort, siehe Sortierverfahren, BubblesortBucket, 484Bündelfehler, 100, 101, 107, 111Burst Error, siehe BündelfehlerBus, siehe Adressbus, siehe Datenbus, siehe

Steuerbus, 12, 15, 253, 272, 276Bus grant, 198Bus request, 198Busy Beaver, 429Busy-Wait, 314by-reference, 738by-value, 683, 726, 738Bytecode, 309, 670

C

C, 9, 598, 600, 604, 616#define, 619

#else, 621#endif, 621#error, 620#if, 621#ifdef, 621#include, 619, 637#pragma, 620#undef, 620ANSI, siehe C90argc, argv, 637, 648Array, siehe C, FelderAusdrücke, 629auto, 641Block, 632break, 635case, 631, 635cast, siehe C, Typumwandlungenconst, 622continue, 635Dateien, 642Datentypen, 621, 626default, 636Dekrement, 629dynamische Speicherverwaltung, 651Elemente, 617enum, 624extern, 640, 641fclose, 643Felder, 626, 647, 648fgetc, 643fgetchar, 643fopen, 642for, 634, 635fputc, 643fputchar, 643free, 651fseek, 643fsetpos, 643Funktionen, 636, 637, 640, 651goto, 633, 635Gültigkeit (Variablen), 639Header, 637if, 631, 633Inkrement, 629Kommentare, 618Konditionalausdrücke, 631, 633Konstanten, 622main, 619, 636, 637, 648Makro, 620malloc, 651

Index 789

Nachteile, 617Namen, 618Operatoren, 629Parameter (Funktion), 636, 648Präprozessor, 619, 620printf, 641register, 641return, 635, 636rewind, 643scanf, 641sizeof, 631Sprungbefehle, 635static, 632, 640stdin, 643stdout, 643strcmp, 644strcpy, 644Strings, 643strlen, 644strncat, 644struct, 627switch, 631, 635Typecast, siehe C, Typumwandlungentypedef, 624Typumwandlung, 631Variablen, 622

Gültigkeit, siehe C, Gültigkeit (Variablen)globale, 640lokale, 640

void, 623volatile, 622Vorteile, 617while, 633, 635Zeichenketten, siehe C, StringsZeiger, 623, 645, 647, 648, 651Zeigerarithmetik, 647Zuweisung, 629

C++, 601, 626C11, 616C90, 616, 618, 624, 639, 640C95, 616C99, 616, 640C#, 601, 721CA-IDMS, 339Cache, 208, 247Cäsar-Code, 140, 141CAN, 15, 101, 103Carmichael-Zahl, 457, 458Carry, 30, 188, 203Cascading Style Sheet, siehe CSS

CCR, 203CDMA, siehe CodemultiplexCentral Processing Unit, siehe CPUCerf, V., 287Certification Authority, 165CGI, 719Chen, P., 339Chi-Quadrat-Test, 449Chomsky, 377, 385, 389, 390, 396

-Grammatik, 394-Hierarchie, 394, 400, 423-Normalform, 406, 407Typ 0 Grammatik, siehe allgemeine GrammatikTyp 0 Sprache, siehe allgemeine SpracheTyp 1 Grammatik, siehe kontextsensitive

GrammatikTyp 1 Sprache, siehe kontextsensitive SpracheTyp 2 Grammatik, siehe kontextfreie GrammatikTyp 2 Sprache, siehe kontextfreie SpracheTyp 3 Grammatik, siehe reguläre GrammatikTyp 3 Sprache, siehe reguläre Sprache

Chomsky, Noam, 394Church, A., 418, 702Church-Turing These, 387, 395, 417, 418, 425, 429CIDR, 291Circuit Switching, siehe LeitungsvermittlungCISC, 234Classpath, 684CLI, 322Client-Server, 293, 707, 719CLK, 194Clojure, 671Closure, 727CLR, 309Cluster, 245, 302, 512CNF, siehe Chomsky-Normalformco-NP, 446COBOL, 9, 598, 599, 617CODASYL-Komitee, 339Codd, E. F., 340, 341Code

perfekter, siehe perfekter Codezyklischer, siehe zyklischer Code

Code-Polynom, 98, 101Code-Redundanz, siehe RedundanzCodebaum, 75, 473Codegenerator, 410Codemultiplex, 271, 285Codierer, 37Codierung, 69

790 Index

Command Line Interface, siehe CLICommodore, 9Common Gateway Interface, siehe CGICommon Language Runtime, siehe CLRCompiler, 378, 409, 428, 597

Code-Optimierung, 411Tools, siehe flex, bison

Compiler-Compiler, 409Complex Instruction Set Computer, siehe CISCComputational Method, 415Computer

Analog-, siehe AnalogrechnerDigital-, siehe Digitalrechnerelektromechanische, 7Generationen, 7Röhren-, 8Transistoren-, 9

Computer Science (Def.), 1Condition Code Register, 203Confidentiality, 138Connection Machine, 10Cook, S., 442Cookie, 742Core i7-Prozessor, 237, 248CP/M, 9, 328CPU, 9, 12–14, 169, 194, 199, 230, 234Cray, 9, 10CRC-Code, 100, 106, 286Cross-Compiler, 409Crossbar Switch, siehe KreuzschienenverteilerCSMA/CA, 278CSMA/CD, 277CSS, 715

Farben, 716Maßangaben, 717Selektoren, 716

Cyclic Redundancy Check, siehe CRCCYK-Parser, 406, 407, 410

D

D-Flip-Flop, 191DAG, 585Dahl, J.O., 667Dalvik, 328DARPA, 287Data Definition Language, siehe DDLData Encryption Standard, siehe DESData Manipulation Language, siehe DMLData Mining, 52, 358

Data Transfer Acknowledge, 196Data Warehouse, 356DataMatrix-Code, 106Datei, 320Dateiverwaltung, 320Datenübertragung, 267Datenbank-Cursor, 744Datenbankmanagement-System, siehe DBMSDatenbankschema, 348Datenbus, 13, 15, 194, 195, 199Datenfernübertragung, siehe DFÜDatenkompression, 80, 82, 115, 116, 118, 120, 123,

512verlustbehaftet, 115, 122, 128verlustfrei, 115

Datenmodellierung, 338Datenobjekt, 655Datenstruktur, 655DBMS, 337DCT, 130, 131, 133DDL, 348DDR-SDRAM, 246de Morgansche Gesetze, 178DEA, siehe deterministischer AutomatDeadlock, 316, 356, 700Debugging, 410Decode, 206Decoder, 186Decodierer, 37deklarative Sprache, 348, 598, 600, 702Dekomposition, 752, 767DENIC, 288, 294denormalisierte Zahl, siehe Gleitkommazahlen,

denormalisiertDepth First Search, siehe Graphsuche, TiefensucheDES, 139, 150, 151, 159, 296DES-Challenge, 151Desktop, siehe SchreibtischmetapherDestruktor, 682, 740deterministisch kontextfreie Sprache, siehe LR(k)

Sprache, 396, 410deterministische Turing-Maschine, siehe Turing-

Maschine, deterministischedeterministischer Automat, 372, 372, 376, 380Dezimalsystem, 17DFT, 108, 128, 131DFÜ, 281Dialogbetrieb, 304Difference Engine, 6Differenz-Codierung, 120, 122

Index 791

Diffie-Hellman Schlüsseltausch, 153, 156

Digital Subscriber Line, siehe DSLdigitale Unterschrift, 165Digitaler Signalprozessor, siehe DSPDigitalisierung, 43, 46Digitalrechner, 12Digraph, siehe Graph, gerichteterDijkstra, siehe Graphsuche, DijkstraDijkstra, E., 315, 606, 654Dimensionstabelle, 357DIN 40700, 175Diode, 172, 173Direct Memory Access, siehe DMADirected Acyclic Graph, siehe DAGdirekte Adressierung, 210disjunktive Normalform, 181diskrete Exponentiation, 159diskreter Logarithmus, 159Diskretisierung, 43Distributivgesetz, 178Divide and Conquer, 437, 461, 471, 503, 668, 765Division, 346Division (binäre), siehe binäre Arithmetik, DivisionDMA, 198, 252DML, 350DMZ, 289DNS, 294Document Type Defintion, siehe DTDDokumentorientierte Datenbank, 353DOM, 714, 730Domain Name System, siehe DNSDomain Object Model, siehe DOMDPDA, siehe Kellerautomat, deterministischerDRAM, 246Drill Down, 358DSL, 282DSP, 260DTACK, 196, 197DTD, 365Dualsystem, siehe BinärsystemDuplex, 272Durchbruchspannung, 173, 251Durchlassspannung, 172dyadisches Polynom, 101Dynamic Random Access Memory, siehe DRAMdynamische Typisierung, 724, 735dynamisches Binden, 689, 772

E

EAN, 104

EBCDIC-Zeichensatz, 266EBNF, 411, 608

Echtzeit-Betrieb, 305, 601Eckert, P., 8ECMAScript, siehe JavaScriptECU, 227Edge, siehe Graph, KanteEDGE, 284Edison, T. A., 7EEPROM, 250effektive Adresse, 210Effektor, 39effizient lösbar, 440effizient prüfbar, 440Einerkomplement, siehe Komplement, Einer-Einerrücklauf, siehe Komplement, EinerrücklaufEingabealphabet, 384Eingabevalidierung, 720eingebettetes SQL, 352eingebettetes System, 15, 16, 227, 259, 301, 409Einprozessor-System, 229Einwegfunktion, 159EKONS, 104El Gamal, 159Electronic Control Unit, siehe ECUelektromechanische Rechenmaschinen, 7Embedded System, siehe eingebettetes SystemEmitter, 173Emitterschaltung, 173, 174endlicher Automat, 186, 372, 384, 385, 396, 400,

404, 410, 412, 475endlicher Körper, 98, 99, 107, 151

Inverse, siehe modulare InverseEndzustand, 376, 385ENIAC, 8, 10, 230Enigma, 143, 144, 148Entity-Relationship-Modell, 338, 765Entropie, 42, 62, 63, 66, 70, 75

maximale, 63, 71physikalische, 64, 66

Entscheidbarkeit, 418, 423Entscheidungsbaum, 361Entscheidungsproblem, 440Entscheidungspunkt, 761Entscheidungstabelle, 780Entscheidungsunterstützungs-System, 356Erfüllbarkeitsproblem, 442erkennender Automat, 377ERP-Software, 670Ersetzungsregel, 393

792 Index

erweiterter euklidischer Algorithmus, sieheeuklidischer Algorithmus, erweiterter

Ethernet, 101, 103, 276ETL, 356euklidischer Algorithmus, siehe ggTeuklidischer Algorithmus, erweiterter, 147Euler, L., 560Euler, Satz von, 147, 161eulersche Phi-Funktion, 144, 145, 147, 158, 161Eulerscher Kreis, siehe Graph, Eulerscher KreisEVA-Prinzip, 12, 415Exception, siehe AusnahmeExecute, 206exklusiv Oder, siehe XOREXPSPACE, 447EXPTIME, 446Extended Style Sheet Language, siehe XSLeXtensible Markup Language, siehe XMLExtract Transform Load, siehe ETLeXtreme Programming, 758, siehe XPExzess-Code, 31

F

Faktentabelle, 357Fakultät, 55, 427, 428, 436, 459, 461, 462, 638Falltürfunktion, 159, 161Fangzustand, 377Fano, R., 79Fano-Algorithmus, 79, 80Fano-Bedingung, 79Fast Ethernet, 268, 276FDM, siehe FrequenzmultiplexFechnersches Gesetz, 39Fehlererkennung, 83, 85, 100, 107, 269Fehlerkorrektur, 83, 85, 98–100, 107, 111Fehlerpolynom, 101Fermat Test, 456Fermat, Satz von, 147, 457Festkommazahlen, 30Festplatte, 249, 320Fetch, 206FFT, 108, 128, 129, 434, 437Fielding, R., 297FIFO, siehe QueueFile, 506

elementare Operationen, 507Grundoperationen, 508Indextabelle, 507indiziertes, 507

mehrstufig, 506segmentiertes, 507

find, 324Firewall, 289Flachbandkabel, 253Flag, 30Flash-Speicher, 250flex, 413FlexRay, 101Fließband-System, 229Fließband-Konflikt, 238Fließbandverarbeitung, 238Flip-Flop, 190–192, 246Floating-Gate, 251FLOPS, 14Floyd-Warshall-Algorithmus, siehe Graph,

Floyd-Warshall-AlgorithmusFlussdiagramm, 776Flynnsche Klassifikation, 236Font, 717formale Sprache, siehe Sprache, 393

FORTH, 527, 602FORTRAN, 9, 598, 599, 604, 617Fourier

-Transformation, 128, 129diskrete, siehe DFT, FFT

Integral, 43fraktale Bildkompression, 133Framework, 669Fredkin-Gatter, 66Fremdschlüssel, 342Frequenzmultiplex, 271Frequenzraum, 128ftp, 296, 325funktionale Sprache, 600Funktionscode, 194, 197Funkübertragung, 267, 277, 278

G

Gamma, E., 697Garbage Collection, 682Gates, Bill, 9Gateway, 290GB, 14GByte, 14Geheimnisprinzip, 668, 770Gehirn, 40Generalisierung, 668, 771Generatormatrix, 96

Index 793

Generatorpolynom, 99, 101Genetik, 40genetischer Code, 40–42Gerätetreiber, 307, 320gerichteter Graph, 375gestreute Speicherung, siehe HashingGET-Request, 297, 719, 721gewichtetes arithmetisches Mittel, 54, 70GFLOPS, siehe FLOPSggT, 144, 145, 146, 147, 161, 427, 459GiB, 14Gibibyte, 14GIF, 123Gigabit Ethernet, 276Gleichverteilung, 449Gleitkommazahlen, 8, 24, 30, 31, 118, 411

Assoziativität, 33Aufbau, 31Basis, 30, 31Bias, 31Charakteristik, 31denormalisierte, 32, 33dezimale, 31, 71Distributivität, 33Exponent, 30, 31Exzess-Code, siehe Exzess-CodeHidden Bit, 31INF, 33Mantisse, 30, 31NaN, 33negative Null, 33Normalform, 30Not a Number, 33Null, 33Overflow, 34positive Null, 33Rechenregeln, 33Underflow, 33Unendlich, 33Verteilung, 32Vorzeichenbit, 31

Gleitpunktzahlen, siehe GleitkommazahlenGND, 194GNOME, 327Gödel, K., 417Goldberg, A., 667Good Suffix Heuristics, 477Google, 328Gosling, J., 667GOTO-Programm, 418, 425, 426, 428

GPG, 164GPRS, 284GPU, 228, 260größter gemeinsamer Teiler, siehe ggTGrammatik, 393

allgemeine, siehe allgemeine Grammatikkontextfreie, siehe kontextfreie Grammatikkontextsensitive, siehe kontextsensitive Grammatikmonotone, siehe monotone Grammatikreguläre, siehe reguläre Grammatiksackgassenfrei, 404Typ 0, siehe allgemeine GrammatikTyp 1, siehe kontextsensitive Grammatik,

monotone GrammatikTyp 2, siehe kontextfreie GrammatikTyp 3, siehe reguläre Grammatik

Graph, 560adjazent, 560Adjazenzmatrix, 564, 565, 567, 568Ausgangsgrad, 563azyklisch, 565Baum, siehe Baum, 562bewerteter, 562DAG, siehe DAGDigraph, siehe Graph, gerichteterDurchsuchen, siehe Graphsuche, 571eben, siehe Graph, planarEdge, siehe Graph, KanteEinfügen von Kanten, 571Einfügen von Knoten, 570Eingangsgrad, 563endlicher, 561Erreichbarkeitsmatrix, 565, 567Eulerscher Kreis, 564Floyd-Warshall-Algorithmus, 567Forward Star, 568gerichteter, 562, 585gewichteter, 562, 576Grad, 561Hamiltonscher Kreis, 564isolierter Knoten, 561isomorph, 562kanonisches Element, 591Kante, 560Kantenfolge, 561Knoten, 560Kreis, 561Kruskal, 588, 591Löschen von Kanten, 571Löschen von Knoten, 571

794 Index

Mehrfachkante, 561parallele Kante, 561Pfad, 561Pfeil, 562planar, 562Prim-Jarník-Algorithmus, 588schlichter, 562Schlinge, 561Spannbaum, 587, 591Speicherung, 564, 568Suchen von Kanten, 570Suchen von Knoten, 570topologische Sortierung, 584transitive Hülle, 566Union-Find, 591Vertex, siehe Graph, Knotenvollständig, 561Wald, 562, 589, 591Weg, 561, 564, 566, 567, 574, 577, 579, 581Wegematrix, 565zusammenhängend, 561, 563Zyklus, 561

Graphdatenbank, 353Graphfärbung, 443Graphical User Interface, siehe GUIGraphsuche

A∗-Algorithmus, 579, 582Algorithmus von Trémaux, 582Breadth First Search, siehe Graphsuche,

BreitensucheBreitensuche, 574Depth First Search, siehe Graphsuche, TiefensucheDijkstra, 577, 579Evaluierungsfunktion, 579Greedy, 579heuristische Funktion, 579IDA∗, 580informierte, 579Labyrinth, 581monotone Heuristik, 579optimal-effizient, 580optimistische Heuristik, 579Tiefensuche, 571uniforme Kosten Suche, 576, 579uninformierte, 579

Gray-Codes, 89, 90Greedy-Verfahren

Graphsuche, 579Kruskal, 588Levenshtein-Distanz, 480

grep, 324Groovy, 671GSM, 283GUI, 326, 719Gutmans, A., 734Guttag, J., 669

H

Hahn, Philipp Matthäus, 4Halbaddierer, 188Halbduplex, 272Halbleiter, 171Halbordnung, 584HALT, 198Halteproblem, 420–422, 430, 446, 462

allgemeines, 422leeres Band, 422spezielles, 420

Haltezustand, 386Hamiltonscher Kreis, siehe Graph, Hamiltonscher

KreisHamming, R. W., 82Hamming-Abstand, siehe Hamming-DistanzHamming-Codes, 94, 97, 100, 103Hamming-Distanz, 82, 83–85, 89, 92, 93, 111Hardware-Abstraktionsschicht, 305harmonische Reihe, 488Hash-Funktionen, 480, 481

Mittenquadratmethode, 481Modulo-Berechnung, 481Zerlegungsmethode, 481

Hashing, 126, 159, 166, 480

Belegungsfaktor, 482, 485, 489doppeltes, 483Klumpenbildung, 483Kollision, 480, 482Komplexität, 487lineare Kollisionsauflösung, 483quadratische Kollisionsauflösung, 483verkettete Listen, 484

Hauptpolynom, 99Heap, 309, 526, 541, 550

einfügen, 542löschen, 542Max-Heap, 541Min-Heap, 541Speicherung, 542

Heap (Halde), 651Heapsort, siehe Sortierverfahren, Heapsort

Index 795

Hecke, 554Hennessy, J., 235Hewlett-Packard, siehe HPHexadezimalsystem, 17, 18, 18, 622Hibernate, 352Hierarchisches DBMS, 339Hilbert, D., 417Hoare, C. A. R., 500, 599, 654höhere Programmiersprache, 597Hollerith, Hermann, 5Hopper, Grace, 9, 599Horner-Schema, 20, 21, 108, 434HP, 9HSPA, 285HTML, 601, 708

Anker, 712DOM, siehe DOMFormular, 719Hyperlink, 712JavaScript, 722PHP, 722Tabelle, 711

HTTP, 297, 708HTTPS, 298Hub, 265Huffman, David A., 75Huffman-Algorithmus, 75, 79, 80, 82, 115, 116, 119,

123, 133Huffman-Baum, 526Hybridrechner, 12Hyper-V, 332hypergeometrische Verteilung, 59Hyperlink, 708, 712Hypertext, 708Hypertext Transfer Protocol, siehe HTTPHyperthreading, siehe Simultanes Multi-ThreadingHypervisor, 330, 331Hyperwürfel, 93, 258

I

IBAN, 105IBM, 9IBM System/360, 234IBM-IMS, 339IBM-PC, 253, 328ICANN, 288, 294IDA∗, siehe Graphsuche, IDA∗Idempotenz, 178IEC 60617-12, 175

IEEE 1394-Bus, 254IEEE 754, siehe GleitkommazahlenIEEE 802.11, siehe WLANIEEE 802.3, siehe EthernetIMAP, 295immutable, 677imperative Sprache, 598Implikation, 179indirekte Adressierung, 211Industry Standard Architecture, siehe ISA-BusINF, siehe Gleitkommazahlen, INFInformatik

angewandte, 2Definition, 1Geschichte, 3Kern-, 2Klassifizierung, 2praktische, 2Studium, 3technische, 2theoretische, 2Wurzeln der, 1

Information, 37, 60, 66Informationsgehalt, 60, 61

maximaler, 63mittlerer, siehe Entropie

Informationstheorie, 60, 602Ingalls, D., 667Inkrement, 764Inorder, siehe Binärbaum, Durchsuchen, InorderInsertion Sort, siehe Sortierverfahren, Insertion SortInstruction Set Architecture, siehe ISAInstrumentierung, 333integrierter Schaltkreis, 175Integrität, 138Intel, 9, 228Interaktionsübersichtsdiagramm, 768Interface, 772Interleave-Faktor, 512Intermediate Language, 309Internet, 281, 287Internet Protocol, siehe IPInterNIC, 288Interpolationssuche, siehe Suchverfahren,

InterpolationssucheInterpreter, 322, 409, 597Interprozess-Kommunikation, 316Interrupt, 195, 197, 204, 251Interrupt-Maske, 204Intranet, 288

796 Index

Inverse (modulare), siehe modulare InverseInverter, 174, 186Involution, 178IP, 265, 290IP-Adresse, 291IP-Datagramm, 290IPL, 9IPSec, 153, 158IPv4, 291IPv6, 292ISA, 234ISA-Bus, 253ISBN-10, 104ISDN, 103, 282ISO 7498, siehe OSI-ModellIsolation, siehe TransaktionIterative Software-Entwicklung, 760

J

Jacobsen, I., 766Jacquard, Joseph Maria, 5Java, 410, 601, 626, 631, 632, 721Java Archiv, 684Java Community Process, siehe JCPJava Database Connectivity, siehe JDBCJava Development Kit, siehe JDKJava Runtime Environment, siehe JREJava Specification Request, siehe JSRJava Virtual Machine, siehe JVMJava-Compiler, 672JavaScript, 601, 721, 723

Anweisungen, 724Datentypen, 724DOM, 730Ereignis, 732Funktion, 725Object, 727Prototyp, 728

JavaScript Object Notation, siehe JSONJCP, 703JDBC, 352JDK, 672JIT, 671JK-Flip-Flop, 191Jobs, Steve, 9Join, 346JPEG, 80, 116, 119, 128, 131, 133, 713JPEG 2000, 133JRE, 672

JRuby, 671JSON, 353, 362, 729JSR, 703JUnit, 756Just in Time Compiler, siehe JITJVM, 309, 328, 670

K

k-größtes Element, 503Kahn, B., 287Kanal, 37Kanalcodierung, siehe BinärcodierungKante, 524Kapselung, siehe GeheimnisprinzipKarnaugh-Veitch-Diagramm, 183, 187Karp, R., 443Kartesisches Produkt, 344Kasiski-Test, 141Katalog, siehe VerzeichnisKathode, 169Kausalität, siehe KausalprinzipKausalprinzip, 49, 379, 448Kay, A., 667kB, 14kByte, 14KDE, 327Kelleralphabet, 384Kellerautomat, 383, 395, 396, 403, 404

deterministischer, 384, 385leerer Keller, 385nichtdeterministischer, 384, 385

Kellerspeicher, siehe StackKellersymbol, 384Kern, 394Kernel, 305Kernel-Modus, 307, 320, 333Kernighan, B. W., 9, 616Kerninformatik, siehe Informatik, Kern-Key Addition (AES), 153Key Management, siehe SchlüsselmanagementKey Schedule, 152Key-Value-Store, 353Keynes, J. M., 54KI, 9, 10, 52, 600, 605KiB, 14Kibibyte, 14Klasse, 680, 769

JavaScript, 728, 740Klassendiagramm, 338, 769

Index 797

Kleene, S.C., 702Kleenesche Hülle, 393, 400Klumpenbildung, siehe Hashing, KlumpenbildungKnoten, siehe Baum, Knoten; Graph, KnotenKnown-Plaintext Angriff, 141, 148, 151, 155Knuth-Morris-Pratt, siehe Pattern Matching,

Knuth-Morris-PrattKoaxialkabel, 267, 277Königsberger Brückenproblem, 560, 563Körper (endlicher), siehe endlicher KörperKollektor, 173Kollision (Hashing), siehe Hashing, KollisionKolmogoroff-Komplexität, 450Kolmogorowsche Axiome, 48Kombinationen, siehe Kombinatorik, KombinationenKombinatorik, 56

Kombinationen, 57Variationen, 57

kombinatorische Schaltung, 185Kommandozeilen-Interpreter, siehe CLIKommunikationsdiagramm, 768Kommutativgesetz, 178Komplement

Einer-, 26

Einerrücklauf, 26

Neuner-, 219Zehner-, 26, 28Zweier-, 25, 26, 27, 203

komplementäres Element, 178komplexen Einheitswurzel, 129Komplexität, 431

algorithmische, 450Kolmogoroff-, 450NP, siehe NP (Komplexitätsklasse)Ordnung, siehe O-NotationP, siehe P (Komplexitätsklasse)

Komplexitätsklasseco-NP, siehe co-NPEXPSPACE, 447EXPTIME, 446NEXPSPACE, 447NEXPTIME, 446NP, siehe NP (Komplexitätsklasse)NPSPACE, 447P, siehe P (Komplexitätsklasse)PSPACE, 447

Komponente, 669, 752Komponentendiagramm, 767Komposition, 681, 771Kompositionsstrukturdiagramm, 767

Kompression, siehe DatenkompressionKonfigurationsmanagement, 756konjunktive Normalform, 181, 183, 443Konstruktor, 681, 728, 740kontextfreie Grammatik, 395, 406, 410kontextfreie Sprache, 385, 396, 404kontextsensitive Grammatik, 395kontextsensitive Sprache, 390, 396, 408Kontrollmatrix, 96Korn, A., 7Kosinus-Transformation, siehe DCTKreuzparitätskontrolle, 86Kreuzprodukt, 344Kreuzschienenverteiler, 256Kritikalität, 750Kruskal, Algorithmus, siehe Graph, KruskalKryptanalyse, 137, 140, 141Kryptographie, siehe Verschlüsselung, 137Kryptologie, siehe Verschlüsselung, 137künstliche Intelligenz, siehe KIKV-Diagramm, siehe Karnaugh-Veitch-Diagramm

L

L-System, 460L1-, L2-, L3-Cache, 247L2-Norm, 582Lagrange-Interpolation, 109Lambda-Kalkül, 702LAMP, 734LAN, 275Landau-Symbole, 433Langzahlmultiplikation, 437Lauflängen-Codierung, siehe RLCLCM, 450LDS, 196leeres Wort, 393Leerheitsproblem, 423Leibniz, Gottfried Wilhelm, 4, 5Leistung, 170Leitungscodierung, 268Leitungsvermittlung, 279Lerdorf, R., 734Levenshtein-Distanz, 361, 478lex, 413lexikalische Analyse, 378, 410, 413Lichtwellenleiter, 267, 276LIFO, siehe StackLindenmayer-System, 460linear beschränkter Automat, 390, 395, 396

798 Index

lineare Codes, 91, 92lineare Liste, 469, 484, 486, 526, 534, 656, 690

durchsuchen, 657, 659einfügen, 657, 659löschen, 657, 659suchen, 657, 659

lineares Modulo-Kongruenzverfahren, 450Linker, 411Links-Shift, siehe Shift-Operationlinkslineare Produktion, 396Linux, 302, 321, 328Liskovsches Substitutionsprinzip, 689, 771LISP, 9, 409, 600Literal, 677LiveScript, siehe JavaScriptLL(k)-Grammatik, 410LLC-Subschicht, 275Load-and-Store-Architektur, 235, 671Local Area Network, siehe LANlogische Gatter, 174, 185, 186logische Operationen, 24, 177, 219LOGO, 601lokales Netz, siehe LANLokalität, 247LOOP-berechenbar, 423, 427LOOP-Programm, 423, 426, 428Lost Update, 313, 355Lovelace, Ada Byron Countess of, 5, 602Lower Data Strobe, 196LR(k) Sprache, 385LTE, 285LZW-Algorithmus, 123, 125, 127

M

m-aus-n-Code, 85M68000, 194, 195, 197–199, 201–206, 208, 214,

217–219, 228MAC-Adresse, 276MAC-Subschicht, 275Magic Number, 679Magnetbandspeicher, 510Mainframe, 302Makro, 222Man-in-the-Middle Angriff, 165Manchester-Code, 268Manhattan-Abstand, 583Map-Reduce, 355MARK1, 8Markup, 709

Markup-Sprache, 362Markup-Tag, 709Maschinenbefehl, 204Maschinencode, 411maschinenorientierte Sprachen, 213Maschinensprache, 213, 409, 597, 602Massenspeicher, siehe Festplatte, Solid-State-Disk,

Bandlaufwerk, 15Master-Slave-Flip-Flop, 192Matrix-Code, 106Mauchly, John W., 8MaxiCode, 106Maxterm, 181Maxwell, J. C., 64Maxwells Dämon, 64MB, 14MByte, 14MD5, 159Mealy-Automat, 373, 375Mebibyte, 14mechanische Rechenmaschinen, 4Median, 503Medium, 267Mehrbenutzer-Betrieb, 304Meilenstein, 761Memory Management Unit, siehe MMUMemory Mapped I/O, 209Mengendifferenz, 345Mengendurchschnitt, 345Mergesort, siehe Sortierverfahren, Mergesort, 437Messaging, 316Metasprache, 607Metazeichen, 412Metcalfe, R. M., 276MFLOPS, siehe FLOPSMiB, 14Microsoft, 9Mikrocontroller, 259Mikrokernel, 305Mikroprogramm, 234Mikroprozessor, siehe CPUMiller-Rabin Test, 457MIMD, 237MIME, 295MIMO, siehe RaummultiplexMinimalautomat, siehe Automat, minimalerMinterm, 181, 183MIPS, 14, 227MIPS-Prozessor, 235MISD, 237

Index 799

MISRA, 600Mittelwert, 54mittlere Wortlänge, 70Mix Columns (AES), 153MLT3-Code, 268MMU, 195, 249, 318Modellbildung, 2, 338, 765Modem, 281MODULA 2, 599modulare Exponentiation, 163modulare Inverse, 144, 146, 148, 161Modulation, 269Modulo-Kongruenzverfahren, 450Monitor, 698monotone Grammatik, 395Monte-Carlo-Methode, 452Moore, G., 228Moore-Automat, 374, 375Mooresches Gesetz, 228Morse, Samuel, 7Morse-Code, 7, 71, 79Mosaic-Browser, 708Most Significant Bit, siehe MSBMotorola, 194MOVE, 202, 205, 214MP3, 80, 116, 713MPEG, 133MS-DOS, 9, 328MSB, 25, 26, 30, 31, 203Multi-Core-CPU, 243Multi-Touch, 327Multicast, 272, 291Multicomputer-System, 229, 245, 354Multiplex, 201, 271Multiplikation

große Zahlen, 437, 438Karatsuba-Verfahren, 438

Multiplikation (binäre), siehe binäre Arithmetik,Multiplikation

Multiprocessing, 309, 311Multiprozessor-System, 229, 244Multitasking, 304, 309

non-preemptive, 311preemptive, 311

Musterabgleich, siehe Pattern MatchingMutual Exclusion, 313MySQL, 734, 743

N

N-Flag, 203

Nachbereich, 394, 399Nachfolger (Baum), siehe Baum, NachfolgerNachricht, 37, 69Nachrichtenraum, 38, 69, 91Namensraum, 673, 683NaN, siehe Gleitkommazahlen, NaNNAND, 175, 183Nassi-Shneiderman-Diagramm, 777NATURAL, 602NEA, siehe nichtdeterministischer Automatnegative Null, siehe Gleitkommazahlen, negative

Null. NET , 601Netzwerk-DBMS, 339Netzwerkschicht, 265Neunerkomplement, siehe Komplement, Neuner-Neuronale Netze, 40Neuronen, 40NEXPSPACE, 447NEXPTIME, 446NICHT, siehe NOTnicht-berechenbare Funktion, 418nichtdeterministische Turing-Maschine, siehe

Turing-Maschine, nichtdeterministische, 388nichtdeterministischer Automat, 373, 380Nichtterminalsymbol, 393, 607NMI, 197, 204Non-Autovektor-Interrupt, 197NOR, 175, 183, 190Normalverteilung, 449, 452NoSQL, 340, 353NOT, siehe logische Operationen, 24, 174Not a Number, siehe Gleitkommazahlen, NaNNP (Komplexitätsklasse), 440NP-schwer, 441, 446NP-vollständig, 440, 441, 443, 446, 564NPSPACE, 447NRZ-Code, 268NTBA, 282Nullbaum, 524NUMA, 244Nygaard, K., 667Nyquist-Bedingung, 44

O

O-Notation, 431, 432, 435, 439ObjectiveC, 667ObjectivePascal, 667Objektcode, 411

800 Index

Objektdiagramm, 767objektorientierte Programmierung

PHP, 740objektorientierte Sprache, 601objektorientiertes DBMS, 340objektrelationales DBMS, 340OCCAM, 602OCR, 105ODER, siehe ORöffentlicher Schlüssel, 139OFDM, siehe orthogonales FrequenzmultiplexOhm, 170Oktalsystem, 17, 18, 18, 19, 22, 34, 622, 623Oktalzahl, siehe OktalsystemOLAP, 356OLTP, 355OMG, 766One-Time-Pad, 139, 141, 142, 154, 155Online Analytical Processing, siehe OLAPOnline Transaction Processing, siehe OLTPOntologie, 605OP-Code, 204, 205Open Source, 670, 702, 703, 724, 743Operationsprinzip

datenflussorientiert, 230von Neumann, 230

operatives System, 356optische Täuschung, 40optische Zeichenerkennung, siehe OCROQL, 340OR, siehe logische Operationen, 24, 175, 186Ordnung

Halb-, 584partielle, 584strenge Total-, 585totale, 585

orthogonale Transformation, 129orthogonales Frequenzmultiplex, 271Ortsraum, 128OSI-Modell, 263OSI-Schichtenmodell, 138Out-of-Order-Execution, 239Overflow, 203overloading, siehe überladenoverriding, siehe überschreiben

P

P = NP Problem, 159, 391, 440, 443P (Komplexitätsklasse), 440

Package, siehe NamensraumPacket Switching, siehe PaketvermittlungPage Fault, 319Page Frame, 318Page Table, 318Paging, 319Paketdiagramm, 767, 775Paketvermittlung, 279PAN, 274Parallelität, 10, 238, 240, 241, 354Parität, 85, 88, 96, 103Parnas, D., 668Parser, 410, 413, 611Parsing Problem, 404partielle Ordnung, 584Partridge, Seth, 5Pascal, 598, 599, 601, 604, 616, 626Pascal, Blaise, 4Pascaline, 4Pascalsches Dreieck, 56PATRICIA, siehe Suchverfahren, PATRICIAPattern Matching, 378, 474

Boyer-Moore, 476durch Automaten, 475Knuth-Morris-Pratt, 476Levenshtein-Distanz, siehe Levenshtein-Distanzsequentiell, 474

Patterson, Tim, 9PC, 228, 302PCB, 310PCI-Bus, 15, 253PCIe, 256PCM, siehe Pulse-Code-ModulationPCRE, 736PDA, siehe KellerautomatPDF, 123PEARL, 601perfekter Code, 94, 96Peripheral Component Interconnect, siehe PCI-BusPeripheriegerät, 15, 232Perl, 412, 721, 735, 736PERM, 8Perpetuum Mobile, 64Personal Area Network, siehe PANPetri-Netz, 605Petterson, D., 235Pfad, 524PGP, 164Pharmazentralnummern, 104

Index 801

Phi-Funktion (eulersche), siehe eulerschePhi-Funktion

PhoneGap, 723PHP, 412, 601, 626, 721, 734

Array, 736Datentypen, 735Formular, 741Funktion, 738Klasse, 740Namensraum, 741Sitzungsdaten, 742

Phrasenstrukturgrammatik, siehe allgemeine Sprache,394

Piconetz, 275Pipe, 316, 324Pipelining, siehe FließbandverarbeitungPixel, 717PL/1, 599Plattenspeicher, 510, 511Plug-And-Play, 320PNG, 116, 713Point-to-Point Protocol, siehe PPPPolarmethode, 452Polling, 255Polymorphie, 689, 772Polynomdivision, 101polynomial reduzierbar, 441, 443POP, 202, 661POP3, 295Port, 266, 294positive Null, siehe Gleitkommazahlen, positive NullPOST-Request, 297, 719, 721Postfix-Schreibweise, siehe UPNPostorder, siehe Binärbaum, Durchsuchen, PostorderPostscript, 123PowerShell, 322PPP, 281Präcompiler, 409prädikative Sprache, 600Präfixcode, 79präfixfrei, 79Präprozessor, 409, 600, 619, 620Pragmatik, 603praktische Informatik, siehe Informatik, praktischePrefetch, 207Preorder, siehe Binärbaum, Durchsuchen, PreorderPrim-Jarník-Algorithmus, siehe Graph, Prim-Jarník-

AlgorithmusPrimärschlüssel, 342PRIMES, 446

Primfaktorisierung, 146, 147, 157, 160, 161, 440,446, 456

primitiv rekursive Funktion, 462primitive Rekursion, 423, 426, 428primitive Wurzel, 158primitives Polynom, 99Primpolynom, 99, 103, 107Primzahl, 107, 145–147, 156–158, 160, 163, 164,

420, 446, 455–457, 481–483sichere, 158, 161, 164

Primzahltest, 455, 457AKS, 456Fermat, 456Miller-Rabin, 457

Principle of Indifference, 54Prioritätswarteschlange, 541, 542, 577, 579, 589Priority Queue, siehe Prioritätswarteschlangeprivater Schlüssel, 139probabilistische Turing-Maschine, siehe Turing-

Maschine, probabilistischeprobabilistischer Primzahltest, 455problemorientierte Programmiersprachen, 213Product Backlog, 764Product Owner, 763Produktion, 393Produktrisiko, 750Profibus, 15Profildiagramm, 767Programmiersprache

ADA, siehe ADAALGOL, siehe ALGOLAssembler, siehe AssemblerBASIC, siehe BASICC, siehe CC++, siehe C++C#, siehe C#Clojure, siehe ClojureCOBOL, siehe COBOLdeklarative, siehe deklarative Spracheerweiterte D-Struktur, 605FORTH, siehe FORTHFORTRAN, siehe FORTRANfunktionale, siehe funktionale SpracheGroovy, siehe GroovyGrundstrukturen, 605höhere, siehe höhere Programmierspracheimperative, siehe imperative SpracheJava, siehe JavaJavaScript, siehe JavaScript; HTML, JavaScriptJRuby, siehe JRuby

802 Index

LISP, siehe LISPLOGO, siehe LOGOMaschinensprache, siehe MaschinenspracheMODULA 2, siehe MODULA 2NATURAL, siehe NATURALObjectiveC, siehe ObjectiveCObjectivePascal, siehe ObjectivePascalobjektorientierte, siehe objektorientierte SpracheOCCAM, siehe OCCAMPascal, siehe PascalPEARL, siehe PEARLPerl, siehe PerlPHP, siehe PHPPL/1, siehe PL/1prädikative, siehe prädikative SprachePROLOG, siehe PROLOGprozedurale, siehe prozedurale SprachePython, siehe PythonRuby, siehe RubyScala, siehe ScalaScheme, siehe SchemeSimula, siehe SimulaSmalltalk, siehe SmalltalkSQL, siehe SQL

Programmierungdeklarativ, 701ereignisgesteuert, 732funktional, 702, 727generisch, 739testgetrieben, 697, 764

Projektion, 344, 427Projektmanagement, 754PROLOG, 9, 409, 464, 600, 601Property, 681Prototyping, 760Provider, 281, 287prozedurale Sprache, 598–600Prozess, 309Prozess-Steuerblock, siehe PCBProzess-Zustände, 310Prozessverwaltung, 309Prüfziffer, 104Pseudo-Tetraden, 72, 82, 187Pseudo-Zufallszahlen, siehe ZufallszahlenPseudocode, 776PSK, siehe ModulationPSPACE, 447Public Key Kryptographie, siehe Verschlüsselung,

asymmetrischPuffer, siehe Queue

Pulse-Code-Modulation, 45, 115Pulsfrequenzmodulation, 39Pumping-Theorem, 399, 400

kontextfreie Sprachen, 403reguläre Sprachen, 402

Punkt-zu-Punkt Verbindung, 256, 276, 281PUSH, 202, 661Push-down Automaton, siehe KellerautomatPython, 412, 601

Q

QAM, siehe ModulationQPSK, siehe ModulationQR-Code, 85, 106, 107, 111Quadtree, 119Qualitätsmanagement, 755Quantisierung, 44Quantisierungsfehler, 45Quantisierungsrauschen, 45Quantisierungstabelle, 132Quelle, 37Quellen-Redundanz, 71Quellsprache, 409Queue, 574, 663, 690, 700Queveda, Torres y, 7Quicksort, siehe Sortierverfahren, Quicksort, 437,

461, 534

R

Radó, T., 429Radix-Suche, siehe Suchverfahren, Radix-SucheRAM, 208, 510Random-Access-Memory, siehe RAM; SpeicherRaummultiplex, 271Read-Only-Memory, siehe ROM; Speicherreaktives System, 674Rechenschieber, 5, 12Rechenwerk, 5, 13, 30, 192, 231Rechts-Shift, siehe Shift-Operationrechtslineare Produktion, 396Reduced Instruction Set Computer, siehe RISCRedundanz, 70, 71, 75, 82, 89, 115, 123Reduzierbarkeit, 421Reed-Solomon Codes, 100, 106, 107, 107–109, 111,

147, 434Refactoring, 752reflexiv-transitive Hülle, 394Reflexivität, 584Register, 30, 192, 208, 231

Index 803

Registermaschine, 418reguläre Grammatik, 396, 410reguläre Sprache, 377, 396, 401, 404, 411regulärer Ausdruck, 410, 411, 446, 447, 677, 736Reis, Philipp, 7rekurrent, 460Rekursion, 426, 428, 436, 459, 501

μ-, siehe μ-rekursive Funktionprimitive, siehe primitive Rekursion

Rekursionstiefe, 460rekursiv aufzählbare Sprache, siehe allgemeine

Sprache, 394Relation, 341Relationale Algebra, 343Relationales DBMS, 340, 341relative Häufigkeit, 47Repeater, 265Requests for Comments, siehe RFCRESET, 198Review, 755Rezeptor, 39RFC, 288Rice, Satz von, 422Ries, Adam, 4Rijndael-Algorithmus, siehe AESRing-Topologie, 272Ringpuffer, 663RIPE, 288RISC, 235Ritchie, D. M., 9, 616RLC, 118, 119, 133RLE, siehe RLCRöhren-Computer, 8ROLAP, 356Roll Up, 358ROM, 209Round-Robin-Scheduling, 313Router, 265, 290RS-Flip-Flop, 190RSA, 139, 147, 153, 160, 165, 297RSA Factoring Challenge, 164Ruby, 721Rumbaugh, J., 766Rundenschlüssel, 152, 153

S

Sackgasse, 399, 404, 408Sampling, siehe AbstastungSampling Rate, 44

SAT, 442, 443SATA, 103, 249Scala, 671Schaltfunktion, 180Schaltnetz, 185, 186, 371Schaltwerk, 189, 192, 371, 418Scheduling, 310, 311Schemalosigkeit, 354Scheme, 601Schicht, 305, 752Schichten-Architektur, 307Schickard, Wilhelm, 4Schieberegister, 154Schlüssel, 342Schlange, siehe QueueSchlüsselmanagement, 138Schnittproblem, 423Schreibtischmetapher, 326Scrum, 758, 763Scrum Master, 763SCSI-Festplatte, 249SDM, siehe RaummultiplexSechzehnersystem, siehe HexadezimalsystemSegment (Speicher), 209Sektor, 249, 512Sekundärspeicher, 248Selbstanwendbarkeitsproblem, 420Selbstreferenz, 728Selection Sort, siehe Sortierverfahren, Selection SortSelektion, 344Semantik, 603semantische Analyse, 410Semaphore, 315, 698semi-strukturierte Daten, 354, 362, 729Semiotik, 602Senke, 37sequentielle Speicherorganisation, 509sequentielle Suche, siehe Suchverfahren, sequentielle

SucheSequenz, 506–508Sequenzdiagramm, 768, 772Serialisierbarkeit, 356serielle Übertragung, 256serielle Verarbeitung, 233Serienaddierer, 190Service, siehe DienstSession-Key, 164SHA-1, 159SHA-2, 159, 166Shakersort, siehe Sortierverfahren, Shakersort

804 Index

Shannon, Claude, 43, 60, 155Shannonsches Codierungstheorem, 70Shared Memory, 316Shell, 305, 322, 412Shell-Skript, 325Shellsort, siehe Sortierverfahren, ShellsortShift Rows (AES), 153Shift-Operation, 29, 30

arithmetisch, 30logisch, 30

sichere Primzahl, siehe Primzahl, sichereSicherungsschicht, 265Sieb des Eratosthenes, 455Signal-Rausch-Abstand, 45Silizium, 172, 176SIM, 286SIMD, 236, 240, 701Simplex, 272Simula, 601, 667Simultanes Multi-Threading, 243SISD, 236, 238, 239Sitzungsschicht, 266Smalltalk, 601, 667Smartphone, 16, 227, 302, 327, 409SMIME, 296SMTP, 295Snooping, 248Software-Architektur, 752Software-Engineering, 747Software-Lebenszyklus, 751Software-Test, 752, 756Software-Wartung, 753Solid State Disk, siehe SSDsort, 324Sortierverfahren

1-Phasen-4-Band-Mischen, 5132-Phasen-3-Band-Mischen, 5134-Band-Mischen, 513am Platz, 490binäres Einfügen, 493Bottom-up Heapsort, 547Bubblesort, 490, 491, 496, 497, 500, 504clever Quicksort, 502Direct Merge, 513, 516direkte, 489, 491externe, 490, 506

Heapsort, 491, 504, 542, 542höhere, 491, 499Insertion Sort, 491, 492, 504Klassifizierung, 491

Komplexität, 491, 492, 494, 498, 500, 502, 504,515, 545

Mergesort, 491, 504, 513, 516, 518n-Band-Mischen, 518Natural Merge, 516Pivotelement, 500Quicksort, 490, 491, 500, 504, 516, 545Reverse Heapsort, 547Schlüssel, 491Selection Sort, 491, 494, 504Shakersort, 497, 504Shellsort, 491, 499, 504Vergleich, 504

Spaghetti-Code, 668Spaltenorientierte Datenbank, 353Spannbaum, siehe Graph, SpannbaumSpannung, 170SPARC-Prozessor, 235Speicher, 5, 13, 169, 190, 192Speicherhierarchie, 245Speicherkomplexität, siehe Komplexität, 431Speicheroperation, 509Speicherorganisation, sequentielle, 509Speicherwerk, 232Speicherzugriff, 509Speicherzyklus, 509Spezialisierung, 668, 771Spezifikation, 751Spielekonsole, 228Splitter, 282Sprache, 394, 396, 603

Abgeschlossenheit, 400allgemeine, siehe allgemeine Sprachedeterministisch kontextfreie, siehe LR(k) Sprachekomplementäre, 394kontextfreie, siehe kontextfreie Sprachekontextsensitive, siehe kontextsensitive SpracheMächtigkeit, 377, 403Programmier-, siehe Programmiersprachereguläre, siehe reguläre Sprache

Spreizung, 285Springerproblem, 464Sprint Backlog, 764Sprungvorhersage, 239SQL, 340, 347, 602

Datentypen, 348GROUP BY, ORDER BY, 352INSERT, UPDATE, DELETE, 350SELECT, FROM, WHERE, 351

SQL-92, 347

Index 805

SRAM, 246SSD, 250, 320SSH, 153, 158, 164, 296, 297, 325SSL, 296, 298Stack, 202, 208, 309, 383, 572, 660, 690Stack Pointer, 202Standardabweichung, 54Stapel, siehe StackStapelverarbeitung, 304Star Join, 358Startsymbol, 393Startzustand, 384statisches SQL, 352statisches Typkonzept, 632Status-Code, 298Statusregister, 203Steganographie, 137Steinbuch, Karl, 1Stellendistanz, 82Stellenwertsystem, 17

Achtersystem, siehe OktalsystemBinärsystem, siehe BinärsystemDezimalsystem, siehe DezimalsystemDualsystem, siehe BinärsystemHexadezimalsystem, siehe HexadezimalsystemOktalsystem, siehe OktalsystemUmwandlung, siehe ZahlenumwandlungZweiersystem, siehe Binärsystem

Stellungnahme, 755Stereotyp, 767Stern-Topologie, 272, 276Sternschema, 356Steuerbus, 15, 199Steuergerät, 15Steuerwerk, 5, 13, 192, 231Stibitz, R., 8Stibitz-Code, 71Strange Loop, 421strenge Totalordnung, 585Streuung, siehe VarianzStromchiffre, 154Stromkreis, 169Stromstärke, 169Stromverbrauch, 304strong typing, 631, 632Stroustrup, B., 667Structured Query Language, siehe SQLStruktogramm, 777Sub Bytes (AES), 152Subnetzmaske, 292

Substitutions-Chiffren, 140Subsystem, 752Suchbaum

binärer, siehe binärer SuchbaumSuchverfahren

binäre Suche, 470, 471, 489Interpolationssuche, 471Muster in Strings, siehe Pattern MatchingPATRICIA, 473Radix-Suche, 473sequentielle Suche, 469

superskalarer Mikroprozessor, 239Supervisor Bit, 199, 203Supervisor-Modus, 204, 307Supervisor-Stack-Pointer, 202Suraski, Z., 734Switch, 265, 272, 276symmetrische Verschlüsselung, siehe Verschlüsse-

lung, symmetrischsynchrone Bussteuerung, 196Synchronisation, 313syntaktische Analyse, siehe SyntaxanalyseSyntax, 603Syntaxanalyse, 385, 404, 407, 410, 413, 608Syntaxbaum, 410, 609Syntaxgraph, 611System, 604System Byte, 197, 203Szilard, Leo, 65, 66

T

T-Flip-Flop, 191Tablet-Computer, 16, 227, 302Tag, siehe Markup-TagTaktfrequenz, 14taktgesteuertes Flip-Flop, 192Taktrückgewinnung, 268Tayloring, 761TB, 14TByte, 14TCP, 292TCP/IP, 287TDM, siehe ZeitmultiplexTebibyte, 14technische Informatik, siehe Informatik, technischetechnischer Durchstich, 752Teile und Herrsche, siehe Divide and Conquerteilerfremd, siehe ggTTeilhaber-Betrieb, 305

806 Index

Teilnehmer-Betrieb, 305Telefonleitung, 281telnet, 296, 325terminale Produktion, 396Terminalsymbol, 393, 607Test-and-Set, 244, 701Testsuite, 697Texas Instruments, siehe TITFLOPS, siehe FLOPStheoretische Informatik, siehe Informatik,

theoretischeThread, 243, 311, 698, 701Thue, A., 394TI, 9TiB, 14Tiefe (Baum), siehe Baum, TiefeTiefensuche, siehe Graphsuche, TiefensucheTIFF, 123TLS, 153, 158, 164Token, 410Top-Down Parser, 410, 609Topologie

Hardware, 253, 257Netzwerk, 272

topologische Sortierung, siehe Graph, topologischeSortierung

Torvalds, L., 328totale Ordnung, 585Touch-Bedienung, 302Trace Bit, 199, 203Transaktion, 355Transduktor, 374Transistor, 173–175transitive Hülle, 393Transitivität, 584Transmission Control Protocol, siehe TCPTransportschicht, 266Transpositions-Chiffren, 143, 144, 148Trap, 251, 333Travelling Salesman, 444, 445, 564Treiber, siehe GerätetreiberTries, 473TSP, 444, 445, 564Türme von Hanoi, 462Turing, Alan M., 144, 386, 418Turing-Berechenbarkeit, siehe Berechenbarkeit, 387

Turing-Maschine, 66, 192, 386, 386, 390, 394, 396,418, 422, 426, 428–430, 440, 442

Anweisungen, 387Brownsche, 66

Konfiguration, 387probabilistische, 389reversible, 66universelle, 417

Twisted-Pair-Kabel, 267, 276

U

UDP, 293UDS, 196überabzählbar unendlich, 389, 395, 419Übergangsdiagramm, 375Übergangsfunktion, 372–374, 384, 386Übergangsgraph, siehe ÜbergangsdiagrammÜbergangstabelle, 374überladen, 688überschreiben, 689übersetzender Automat, 374Übersetzer, siehe CompilerÜbertragsbit, siehe CarryUMA, 244umgekehrte polnische Notation, siehe UPNUML, 766UMTS, 285UND, siehe ANDUnderflow, siehe Gleitkommazahlen, Underflowunentscheidbar, 409, 420–422Unicast, 272Unicode, 74, 363, 709Unified Modeling Language, siehe UMLUniform Resource Identifier, siehe URIuniforme Kosten Suche, siehe Graphsuche, uniforme

Kosten SucheUnion-Find, siehe Graph, Union-Findunitäre Matrix, 129unitäre Transformation, 129Universal Serial Bus, siehe USBUnix, 9, 321, 328, 600, 616unmittelbare Adressierung, 211unvollständiger Automat, 378Unvollständigkeitstheorem, 417, 421UPN, 527, 662Upper Data Strobe, 196URI, 298URL, siehe URIURN, siehe URIUSB, 15, 101, 103, 254, 320Use Case, 768User Datagram Protocol, siehe UDPUser-Mode, 204, 307

Index 807

User-Stack-Pointer, 202UTF, siehe Unicode

V

V-Flag, 203V-Modell (Boehm), 756V-Modell XT, 761Valid Memory Address, 196Valid Peripheral Address, 196Validierung, 2Varianz, 54Variationen, siehe Kombinatorik, VariationenVater, siehe Baum, VaterVcc, 194VDSL, siehe DSLVektorprozessor, 229, 240Vektorraum, 91Venn-Diagramm, 180Verband, 179Verbund, 346Vereinigung, 345Vererbung, 771

JavaScript, 729verkettete Liste , siehe lineare Listeverlustbehaftete Kompression, siehe Datenkompressi-

on, verlustbehaftetverlustfreie Kompression, siehe Datenkompression,

verlustfreiVernam-Chiffre, siehe One-Time-Pad, 137, 141, 142Verschieben (bitweise), siehe Shift-OperationVerschlüsselung, 137, 448

AES, siehe AESasymmetrisch, 138, 156, 455Cäsar-Code, siehe Cäsar-CodeDES, siehe DESklassische Verfahren, 140Passwörter, 160RSA, siehe RSASubstitutions-Chiffren, siehe Substitutions-

Chiffrensymmetrisch, 138, 139, 150

Transpositions-Chiffren, siehe Transpositions-Chiffren

Vigenère-Code, siehe Vigenère-CodeVersionskontrolle, 756Verteilungsdiagramm, 767Vertex, siehe Graph, KnotenVerzeichnis, 321VHDL, 192

vi, 324Vielwegbaum, 548

(a,b)-Baum, 549, 551B-Baum, siehe B-BaumBrüder, 548Speicherung, 548

Vigenère-Code, 141Virtual Machine Monitor, siehe HypervisorVirtualBox, 332Virtualisierung, 330Virtuelle Maschine, 308, 330, 333virtueller Speicher, 249, 317VLIW, 240VLSI, 9, 176VMA, 196VMM, siehe HypervisorVMware, 332Voice-Over-IP, 283Volladdierer, 188, 190Volt, 169von Neumann, J., 8, 230von-Neumann-Architektur, 8, 10, 230, 598von-Neumann-Flaschenhals, 233Vorgänger, siehe Baum, VorgängerVorgehensbaustein, 762Vorgehensmodell, 757

agil, 758plangetrieben, 757Produkt, Rolle und Aktivität, 757, 762

Vorzeichenbit, 26, 31VPA, 196, 198

W

W3C, 708Wählverbindung, 281Wahrheitstafel, 24, 91Wahrheitswert, 177Wahrscheinlichkeit, 47, 48

Additionsgesetz, 48Bayes, 49, 51, 54bedingte, 49totale, 49, 51

Walkthrough, 755Warteschlange, siehe QueueWasserfallmodell, 759Watchdog, 198Wavelet-Transformation, 133Waver, 176Web of Trust, 165

808 Index

Webersches Gesetz, 39wechselseitiger Ausschluss, 313Weg, 524WEP, 278WHILE-Programm, 418, 425, 426, 428, 429, 462Widerstand, 170WiFi, siehe WLANWilkes, V., 9WIMP, siehe SchreibtischmetapherWindows, 328Windows 8, 305Windows Apps, 306Windows NT, 328Windows RT, 328WinRT, 306Wireless LAN, siehe WLANWirth, N., 599, 616WLAN, 275, 277Working Directory, siehe ArbeitsverzeichnisWorld Wide Web, 288Worst-case Laufzeit, 431Wortlängenmonotonie, 395Wortproblem, 378, 404, 408, 409, 423, 446, 447Wozniak, Stephen, 9WPA, 278WPA2, 153, 278Wurzel, siehe Baum, WurzelWurzelbaum, 523WYSIWYG, 709

X

X-Flag, 203x86-Prozessor, 234, 306, 333XenServer, 332XML, 353, 362, 601

-Schema, 365Attribut, 364Element, 364Namensraum, 365Prolog, 363valide, 365wohlgeformt, 365

XOR, siehe logische Operationen, 24, 92, 99, 101XP, 764XPath, 366XSD, siehe XML-SchemaXSL, 366

Y

yacc, 409, 413

Z

Z-Flag, 203Zahlensystem, siehe StellenwertsystemZahlenumwandlung, 18, 22

direkte Methode, 18Divisionsmethode, 19Horner-Schema, 20Nachkommastellen, 20, 22periodische Brüche, 22Restwertmethode, 20

Zehnerkomplement, siehe Komplement, Zehner-Zehnersystem, siehe DezimalsystemZeigerarithmetik, 678Zeitkomplexität, siehe Komplexität, 431Zeitmultiplex, 271, 277, 311Zeitverlaufsdiagramm, 768Zentraleinheit, 12Zentralprozessor, siehe CPUZerteilungsproblem, siehe Parsing ProblemZielsprache, 409zOS, 302Zufallsexperimente, 47Zufallszahlen, 154, 448, 449

gleichverteile, 450normalverteilte, 452Polarmethode, 452

Zugriffhalbsequentieller, 510sequentieller, 510serieller, 510wahlfreier, 510

Zugriffszeit, 510Zuse Z3, 7Zuse, Konrad, 7Zustand, 372Zustandsdiagramm, 768, 774Zwei-Adress-Maschine, 209Zweierkomplement, siehe Komplement, Zweier-Zweiersystem, siehe Binärsystemzyklischer Code, 98, 99, 107Zykluszeit, 510Zylinder, 249

Die Autoren

Professor Dr. Hartmut Ernst hat nach drei Jahren Forschungstätigkeit in den USA und Israelab 1986 als Professor für technische Informatik den Aufbau der Fakultät für Informatik an derHochschule Rosenheim begleitet. Zehn Jahre lang war er dort Mitglied der Hochschulleitung. Alsaktiver Gesellschafter eines mittelständischen Betriebs in der Datenverarbeitungsbranche ist er mitPraxisfragen bestens vertraut.

Professor Dr. Jochen Schmidt studierte Informatik an der FH Nürnberg und der UniversitätErlangen-Nürnberg, wo er anschließend lange in Forschung und Lehre auf dem Gebiet der Mus-tererkennung und Computer Vision tätig war. Es folgte ein mehrjähriger Forschungsaufenthalt ander Auckland University of Technology in Neuseeland als stellvertretender Direktor des Centre forArtificial Intelligence Research. Er hat Industrieerfahrung in der Automotive-Software-Entwicklungfür Fahrerassistenzsysteme und ist seit 2010 Professor für Informatik an der Hochschule Rosenheim.

Professor Dr. Gerd Beneken leitet den Studienschwerpunkt Software-Engineering im Stu-diengang Informatik an der Hochschule Rosenheim. Er begleitet seit 2003 studentische Teams beider Durchführung von Software-Entwicklungsprojekten, von den ersten Anforderungen bis zurLieferung an Kunden. Er promovierte an der TU München über das Thema Software-Architekturund Projektmanagement und arbeitete mehrere Jahre als Software-Ingenieur bei der sd&m AG inMünchen.

© Springer Fachmedien Wiesbaden 2016H. Ernst et al., Grundkurs Informatik,DOI 10.1007/978-3-658-14634-4