Antoni Kreczmar

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Antoni Kreczmar
Ilustracja
Data i miejsce urodzenia 1945
Warszawa
Data i miejsce śmierci 1996
Warszawa
Zawód, zajęcie informatyk
Narodowość polska
Alma Mater Uniwersytet Warszawski
Uczelnia Uniwersytet Warszawski
Wydział Wydział Matematyki, Informatyki i Mechaniki
Stanowisko profesor
Rodzice Jerzy Kreczmar
Felicja Kasman
Dzieci Michał Kreczmar, Tomasz Kreczmar
Odznaczenia
Krzyż Kawalerski Orderu Odrodzenia Polski

Antoni Kreczmar (ur. 1945 w Warszawie, zm. 1996 tamże) – polski informatyk i matematyk, doktor habilitowany[1], pracownik naukowy Instytutu Informatyki Uniwersytetu Warszawskiego.

Pochodził z rodziny Kreczmarów, nauczycieli od pokoleń, a później także ludzi teatru i filmu[2]. Był synem Jerzego Kreczmara.

Osiągnięcia naukowe[edytuj | edytuj kod]

W zakresie logiki algorytmicznej[edytuj | edytuj kod]

  • Jego pierwsze badania (rozprawa doktorska) dotyczyły oszacowania zbioru tautologii logiki algorytmicznej. Wykazał, że zbiór ten nie mieści się w żadnej klasie arytmetycznej hierarchii Kleene-Mostowskiego.[Kreczmar 1977a ↓]
  • Udowodnił, że ciało liczb wymiernych jest scharakteryzowane z dokładnością do izomorfizmu przez aksjomaty ciała oraz własność stopu algorytmu Euklidesa [Kreczmar 1977b ↓]. Wynika stąd, że każda prawdziwa własność algorytmiczna dowolnego programu P działającego w jakimś ciele Euklidesowym może być wyprowadzona z aksjomatów uporządkowanego ciała Euklidesowego, tzn. z aksjomatów ciała wzbogaconych o następującą formułę:
(Euc)
którą należy czytać: dla każdych nieujemnych wartości x i y, program(algorytm) Euklidesa kończy obliczenia. A dokładniej, program ujęty w nawiasy {} kończy swoje obliczenia i jego wyniki spełniają formułę x=y następującą po nim. Jest to przykład formuły algorytmicznej. Zauważ, że formuła ta nie jest prawdziwa w dziedzinie liczb rzeczywistych, w dziedzinie odcinków na płaszczyźnie z odejmowaniem odcinków i porównywaniem ich długości, ani w dziedzinie liczb zespolonych.
  • udowodnił, że zbiór własności algorytmicznych prawdziwych w dziedzinie liczb rzeczywistych to formuły dające się wyprowadzić ze schematu aksjomatów liczb formalnie rzeczywistych [Kreczmar 1977b ↓, s. 19].
  • Jest współautorem pierwszej monografii na temat logiki algorytmicznej [Banachowski i in. 1977 ↓].

W zakresie złożoności obliczeniowej[edytuj | edytuj kod]

  • zmodyfikował algorytm Strassena mnożenia macierzy uzyskując znaczne zmniejszenie zapotrzebowania na dodatkowe komórki pamięci roboczej [Kreczmar 1976 ↓] z na (Jak zazwyczaj, przyjmuje się, że mówimy o mnożeniu macierzy o rozmiarach ).
  • po raz pierwszy w Polsce poprowadził wykład ze złożoności obliczeniowej[3],
  • był współautorem polskiego tłumaczenia ważnej dla pokoleń informatyków książki Projektowanie i analiza programów komputerowych autorstwa A. Aho, J. Hopcrofta i J. Ullmana[4],

W zakresie języków programowania obiektowego[edytuj | edytuj kod]

  • Jest autorem running systemu (dzisiaj częściej używa się nazwy maszyna wirtualna) dla języka Loglan'82. Przy tej okazji rozwiązał wiele problemów:
  1. Czy istnieje taki system zarządzania pamięcią obiektów, w którym można usuwać niepotrzebne obiekty w sposób bezpieczny (tzn. bez ryzyka powstania wiszących referencji) i w czasie stałym?
  2. W jaki sposób należy odszukiwać wystąpienie deklarujące dany identyfikator używany w danym miejscu programu?
  3. Czy można zaadaptować (zachować) mechanizm Display Vectora?
  4. Jak ma działać system współprogramów?
