Ksiazka_ZBIOR_tom1.pdf

z b i ó r w y k ł a d ó w w s z e c h n i c y p o p o ł u d n i o w e j

ISBN 978-83-921270-4-8

tom1

Podstawy algorytmiki.

Zastosowania informatyki

Warszawska Wyższa

Szkoła Informatyki

ul. Lewartowskiego 17

00-169 Warszawa

www.wwsi.edu.pl

Człowiek – najlepsza inwestycja

Projekt współfinansowany ze środków Unii Europejskiej w ramach Europejskiego Funduszu Społecznego

Podstawy algorytmiki.

Zastosowania informatyki

z b i ó r w y k ł a d ó w w s z e c h n i c y p o p o ł u d n i o w e j

tom1

Publikacja współfinansowana ze środków Unii Europejskiej

w ramach Europejskiego Funduszu Społecznego

Podstawy algorytmiki.

Zastosowania informatyki

Człowiek – najlepsza inwestycja

Tom 1.

Podstawy algorytmiki. Zastosowania informatyki

Redaktor merytoryczny: prof. dr hab. Maciej M. Sysło

Redaktor: Magdalena Kopacz

Publikacja opracowana w ramach projektu edukacyjnego Informatyka+

– ponadregionalny program rozwijania kompetencji uczniów szkół ponadgimnazjalnych

w zakresie technologii informacyjno-komunikacyjnych (ICT)

www.informatykaplus.edu.pl

kontakt@informatykaplus.edu.pl

Wydawca:

Warszawska Wyższa Szkoła Informatyki

ul. Lewartowskiego 17, 00-169 Warszawa

www.wwsi.edu.pl

rektorat@wwsi.edu.pl

Wydanie pierwsze

Publikacja nie jest przeznaczona do sprzedaży.

ISBN 978-83-921270-4-8

Projekt graficzny: FRYCZ I WICHA

Wszystkie tabele, rysunki i zdjęcia, jeśli nie zaznaczono inaczej, pochodzą z archiwów autorów lub zostały przez nich opracowane.

< 4 >

Informatyka + – Wszechnica Popołudniowa

< 5 >

Wstęp

podstaWy algorytmiki. ZastosoWania informatyki

Zbiór WykładóW WsZechnicy popołudnioWej

Zgodnie z założeniami, projekt Informatyka+ – ponadregionalny program rozwijania kompetencji uczniów

szkół ponadgimnazjalnych w zakresie technologii informacyjno-komunikacyjnych (ICT) ma na celu podniesie-

nie poziomu kluczowych kompetencji uczniów szkół ponadgimnazjalnych w zakresie informatyki i jej zasto-

sowań, niezbędnych do dalszego kształcenia się na kierunkach informatycznych i technicznych lub podjęcia

zatrudnienia, oraz stworzenie uczniom zdolnym innowacyjnych możliwości rozwijania zainteresowań nauko-

wych w tym zakresie. Program ten jest alternatywną formą kształcenia pozalekcyjnego.

Realizacja projektu zbiegła się w czasie ze światowym kryzysem kształcenia informatycznego. Od

upadku dot.comów na początku tego wieku aż o 50% spadło zainteresowanie studiami informatycznymi

w Stanach Zjednoczonych i podobne tendencje zaobserwowano w Wielkiej Brytanii oraz w innych krajach. Po-

wszechny i łatwy dostęp do najnowszej technologii komputerowej i prostota w opanowaniu jej podstawowych

funkcji doprowadzają młodych użytkowników tej technologii do przekonania, że posiedli jej najważniejsze

tajniki i szkoda czasu na głębsze studia w tym kierunku. Rynek pracy jednak jest w stanie wchłonąć każdą

liczbę wysoko i średnio wykwalifikowanych informatyków i specjalistów z dziedzin pokrewnych.

Projekt Informatyka+ jest formą działań określanych mianem outreach , które są adresowane przez

uczelnie do uczniów i mają na celu głębsze zaprezentowanie, czym jest informatyka, przybliżenie jej zastoso-

wań oraz wskazanie możliwości dalszego kształcenia się w kierunkach związanych z profesjonalnym wyko-

rzystaniem technologii komputerowej i technologii informacyjno-komunikacyjnej. Inicjatywę tę należy uznać

za niezmiernie aktualną i potrzebną, wpisującą się zarówno w myślenie o przyszłości dziedziny informatyka

