-
pierwsza maszyna licząca
około roku 1645 francuski matematyk Blaise Pascal konstruuje Pascalinę, zwaną też Arithmetique, wykonującą dodawanie, odejmowanie i operacje ułamkowe (często nieprawidłowo) – urządzenie to jest wymieniane jako jedna z pierwszych maszyn liczących. -
Gottfried Wilhelm Leibinz udoskanala maszynę liczącą Pasquala
Maszyna ta była formą kalkulatora mechanicznego opartego na wcześniejszych konstrukcjach (pascalina Blaise'a Pascala i zegar liczący Wilhelma Schickarda). Była zdolna dododawania, odejmowania, mnożenia, dzielenia i wyprowadzania pierwiastków kwadratowych. -
Krosno tkackie z algorytmem na kartach perforowanych
Joseph Jacquard skonstruował maszynę do tkania, która pozwalała na uzyskanie dowolnego wzoru. Było to pierwsze programowe sterowanie w dziejach techniki. -
Idea maszyny analitycznej sformułowana przez Charlesa Babbage'a
W 1842 roku Charles Babbage, który na podstawie swoich doświadczeń sformułował ideę maszyny analitycznej zdolnej do realizacji złożonych algorytmów matematycznych. Wspierała go Ada Lovelace. Prace Lovelace zawierały opis swoistego języka programowania. Niestety, Babbage nigdy nie zbudował swojego mechanicznego komputera. Programy napisane przez Lovelace zostały przetestowane na modelu maszyny różnicowej wykonanym w XX wieku i okazały się poprawne. -
Pierwsza maszyna opracowująca dane statystyczne
Hermann Hollerith zaprojektował maszynę i algorytm do opracowywania danych statystycznych. -
Nowe pytania i idee dotyczące algorytmów
Matematyk niemiecki
Dawid Hilbert, wśród 23 wyzwań dla matematyków zaczynającego się stulecia,
jako dziesiąty problem sformułował pytanie: czy istnieje algorytm, który dla
dowolnego równania wielomianowego wielu zmiennych o współczynnikach w
liczbach całkowitych znajduje rozwiązanie w liczbach całkowitych? -
Złamanie szyfru Enigmy przez Mariana Rejewskiego, Henryka Zegalskiego i Jerzego Różyckiego
W roku 1932 trzem matematykom M. Rejewskiemu, H. Zegalskiemu i J. Różyckiemu udało się złamać szyfr Enigmy, najważniejszej maszyny szyfrującej
używanej przez hitlerowskie Niemcy. Sukces ten był możliwy
dzięki opracowaniu nowych algorytmów deszyfrujących. Odczytywanie szyfrów nie było proste, bowiem
Niemcy stale udoskonalali maszynę i sposoby szyfrowania. Pod koniec wojny praktycznie cała
korespondencja szyfrowana była odczytywana przez aliantów. Dekryptaż meldunku zajmował jeden do dwóch dni. -
Rozprawa Alana Turinga
W roku 1936 matematyk brytyjski Alan Turing opublikował rozprawę „O liczbach obliczalnych z ich zastosowaniem dla problemu rozstrzygalności”.
Odpowiedział w niej na najważniejsze pytanie, jakie stawiali sobie na początku XX
wieku matematycy i filozofowie matematyki: czy da się stworzyć maszynę, która
będzie rozstrzygać automatycznie, bez udziału człowieka, prawdziwość twierdzeń
matematycznych? Turing w błyskotliwy sposób wykazał, że taka maszyna nigdy
nie powstanie. -
Początek współczesnych koncepcji budowy i uruchamiania komputera
John von Neumann skonstruował program realizujący algorytm sortowania przez scalanie na komputerze EDVAC. -
Przełomowe odkrycie Stevena Cooka
Przełomowym rokiem w naszym pojmowaniu złożoności obliczeniowej był
rok 1971, kiedy to informatyk amerykański Steven Cook wykazał, że problem
spełnialności formuł zdaniowych jest NP-zupełny. W ten sposób stworzył
podwaliny pod bardzo ważną klasę problemów trudnych obliczeniowo, tzw. NPtrudnych,
do której – obok kilku tysięcy problemów kombinatorycznych – należą
takie zagadnienia jak problem komiwojażera czy kolorowanie grafów.
