{"entities":{"Q1360183":{"pageid":1370922,"ns":120,"title":"Item:Q1360183","lastrevid":67234791,"modified":"2026-04-12T16:16:15Z","type":"item","id":"Q1360183","labels":{"en":{"language":"en","value":"Lectures on computer science. Vol. 3: Computability, formal languages, specifications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1034444"}},"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":"Q1360183$25B98D30-1969-4097-AC49-5993D4072032","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63a04c163d2dbf83791f1e5bd3cc3ce132547697","datavalue":{"value":{"text":"Lectures on computer science. Vol. 3: Computability, formal languages, specifications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1360183$283E7BAB-6D21-481A-974B-9391F58D7308","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b85a3536dc47bd48d4c3f651c5bbe9d5fa95831","datavalue":{"value":"0879.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$7D5156A1-521F-4EDA-88AD-DC481CE8D9D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6819186aad22a1a059f3cff417ec173696dd9f42","datavalue":{"value":{"entity-type":"item","numeric-id":844182,"id":"Q844182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1360183$93FB9C94-D142-4472-BBAB-DCC769F50A0F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"529abe3227038afcd857fe878e6e645f9eb8f240","datavalue":{"value":{"entity-type":"item","numeric-id":167293,"id":"Q167293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1360183$1ED35B62-CA70-4F63-B209-3F4B9229E1B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ec8c20900676bdc973f1dd224c2bbe10923a4d6","datavalue":{"value":{"time":"+1997-07-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1360183$296D7F20-CA7B-4A15-87DD-F65E08ACC949","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ad4740d0686d799e3d58e2bd6c5de443946d98d8","datavalue":{"value":"Dieses ist der 3. Band in der Buchreihe Vorlesungen \u00fcber Informatik von Prof. Goos. Der vorliegende Band behandelt die eher theoretischen Aspekte der Informatik in ihren Grundz\u00fcgen, wie es f\u00fcr das Niveau einer Grundstudiumsvorlesung angemessen ist. Es wird mit den Themen der klassischen Berechenbarkeitstheorie begonnen: im Anschlu\u00df an eine Diskussion des Algorithmenbegriffs und der Churchschen These werden nachfolgend verschiedene Formalismen zur Spezifikation des Berechenbarkeitsbegriffs besprochen: verschiedene Formen von Programmen (auf abstrakten Maschinen), die Turingmaschine, rekursive Funktionen, und als Paradebeispiel f\u00fcr ein unterscheidbares Problem, das Postsche Korrespondenzproblem. Auf diesen Berechenbarkeitsteil schlie\u00dft sich in nat\u00fcrlicher Weise ein Abschnitt \u00fcber Komplexit\u00e4tstheorie an, wobei der Fokus auf den Klassen P und NP und verschiedenen NP-Vollst\u00e4ndigkeitsbeweisen liegt.   Die Diskussion formaler Sprachen geht den Weg von den einfachen (sprich: regul\u00e4ren Sprachen) zu den schwierigen (kontextfreien und kontextsensitiven), wobei jeweils die entsprechenden Grammatikarten und Automatentypen angegeben werden.   Eine Besonderheit dieses Buches, im Vergleich zu anderen mit \u00e4hnlichem Anliegen und \u00e4hnlicher Zielgruppe, ist die Behandlung von Programmtransformationen (Einsetzen, Falten, Entrekursivieren), und ferner auch die Behandlung der Oxforder Z-Notation zur Spezifikation von Eigenschaften objektorientierter Modelle, wobei der zentrale Begriff der des Schemas ist.   Das letzte Kapitel befa\u00dft sich mit Ablaufspezifikationen, Synchronisierung und Kommunikation. Mittels Zustandsdiagrammen (Statecharts) k\u00f6nnen Konzepte wie Ereignisse, Bedingungen, Aktionen in ihrem zeitlichen Ablauf in einem nebenl\u00e4ufigen, parallelen System modelliert werden. Probleme der Kooperation und Synchronisation zwischen Prozessen mittels geeigneten Kommunikationsprotokollen werden exemplarisch besprochen.   Zusammenfassung: ein sehr breit angelegtes Lehrbuch, das sehr viele, auch moderne Aspekte der Informatik behandelt. Hierbei kann (und soll) nat\u00fcrlich nicht jedes Thema mit seiner gesamten theoretischen Tiefe behandelt werden.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360183$C14D9F40-7173-41DC-B0C4-1B48E3A1BA76","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$A8BD3B49-3ACF-4C99-ACAD-FB4D8046289D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$9FCD8AC0-4B87-4783-85EF-0A943BB9704A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$1F6793E0-BADB-422D-AAA4-CFD09B80E659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$7074923F-7124-4108-B02D-5EE49A4FCD45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8e3f40e3cc87753c4e0b7d7ce4bdc00805f626f","datavalue":{"value":"68N01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$0F69148B-5C74-46DA-AC17-45BDE5D785EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$0662AFE6-FF0F-4DE9-AA97-A0614F92676F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$B143AFB7-A27C-4951-A614-9CFCF08CC416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$F936686D-8529-4218-834B-30CB342FA3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$CC2294CA-37DE-418A-9338-4DFB1F46E7E0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10034b1f213de8c18cc21a7dde7591da590fc0ff","datavalue":{"value":"1034444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360183$4426482B-37BC-4064-BAF4-8098A86532D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f2891ec95ee556b0ac2cc2dddee3d77811bd94","datavalue":{"value":"computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360183$3693A740-6F31-4EA2-BF2C-F431FBBED5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47511de611e7ca7c7f052290389ebfdae4c32892","datavalue":{"value":"specification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360183$E95CDBF4-394F-43F0-BF21-52D1628FD024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e2084cc29e670eea4c95dc6235db08eceb1eb8c","datavalue":{"value":"NP completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360183$FBBD7C1A-B373-4CBE-8C1F-3746E079DB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360183$4A029DF3-9345-4192-970C-CE70CE409386","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":"Q1360183$1E3950EF-16AE-4A9E-B621-470CC38105A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48489563ac10f4036f1f210094c40c5647f3aaaf","datavalue":{"value":{"entity-type":"item","numeric-id":3686043,"id":"Q3686043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa0be0b105d101c96b5d81bf9cc5ebc4ca4a71cc","datavalue":{"value":{"amount":"+0.8830788","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$A5B34924-37E8-473E-A9C6-765F050C0B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19938a644ca9d13787ad4d45fd076e2d394756f8","datavalue":{"value":{"entity-type":"item","numeric-id":3992695,"id":"Q3992695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d06b4a61db2e078a2fce7bb22343b32037e4110e","datavalue":{"value":{"amount":"+0.8693895","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$BD99EE28-75D3-42C4-8E46-F6F841564699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6bbad5a37da2b279eac05b887ccff4743c7b462","datavalue":{"value":{"entity-type":"item","numeric-id":2783417,"id":"Q2783417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"767dfc69124ac84b4a1d65a7c1c44492dacc42b6","datavalue":{"value":{"amount":"+0.8675452","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$C8E4FBAE-4B32-4AE4-811F-74E5E441879C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4e500cc4e2feec64e336e2b40066e3bbf2987ad","datavalue":{"value":{"entity-type":"item","numeric-id":4216749,"id":"Q4216749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a0a8c75016b735c3141274d7959464837828a7f","datavalue":{"value":{"amount":"+0.8621618","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$FF3B72BD-9333-46A2-8BE0-FC807E3A31E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32a8d2b4092045f3dd9407118c0c6651e93aaba6","datavalue":{"value":{"entity-type":"item","numeric-id":5906775,"id":"Q5906775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d24b6f433f7117921866a8cb522b2ed31af1d5b0","datavalue":{"value":{"amount":"+0.8617128","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$5E8327B0-0CDA-4629-8FE9-FF7036EA96CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"947e77742efa20697f2438790f8af991c00fb2dd","datavalue":{"value":{"entity-type":"item","numeric-id":5915388,"id":"Q5915388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d24b6f433f7117921866a8cb522b2ed31af1d5b0","datavalue":{"value":{"amount":"+0.8617128","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$7E51EDC4-2C7F-48EE-8CD6-9D8B4595A5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5125d577b6919f81dd92ff36498af313f9b3e36d","datavalue":{"value":{"entity-type":"item","numeric-id":4398765,"id":"Q4398765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f49685b1db59f12c103595fa62170dc3f04e456","datavalue":{"value":{"amount":"+0.8596834","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$DE37C47F-78B2-473D-A394-1EF343D9CC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbfa8a6077f7c9a7a3380ec3f33c7a4bd8a4f542","datavalue":{"value":{"entity-type":"item","numeric-id":5491530,"id":"Q5491530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21c49cff781799f42deea4959a254bdbedd20915","datavalue":{"value":{"amount":"+0.8543038","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$D9A81FE8-80BA-46B9-BC1B-B56713114A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a2a9736d1e1a4e7347aa2b7685b892753a3b863","datavalue":{"value":{"entity-type":"item","numeric-id":3167172,"id":"Q3167172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd2fff4e6e338d20ab8c31fd4a38bb636e47f5b","datavalue":{"value":{"amount":"+0.85334337","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360183$CD4F1161-8F56-4627-B40D-2B1345D5093F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lectures on computer science. Vol. 3: Computability, formal languages, specifications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lectures_on_computer_science._Vol._3:_Computability,_formal_languages,_specifications"}}}}}