Schemat aksjomatu instrukcji kill
Niech x1, ... ,xn będą zmiennymi, n>0, 1≤i≤n. Każda formuła o podanym poniżej schemacie jest twierdzeniem running systemu Kreczmara.
co się czyta: jeżeli na pewien obiekt o wskazuje n zmiennych to po wykonaniu instrukcji kill(xi) wspólną wartością tych zmiennych jest none (oznacza to, że sam obiekt o jest od tej pory niedostępny i może być przez tę samą instrukcję kill bez szkody usunięty). W konsekwencji:
  • nie ma potrzeby powtarzania operacji kill(x1),kill(x2), ...
  • nie występuje zjawisko wiszących referencji,
  • każda próba odniesienia się do atrybutu obiektu, który wcześniej został usunięty zostanie wykryta i spowoduje zgłoszenie wyjątku „reference to none”.
Należy podkreślić, że koszt operacji kill jest stały, niezależny od liczby n wskaźników na usuwany obiekt.
Taki system zarządzania pamięcią obiektów zastosowano tylko raz, w implementacji języka Loglan'82.

System zarządzania obiektami jest pomyślany całościowo, dostarcza operacji:

  • wspomagających powstanie obiektu – new,
  • sprawdzających legalność operacji dostępu do atrybutów obiektu,
  • usuwania obiektu na żądanie,
  • defragmentacji i odśmiecania pamięci obiektowej.

Porównaj sposoby pozbywania się niepotrzebnych obiektów

model A (Loglan'82) Model B (C++ 1986) Model C (Java 1995, Python)
Przed
Na pewien obiekt o wskazują zmienne x1,x2, ..., xn.
Instrukcja      kill(xi)      delete(xi) x1=null;x2=null; ... xn=null;
Po wykonaniu instrukcji gc() obiekt zostanie usunięty.
Po Wszystkie zmienne przyjęły wartość none. Obiekt został usunięty. Obiekt o został usunięty. x ma wartość null. Inne zmienne wskazują na zwolnione pole – jest to groźny błąd – wiszącej referencji. Obiekt został usunięty, pod warunkiem, że nie zapomniano o żadnej zmiennej wskazującej na obiekt o[5].
Koszt Stały (nieduży) Stały (nieduży). Znaczny, zależny od liczby zmiennych wskazujących na obiekt i od łącznego rozmiaru pamięci obiektowej (koszt operacji gc()).
Ryzyko Brak(!).
Próba dostępu do obiektu o podnosi wyjątek reference to none.
Duże prawdopodobieństwo (przy n>1) błędu wiszących referencji
Duże prawdopodobieństwo błędu sprzecznych informacji.
Spore szanse na to, że programista zapomni usunąć, którąś referencję do niepotrzebnego obiektu.
  • Opracował na nowo system zarządzania obiektami współprogramów (ang. coroutines)[Cioni i Kreczmar 1989 ↓, s. 297-308]. Usunął w ten sposób sprzeczności występujące w systemie współprogramów w języku Simula67.
  • Rozwiązał razem z H. Langmaackiem, M. Krause i M. Warpechowskim problem adaptacji mechanizmu Display Vectora dla klasy języków z klasami zagnieżdżanymi i z dziedziczeniem [Kreczmar i in. 1986 ↓, zobacz też Kreczmar i in. 1983 ↓][6].
  • Podał prawidłowe rozwiązanie problemu statycznego wiązania aplikacyjnych wystąpień identyfikatorów z odpowiednią deklaracją [Kreczmar i in. 1983 ↓].
  • Jest współautorem kolejnej (niezrealizowanej) wersji języka Loglan (zobacz Kreczmar, Salwicki i Warpechowski 1990 ↓]).
  • Stworzył running system dla języka Loglan'88.

Inne[edytuj | edytuj kod]

Wypromował 5 doktorantów. Dwóch z nich zostało profesorami.

Został wyróżniony nagrodą państwową 1. stopnia (zespołową) w dziedzinie nauki, za opracowanie i realizację języka programowania obiektowego Loglan'82, [nagroda w roku 1986].

Przyczynił się do rozwoju internetu w Polsce w latach 90. XX wieku[7].

W 1989 był współorganizatorem konferencji Mathematical Foundations of Computer Science w Porąbce [Kreczmar i Mirkowska 1989 ↓].

W latach 1994-1996 był dyrektorem departamentu Informatyki w Ministerstwie Finansów. Zmarł w trakcie pracy nad zadaniem zbudowania systemu POLTAX, informatycznego systemu podatkowego.

Odznaczony pośmiertnie Krzyżem Kawalerskim Orderu Odrodzenia Polski.

Wybrane publikacje[edytuj | edytuj kod]

W jego dorobku publikacyjnym znajdują się m.in.[8]:

  1. [Kreczmar 1977a] Antoni Kreczmar. Effectivity problems of Algorithmic Logic. „Fundamenta Informaticae”, 1977. 
  2. [Kreczmar 1977b] Antoni Kreczmar. Programmability in Fields. „Fundamenta Informaticae”, s. 195-230, 1977. 
  3. [Kreczmar, Cioni 1984] Antoni Kreczmar, Gianna Cioni. Programmed deallocation without dangling reference. „Information Processing Letters”, s. 179-187, 1984. 
  4. [Banachowski, Kreczmar 1989] Lech Banachowski, Antoni Kreczmar: Elementy Analizy Algorytmów. Warszawa: WNT, 1989, s. 197. ISBN 83-204-1147-5.Sprawdź autora:1.
  5. [Banachowski, Kreczmar, Rytter 1987] Lech Banachowski, Antoni Kreczmar, Wojciech Rytter: Analiza Algorytmów i Struktur Danych. Warszawa: WNT, 1987, s. 217. ISBN 83-204-0717-6.
  6. [Banachowski, Kreczmar, Rytter 1991] Lech Banachowski, Antoni Kreczmar, Wojciech Rytter: Analysis of Algorithms and Data Structures. New York: Addison-Wesley, 1991, s. 300. ISBN 0-201-41693-X.
  7. [Loglan 82] W.M. Bartol i in.: Report on the Loglan'82 programming language. Warszawa-Łódź: PWN, 1984, s. 165.Sprawdź autora:1.
  8. [Kreczmar 1976] Antoni Kreczmar: On Memory Requirements of Strassen’s Algorithm. T. Proc. MFCS'76. Berlin: Springer, 1976, s. 404-407, seria: LNCS. ISBN 3-540-07854-1.Sprawdź autora:1.
  9. [Grabowski, Kreczmar 1978] Michał Grabowski, Antoni Kreczmar: Dynamic theories of real and complex numbers. T. Proc. MFCS'78. Berlin: Springer Vlg, 1978, s. 239-249, seria: LNCS 64. ISBN 0-387-08921-7.
  10. [Kreczmar, Oktaba, Ratajczak, Litwiniuk 1983] Antoni Kreczmar, W.M. Bartol, H. Oktaba, A.I. Litwiniuk: Semantics and Implementation of Prefixing at Many Levels. T. proc. Logics of Programs and their Applications. Berlin: Springer Vlg, 1983, s. 45-80, seria: LNCS 148. ISBN 0-387-11981-7.
  11. [Kreczmar i in 1984] Antoni Kreczmar, Manfred Krause, Hans Langmaack, Andrzej Salwicki: Specification and Implementation Problems of Programming Languages Proper for Hierarchical Data Types. T. Rep. 8410. Kiel: Institut fuer Informatik, University of Kiel, 1984.
  12. [Kreczmar 1982] Antoni Kreczmar: The programming language Loglan'82 Basic constructs and facilities. Warszawa: Uniwersytet Warszawski, 1982, s. 66.
  13. [Kreczmar i in. 1986] Antoni Kreczmar, Manfred Krause, Hans Langmaack, Marek Warpechowski: Concatenation of program modules an algebraic approach to the semantics and implementation problems. Berlin: Springer, 1986, s. 134-156, seria: LNCS 208.
  14. [Kreczmar, Salwicki, Warpechowski 1990] Antoni Kreczmar, Andrzej Salwicki, Marek Warpechowski: Loglan'88 – Report on the Programming Language. Berlin: Springer Vlg, 1990, s. 133, seria: LNCS 414. ISBN 0-387-52325-1.
  15. [Cioni,Kreczmar 1989] Gianna Cioni, Antoni Kreczmar: Modules in High Level Programming Languages. T. Advanced Programming Methodologies. London: Academic Press, 1989, s. 247-340. ISBN 0-12-174690-9.
  16. [Cioni,Kreczmar, Vitale 1989] Gianna Cioni, Antoni Kreczmar, Ricardo Vitale: Storage Management. T. Advanced Programming Methodologies. London: Academic Press, 1989, s. 341-366. ISBN 0-12-174690-9.
  17. [Kreczmar, Mirkowska 1989] Antoni Kreczmar, Grażyna Mirkowska: Mathematical Foundations of Computer Science. Berlin: Springer Vlg, 1989, s. 620, seria: LNCS. ISBN 978-3-540-51486-2.
  18. [Kreczmar 1977] Antoni Kreczmar: On finite and infinite computations. T. Proc. FCT'77. Bonn: Springer Vlg, 1977, s. 441-446, seria: LNCS 56. ISBN 0-387-08442-8.
  19. [Kreczmar 1977] Antoni Kreczmar. On infinite sets of polynomial relations. „Bull.Acad.Pol.Sci.Ser.Astr.Math.Phys.”. 25, 1977. PWN. 
  20. [Kreczmar 1979] Antoni Kreczmar: Some historical remarks on algorithmic logic. T. Algorithms in Modern Mathematics and Computer Science. Berlin: Springer Vlg, 1979, s. 999-1000, seria: LNCS. ISBN 0-12-345678-9.
  21. [Banachowski i in.] Lech Banachowski, Antoni Kreczmar, Grażyna Mirkowska, Helena Rasiowa, Andrzej Salwicki: An introduction to Algorithmic Logic – Metamathematical Investigations of Theory of Programs. T. 2: Banach Center Publications. Warszawa: PWN, 1977, s. 7-99, seria: Banach Center Publications. ISBN 123.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Dr hab. Antoni Kreczmar, [w:] baza „Ludzie nauki” portalu Nauka Polska (OPI) [online] [dostęp 2015-12-30].
  2. Zob. rozdział o Kreczmarach w Olgierd Budrewicz: Sagi warszawskie, czyli sensacyjne i powszednie, romantyczne i prozaiczne dzieje dziesięciu wielkich rodów warszawskich. Warszawa: Czytelnik, 1967.zobacz też Jan Kreczmar, Justyna Kreczmarowa, Zbigniew Zapasiewicz, Adam Kreczmar.
  3. W r. 1974 w Instytucie Informatyki UW.
  4. A.V. Aho, J.E. Hopcroft, J.D. Ullman: Projektowanie i analiza programów komputerowych. Warszawa: PWN, 1983.
  5. Sytuacja w Pythonie wymaga dłuższego opisu. Programista może mianowicie niektóre referencje do obiektu o określić jako słabe. Zwalnia go to z obowiązku pamiętania, że takie referencje do obiektu o istnieją. Wystarczy osunąć tylko silne referencje do obiektu, by przy odśmiecaniu obiekt ten został usunięty.
  6. E.W. Dijkstra [E.W. Dijkstra, Recursive programming, Numerische Mathematik 2 (1960) 312–318] opracował mechanizm znany jako Display Vector, który pozwala przyśpieszyć dostęp do wielkości nielokalnych w językach programowania z zagnieżdżaniem procedur np. Algol60, Pascal. Nie było wiadomo, czy mechanizm ten da się zastosować w językach, które mają mechanizmy dziedziczenia bardziej liberalne niż Simula67, np Loglan'82, czy później powstały język Java?
  7. Był delegatem Senatu UW w projekcie NASK w latach 90 XX wieku.
  8. Kreczmar, Antoni (1945-1996). Katalog elektroniczny Biblioteki Narodowej. [dostęp 2017-02-02].

Linki zewnętrzne[edytuj | edytuj kod]