i o przyszłych karierach młodych Polaków w zawodach informatycznych, jak i rozwoju nowoczesnego pań-

stwa. Szczegółowe informacje o projekcie i jego efektach są zamieszczane na stronie http://www.informatykaplus.

edu.pl/.

Wstęp ............................................................................................................................................................... 5

tendencje W roZWoju informatyki i jej ZastosoWań

Informatyka – klucz do zrozumienia, kariery, dobrobytu, Maciej M. Sysło ........................................................ 9

Czy komputery będą robić biznes, Wojciech Cellary ....................................................................................... 33

Algorytmika Internetu, Krzysztof Diks ............................................................................................................ 45

Jak wnioskują maszyny, Andrzej Szałas .......................................................................................................... 59

Język językowi nie równy, Jan Madey .............................................................................................................. 77

Programowanie współbieżne w informatyce i nie tylko, Marcin Engel ............................................................. 93

Jak informatyka pomaga zajrzeć do wnętrza ludzkiego ciała, Ryszard Tadeusiewicz .....................................111

Naśladowanie żywego mózgu w komputerze, Ryszard Tadeusiewicz ............................................................ 131

Od złamania Enigmy do współczesnej kryptologii, Jerzy Gawinecki ...................................................................... 153

Od abaków do maszyny ENIAC i Internetu, Piotr Sienkiewicz ...........................................................................165

algorytmika i programoWanie

Porządek wśród informacji kluczem do szybkiego wyszukiwania, Maciej M. Sysło ...................................... 187

Czy wszystko można policzyć na komputerze, Maciej M. Sysło .................................................................... 219

Dlaczego możemy się czuć bezpieczni w sieci, czyli o szyfrowaniu informacji, Maciej M. Sysło .................... 227

Znajdowanie najkrótszych dróg oraz najniższych i najkrótszych drzew, Maciej M. Sysło .............................. 249

O relacjach i algorytmach, Zenon Gniazdowski ............................................................................................. 265

Niniejszy zbiór wykładów prowadzonych w ramach Wszechnicy Popołudniowej, stanowiącej jedną z form re-

alizacji projektu, oddajemy przede wszystkim do rąk uczniów. Tom 1 zawiera wykłady z zakresu: Tendencje

w rozwoju informatyki i jej zastosowań oraz Algorytmika i programowanie.

Pierwsza grupa tematów reprezentuje szerokie spektrum zastosowań informatyki w różnych dziedzinach, ta-

kich jak kryptografia, ekonomia i medycyna, oraz wykorzystania metod informatycznych przy rozwiązywaniu

rzeczywistych problemów, jak wnioskowanie i wyszukiwanie informacji w Internecie.

Druga grupa zagadnień stanowi łagodne wprowadzenie do algorytmiki, która jest bazą dla kompute-

rowego rozwiązywania problemów. Przedstawiono podstawowe problemy i możliwie najefektywniejsze algo-

rytmy ich rozwiązywania. Algorytmom towarzyszą odpowiednio dobrane struktury danych, a głównym kryte-

rium doboru problemów i algorytmów jest złożoność obliczeniowa ich rozwiązywania. Omówiono problemy,

które można rozstrzygnąć bardzo efektywnie, a także te, dla których dotychczas nie wymyślono praktycznych

i użytecznych metod rozwiązywania.

Do lektury zamieszczonych tekstów wystarczy znajomość matematyki i informatyki na poziomie szkoły po-

nadgimnazjalnej. Nowe pojęcia są wprowadzane na przykładach i w sposób intuicyjny, umożliwiający nadą-

żanie za tokiem wykładu.

Prof. dr hab. Maciej M. Sysło

Merytoryczny Koordynator

Projektu Informatyka+

Warszawa, jesienią 2011 roku

Tendencje

w rozwoju informatyki

Informatyka – klucz do zrozumienia, kariery, dobrobytu

Czy komputery będą robić biznes

Algorytmika Internetu

Jak wnioskują maszyny

Język językowi nie równy

Programowanie współbieżne w informatyce i nie tylko

Jak informatyka pomaga zajrzeć do wnętrza ludzkiego ciała

Naśladowanie żywego mózgu w komputerze

Od złamania Enigmy do współczesnej kryptologii

Od abaków do maszyny ENIAC i Internetu

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: