Antoni Kreczmar

Szablon:Naukowiec infobox Antoni Kreczmar (ur. 1945 w Warszawie, zm. 23 października 1996 tamże) – polski informatyk i matematyk, doktor habilitowany, pracownik naukowy Instytutu Informatyki Uniwersytetu Warszawskiego.

Pochodził z rodziny Kreczmarów, nauczycieli od pokoleń, a później także ludzi teatru i filmu. Był synem Jerzego Kreczmara. W roku 1973 obronił rozprawę doktorską Effectivity problems of Algorithmic Logic, promowaną przez prof. Helenę Rasiową. W 1977 napisał pracę "Programmability in fields", przedstawioną później jako rozprawę habilitacyjną na Wydziale Matematyki UW. Spoczywa w grobowcu rodzinnym na cmentarzu Powązkowskim w Warszawie (kw. 190–V–24/25).

Grób Antoniego Kreczmara na warszawskim cmentarzu Powązkowskim

Osiągnięcia naukowe

W zakresie logiki algorytmicznej

• 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.[[[:Szablon:Odn]]]
• Udowodnił, że ciało liczb wymiernych jest scharakteryzowane z dokładnością do izomorfizmu przez aksjomaty ciała oraz własność stopu algorytmu Euklidesa [[[:Szablon:Odn]]]. 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łę:

Szablon:Wzór

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 [[[:Szablon:Odn]]].
• Jest współautorem pierwszej monografii na temat logiki algorytmicznej [[[:Szablon:Odn]]].

W zakresie złożoności obliczeniowej

• zmodyfikował algorytm Strassena mnożenia macierzy uzyskując znaczne zmniejszenie zapotrzebowania na dodatkowe komórki pamięci roboczej [[[:Szablon:Odn]]] z $\frac{11}{3}{n}^2$ na $\frac{2}{3}{n}^2$ (Jak zazwyczaj, przyjmuje się, że mówimy o mnożeniu macierzy o rozmiarach $n\times n$).

• po raz pierwszy w Polsce poprowadził wykład ze złożoności obliczeniowej,

• 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,

• jest współautorem trzech książek o analizie algorytmów
  • Elementy analizy algorytmów [[[:Szablon:Odn]]],
  • Analiza algorytmów i struktur danych [[[:Szablon:Odn]]],
  • Analysis of Algorithms and Data Structures [[[:Szablon:Odn]]]

W zakresie języków programowania obiektowego

• Jest współautorem języka programowania obiektowego Loglan'82 [[[:Szablon:Odn]], Szablon:Odn]

• 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?

• Opracował bezpieczny i efektywny system zarządzania pamięcią obiektów, [[[:Szablon:Odn]], Szablon:Odn], jest to system kompletny, oferujący operacje: tworzenia nowego obiektu i rezerwowania pamięci dla niego, kompresji kopca obiektów, odśmiecania kopca, tj. pamięci obiektowej i przede wszystkim operację kill bezpiecznego usuwania obiektu. Tutaj omówimy jego unikalną cechę wyrażającą się w postaci poniższego schematu:

Schemat aksjomatu instrukcji kill

Niech x₁, ... ,x_n będą zmiennymi, n>0, 1≤i≤n. Każda formuła o podanym poniżej schemacie jest twierdzeniem running systemu Kreczmara.

$(x_1=\dots =x_n\ne none)\Rightarrow [kill(x_i)](x_1=\dots =x_n=none)$

co się czyta: jeżeli na pewien obiekt o wskazuje n zmiennych to po wykonaniu instrukcji kill(x_i) 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(x₁),kill(x₂), ...
• 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.
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)[[[:Szablon:Odn]]]. 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 [[[:Szablon:Odn]], zobacz też Szablon:Odn].
• Podał prawidłowe rozwiązanie problemu statycznego wiązania aplikacyjnych wystąpień identyfikatorów z odpowiednią deklaracją [[[:Szablon:Odn]]].
• Jest współautorem kolejnej (niezrealizowanej) wersji języka Loglan (zobacz Szablon:Odn]).
• Stworzył running system dla języka Loglan'88.

Inne

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.

W 1989 był współorganizatorem konferencji Mathematical Foundations of Computer Science w Porąbce [[[:Szablon:Odn]]].

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

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

1. [Kreczmar 1977a] Szablon:Cytuj pismo
2. [Kreczmar 1977b] Szablon:Cytuj pismo
3. [Kreczmar, Cioni 1984] Szablon:Cytuj pismo
4. [Banachowski, Kreczmar 1989] Szablon:Cytuj książkę
5. [Banachowski, Kreczmar, Rytter 1987] Szablon:Cytuj książkę
6. [Banachowski, Kreczmar, Rytter 1991] Szablon:Cytuj książkę
7. [Loglan 82] Szablon:Cytuj książkę
8. [Kreczmar 1976] Szablon:Cytuj książkę
9. [Grabowski, Kreczmar 1978] Szablon:Cytuj książkę
10. [Kreczmar, Oktaba, Ratajczak, Litwiniuk 1983] Szablon:Cytuj książkę
11. [Kreczmar i in 1984] Szablon:Cytuj książkę
12. [Kreczmar 1982] Szablon:Cytuj książkę
13. [Kreczmar i in. 1986] Szablon:Cytuj książkę
14. [Kreczmar, Salwicki, Warpechowski 1990] Szablon:Cytuj książkę
15. [Cioni,Kreczmar 1989] Szablon:Cytuj książkę
16. [Cioni,Kreczmar, Vitale 1989] Szablon:Cytuj książkę
17. [Kreczmar, Mirkowska 1989] Szablon:Cytuj książkę
18. [Kreczmar 1977] Szablon:Cytuj książkę
19. [Kreczmar 1977] Szablon:Cytuj pismo
20. [Kreczmar 1979] Szablon:Cytuj książkę
21. [Banachowski i in.] Szablon:Cytuj książkę

Zobacz też

• odśmiecanie pamięci

Linki zewnętrzne

• Szablon:Cytuj stronę
• Szablon:Cytuj stronę