Wprowadzenie do algorytmiki - wyszukiwanie+i+porzadkowanie+informacji.pdf - Algorytmy - uchym

Wszechnica Poranna:

Algorytmika i programowanie

Wprowadzenie do algorytmiki

i programowania – wyszukiwanie

i porządkowanie informacji

Maciej M Sysło

Człowiek – najlepsza inwestycja

Rodzaj zajęć: Wszechnica Poranna

Tytuł: Wprowadzenie do algorytmiki i programowania

— wyszukiwanie i porządkowanie informacji

Autor: prof. dr hab. Maciej M Sysło

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

Zeszyt dydaktyczny opracowany 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

Projekt graficzny: FRYCZ I WICHA

Warszawa 2009

Publikacja nie jest przeznaczona do sprzedaży.

Wyszukiwanie

i porządkowanie informacji

Maciej M. Sysło

Uniwersytet Wrocławski, UMK w Toruniu

syslo@ii.uni.wroc.pl, syslo@mat.uni.torun.pl

< 2 >

Informatyka+

Streszczenie

Te zajęcia są wprowadzeniem do algorytmiki i programowania. Na przykładach bar-

dzo prostych problemów, takich jak: znajdowanie największego i/lub najmniejszego

elementu w ciągu, wyłanianie zwycięzcy i drugiego zawodnika w turnieju, porządko-

wanie ciągu liczby oraz poszukiwanie elementów w zbiorach nieuporządkowanych

i uporządkowanych, przedstawione jest podejście do rozwiązywania problemów

w postaci algorytmów i do ich komputerowej implementacji w języku Pascal lub C++.

Omawiane są m.in. specyfikacja problemu, schematy blokowe algorytmów, podsta-

wowe struktury danych (ciąg i tablica) oraz pracochłonność (złożoność) algorytmów.

Na warsztatach zostają wprowadzone podstawowe instrukcje języka programo-

wania (iteracyjna i warunkowa oraz procedura i funkcja niestandardowa), wystar-

czające do zaprogramowania i uruchomienia komputerowych realizacji algorytmów

omówionych na wykładzie. Wykorzystywane jest oprogramowanie edukacyjne, uła-

twiające zrozumienie działania algorytmów i umożliwiające wykonywanie ekspery-

mentów z algorytmami bez konieczności ich programowania. Przytoczono ciekawe

przykłady zastosowań omawianych zagadnień.

Rozważania są prowadzone na elementarnym poziomie i do ich wysłuchania oraz

wzięcia udziału w warsztatach wystarczy znajomość informatyki wyniesiona z gim-

nazjum. Te zajęcia są adresowane do wszystkich uczniów w szkołach ponadgimna-

zjalnych, zgodnie bowiem z nową podstawą programową, kształceniem umiejętno-

ści algorytmicznego rozwiązywania problemów mają być objęci wszyscy uczniowie.

Spis treści

1. Algorytm, algorytmika i algorytmiczne rozwiązywanie problemów

2. Pierwszy algorytm – przeszukiwanie zbioru

3. Kompletowanie podium zwycięzców turnieju

4. Jednoczesne znajdowanie najmniejszego i największego elementu

5. Porządkowanie przez wybór – iteracja algorytmu

6. Poszukiwanie informacji w zbiorze

6.1. Poszukiwanie elementu w zbiorze nieuporządkowanym

6.2. Poszukiwanie elementu w zbiorze uporządkowanym

Zakończenie

Literatura

> Wyszukiwanie i porządkowanie informacji

< 3 >

1 AlgorytM, AlgorytMikA

i AlgorytMiczne rozWiązyWAnie probleMóW

Ten rozdział jest krótkim wprowadzeniem do zajęć w module „Algorytmika

i programowanie”. Krótko wyjaśniamy w nim podstawowe pojęcia oraz stoso-

wane na zajęciach podejście do rozwiązywania problemów z pomocą kompu-

tera.

jak i będący jedynie działaniem umysłu, jest wykonywany według jakiegoś

przepisu postępowania, którego nie zawsze jesteśmy nawet świadomi. Wiele

naszych czynności potrafimy wyabstrahować i podać w postaci precyzyjnego

opisu, ale w bardzo wielu przypadkach nie potrafimy nawet powtórzyć, jak to

się dzieje lub jak to się stało 1 .

Nie wszystkie postępowania z naszego otoczenia, nazywane algorytma-

mi, są ściśle związane z komputerami i nie wszystkie przepisy działań można

uznać za algorytmy w znaczeniu informatycznym. Na przykład nie są nimi na

ogół przepisy kulinarne, chociaż odwołuje się do nich David Harel w swoim fun-

damentalnym dziele o algorytmach i algorytmice [5]. Otóż przepis np. na spo-

rządzenie „ciągutki z wiśniami”, którą zachwycała się Alicja w Krainie Czarów,

nie jest algorytmem, gdyż nie ma dwóch osób, które na jego podstawie, dyspo-

nując tymi samymi produktami, zrobiłyby taką samą, czyli jednakowo smaku-

jącą ciągutkę. Nie może być bowiem algorytmem przepis, który dla identycz-

nych danych daje różne wyniki w dwóch różnych wykonaniach, jak to najczę-

ściej bywa w przypadku robienia potraw według „algorytmów kulinarnych”.

Algorytm

Powszechnie przyjmuje się, że algorytm jest opisem krok po kroku rozwiązania

postawionego problemu lub sposobu osiągnięcia jakiegoś celu. To pojęcie wy-

wodzi się z matematyki i informatyki – za pierwszy algorytm uznaje się bowiem

algorytm Euklidesa, podany ponad 2300 lat temu. W ostatnich latach algorytm

stał się bardzo popularnym synonimem przepisu lub instrukcji postępowania.

W szkole, algorytm pojawia się po raz pierwszy na lekcjach matematyki już

w szkole podstawowej, na przykład jako algorytm pisemnego dodawania dwóch

liczb, wiele klas wcześniej, zanim staje się przedmiotem zajęć informatycznych.

O znaczeniu algorytmów w informatyce może świadczyć następujące okre-

ślenie, przyjmowane za definicję informatyki:

Algorytmika

Algorytmika to dział informatyki, zajmujący się różnymi aspektami tworzenia

i analizowania algorytmów, przede wszystkim w odniesieniu do ich roli jako

precyzyjnego opisu postępowania, mającego na celu znalezienie rozwiązania

postawionego problemu. Algorytm może być wykonywany przez człowieka,

przez komputer lub w inny sposób, np. przez specjalnie dla niego zbudowane

urządzenie. W ostatnich latach postęp w rozwoju komputerów i informatyki był

nierozerwalnie związany z rozwojem coraz doskonalszych algorytmów.

Informatyka jest dziedziną zajmującą się rozwiązywaniem problemów

z wykorzystaniem komputerów. O znaczeniu algorytmów w informatyce może

świadczyć fakt, że każdy program komputerowy działa zgodnie z jakimś algo-

rytmem, a więc zanim zadamy komputerowi nowe zadanie do wykonania po-

winniśmy umieć „wytłumaczyć” mu dokładnie, co ma robić. Bardzo trafnie to

sformułował Donald E. Knuth, jeden z najznakomitszych, żyjących informaty-

ków:

informatyka jest dziedziną wiedzy i działalności

zajmującą się algorytmami

W tej definicji informatyki nie ma dużej przesady, gdyż zawarte są w niej po-

średnio inne pojęcia stosowane do definiowania informatyki: komputery – jako

urządzenia wykonujące odpowiednio dla nich zapisane algorytmy (czyli nieja-

ko wprawiane w ruch algorytmami); informacja – jako materiał przetwarzany

i produkowany przez komputery; programowanie – jako zespół metod i środ-

ków (np. języków i systemów użytkowych) do zapisywania algorytmów w po-

staci programów.

Położenie nacisku w poznawaniu informatyki na algorytmy jest jeszcze uza-

sadnione tym, że zarówno konstrukcje komputerów, jak i ich oprogramowanie

bardzo szybko się starzeją, natomiast podstawy stosowania komputerów, któ-

re są przedmiotem zainteresowań algorytmiki, zmieniają się bardzo powoli,

a niektóre z nich w ogóle nie ulegają zmianie.

Algorytmy, zwłaszcza w swoim popularnym znaczeniu, występują wszędzie

wokół nas – niemal każdy ruch człowieka, zarówno angażujący jego mięśnie,

1 Interesująco ujął to J. Nievergelt w artykule [7] – Jest tak, jakby na przykład stono-

ga chciała wyjaśnić, w jakiej kolejności wprawia w ruch swoje nogi, ale z przerażeniem

stwierdza, że nie może iść dalej.

Wprowadzenie do algorytmiki - wyszukiwanie+i+porzadkowanie+informacji.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: