Wykład 1. Czy wszystko można policzyć na komputerze? Przedmiotem wykładu jest łagodne wprowadzenie do analizy pracochłonności algorytmów na tle możliwości komputerów. Istnieją bowiem problemy, których komputery mogą nigdy nie móc rozwiązać, dlatego szczególną uwagę przywiązuje się do możliwie najszybszego wykonywania podstawowych obliczeń, takich np. jak przeszukiwanie zbioru, porządkowanie danych, znajdowanie szczególnych elementów w zbiorach, obliczanie wartości podstawowych funkcji (wielomianu, potęgi). Przedstawione zostaną problemy, dla których są znane algorytmy optymalne (tj. takie, których nie można już przyspieszyć), oraz takie problemy, których nie potrafimy rozwiązywać szybko, nawet z użyciem najszybszych komputerów. Problemy z tej drugiej grupy znajdują zastosowanie w kryptografii. Rozważania będą ilustrowane praktycznymi zastosowaniami omawianych metod.