{"entities":{"Q4040541":{"pageid":6070257,"ns":120,"title":"Item:Q4040541","lastrevid":108784100,"modified":"2026-11-10T06:47:11Z","type":"item","id":"Q4040541","labels":{"en":{"language":"en","value":"Grundbegriffe der theoretischen Informatik"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 193738"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040541$0DC5CABA-DF18-4F3A-BFE0-B7EE3B0495FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aeb28047dcb4f1f4b9d0593bcb89effb815ea1f0","datavalue":{"value":"0695.68001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$D96059BD-97E3-4057-8FAB-CED4A9AE19C7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bcd3ad77457c5e98642d406d48f3bcc6a895f506","datavalue":{"value":{"entity-type":"item","numeric-id":1312714,"id":"Q1312714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040541$3AFEFCBB-7D3B-4263-89FC-E542B6A033C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28319e3934f5b194abbcd5639e9eae3758e9e43c","datavalue":{"value":{"time":"+1993-06-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4040541$8CC2C20D-5792-43B0-8BD2-810E7759ABF6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$A1677778-D0EC-482E-9C2A-FAD3B20131DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$56FF37FF-D237-4B68-BEE4-CCF6E1FB2FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$3A44BF27-2427-4AB4-ABA4-62C2AD3350B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$E1CC409E-39E9-4AD6-8C86-8C141921BA63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$572D4596-0CEE-4C7E-A5B5-55C6FDC199CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$CC4321F2-C8EE-4B6C-84DD-DCC7E37D9F9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f868c6887f9ea6fccd8194f80fbc0e333ffa468f","datavalue":{"value":"193738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040541$B0542FEA-D083-4ED9-9055-ECA9A19EDDEB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f2891ec95ee556b0ac2cc2dddee3d77811bd94","datavalue":{"value":"computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$90DEFB9C-F94D-458A-80C5-13D52CF317F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43893d5d64746664e118f56a0c06a6724f1206d0","datavalue":{"value":"unsolvability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$9B8659A7-F4FF-4A1F-8035-96F7A43418AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d1f75e8f430718e0f2a1042e291cbf21500b20b","datavalue":{"value":"grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$0FE38C40-A03C-4E12-8259-09784E43D57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$C8CB44CB-F203-43E3-A7B4-7C22090321A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$AB3E6F38-158D-4CCC-9E07-DB9777F5CC74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b343d76b5a54ac856d8d02309b9ae7b3cb9b6a3","datavalue":{"value":"complexity of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$37BDA0B0-5A34-447D-A2BF-D37EFA295BC5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040541$A55F64F7-FDB9-4B9B-A6E7-3F0114BD6FF7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fddbdb0eb095701c7e3e4370737a17fcdbaab0f","datavalue":{"value":{"entity-type":"item","numeric-id":3468598,"id":"Q3468598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99b466b2aec00f5c1434589a24ec8cef3fa1d5dd","datavalue":{"value":{"amount":"+0.9865527153015136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040541$6A069D43-2AF3-4907-B6A5-76CD695830EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79870e53d59767aade732e9ebb6b24f12c4d11bc","datavalue":{"value":{"entity-type":"item","numeric-id":4851834,"id":"Q4851834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e352a8f3df8ba115959819f0dd0d206eb618433d","datavalue":{"value":{"amount":"+0.8476285338401794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040541$CAA563B6-D828-4623-89D0-DAB40DA34205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c16824f0501d95177a135d7a6e983118c5fc829","datavalue":{"value":{"entity-type":"item","numeric-id":2715629,"id":"Q2715629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab8a7dd94094ac12ead2460653264ce531bcb47","datavalue":{"value":{"amount":"+0.8432436585426331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040541$4CF228AC-2CBF-43A7-9725-EB56B599C650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c03f7c49df26a27e43ae18e93c043e9216f4dd36","datavalue":{"value":{"entity-type":"item","numeric-id":4715507,"id":"Q4715507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06482084ba1d7ab6bd2e80969ea42abc19f451c7","datavalue":{"value":{"amount":"+0.8364361524581909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040541$12CBDE65-0AC4-4C09-9632-E0D61C1CD63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d307ed9572587989dcc749af3f1578a2141e494","datavalue":{"value":{"entity-type":"item","numeric-id":4877295,"id":"Q4877295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1a9019dc45e0c11fab815afbe353f2ecf51852","datavalue":{"value":{"amount":"+0.8313382863998413","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040541$57B47F63-50CD-41A5-A07F-E48078F4E196","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"568fdc1e4ddb11b36f4d6dbef70217c706c18bc2","datavalue":{"value":{"text":"Grundbegriffe der theoretischen Informatik","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4040541$D8009939-7E74-40F6-A249-B50F92E44F3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d6bb1a6be3dc6eaea4a46276b82626cddaaf801b","datavalue":{"value":"Inhalt des auf Vorlesungen basierenden Buches: 1. Grundlagen (stark motivierende Fragen: Ist ``alles'' berechenbar? Beweise f\u00fcr die Undurchf\u00fchrbarkeit gewisser Berechnungen) 2. Programme (Berechenbarkeit; verschiedene Programmiersprachen und ihre \u00c4quivalenz; Halteprobleme in PASCAL als (mitrei\u00dfend knapp, streng, einleuchtend durchgef\u00fchrter) Beweis f\u00fcr Nichtberechenbarkeit einer Funktion 3. Funktionen (begeisternd formalisiert vorgetragenes klassisches Wissen \u00fcber arithmetische Funktionen) 4. Regelsprachen 5. Regul\u00e4re Sprachen und Automaten 6. Kontextfreie Sprachen (klassisches Grundwissen \u00fcber Regelsprachen - bis auf einige Ausnahmen im holpernden Duktus bekannter Literatur; der Ansatz: ``Produktionssysteme und Automaten definieren Relationen \u00fcber Wortmengen'' bleibt Abbreviatur statt zum Formalismus der Relationen ausgebaut zu werden.) 7. Berechenbarkeit (\u00dcbersichtliche Einf\u00fchrung der Turingmaschinen; der Beweis ihrer \u00c4quivalenz zu MiniPascal-Programmen ist die wesentliche didaktische Leistung des Buches - so werden bereits bewiesene Resultate nutzbar und der bekannte ``Turing-Wust'' wird vermieden. Durch geschickte Reduktion auf bereits Bewiesenes k\u00f6nnen das PKP und die anderen klassischen Entscheidbarkeitsfragen auf wenigen Seiten abgehandelt werden.) 8. Komplexit\u00e4t (guter, in seiner arithmetischen Betrachtung wiederum begeisternder \u00dcberblick \u00fcber Zeitschranken, Komplexit\u00e4tsma\u00dfe und -klassen. Reduzibilit\u00e4t und Vollst\u00e4ndigkeit werden auf kleinstem Raum anschaulich abgehandelt.) Durch dies Buch weist sich Verf. vor allem als passionierter Mathematiker mit Vorlieben im Bereich des klassisch-arithmetischen Kalk\u00fcls aus. Dort gelingt ihm jene Eleganz der Beweisf\u00fchrung, die den Leser seine Umgebung vergessen l\u00e4\u00dft. Ohne es explizit zu intendieren - sozusagen als Seiteneffekt - f\u00fchrt er au\u00dferdem den beweisf\u00e4higen Umgang mit der ``PEANO-Datenstruktur'' vor. Die Unvollkommenheit des klassischen Einstiegs in die Theorie der Regel erinnern zwar schmerzhaft an das Vorlesungsmanuskript als Urbild dieses Buches, k\u00f6nnen jedoch als Anreiz verstanden werden, den Relationskalk\u00fcl \u00fcber Halbgruppen in Richtung jener Herleitungsf\u00e4higkeit auszubauen, die ohne ``Prosa'' auskommt. Kurzum: Eine in jeder Hinsicht anregende Lekt\u00fcre.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040541$31A3BAA5-C9A1-43FB-B91E-BC70006C3510","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Grundbegriffe der theoretischen Informatik","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Grundbegriffe_der_theoretischen_Informatik"}}}}}