Spotkanie 43. Anagramy w tekstach

Palindrom (gr. palindromeo – biec z powrotem) - wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.

Spotkanie 42. Przybliżona wartość miejsca zerowego - metoda połowienia przedziałów.

1. Miejsce zerowe.
To argument x, dla którego funkcja przyjmuje wartość zero f(0)=0.

Naszym zadaniem jest znalezienie przybliżonej wartości miejsca zerowego, czyli punktu przecięcia wykresyu z osią Ox. Będziemy posługiwali się metodą "dziel i zwyciężaj".
Jednak aby algorytm działał poprawnie muszą być spełnione warunki:

• funkja f(x), której wykres jest linią ciągła w przedziale [p,q];
• wartość funkcji w punktach p i q są przeciwnych znaków, czyli spełniają warunki f(p) * f(q) < 0;

Spotkanei 41. Obliczanie pola obszaru ograniczonego wykresem funkcji.

Metoda całkowanie numerycznego - zajmuje się obliczaniem pola obszaru ograniczonego wykresem funkcji.

Wyróżniamy metody:

• prostokątów;

• trapezów;

Spotkanei 40. Metody numeryczne.

Spotkanie 39. Sortowanie przez scalanie. Sortowanie szybkie.

1. Sortowanie przez scalanie.
Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .

W tej metodzie wyróżniamy 2 etapy:

1. Podział - faza wykonywana jest rekurencyjnie , polega na podzieleniu ciągu na podciągi zawierające jedną wartość
2. Scalanie - realizowana jest podczas łączenia podciągów i polega na scalaniu ich, z jednoczesnym sortowaniem

Wynika stąd, że głównym celem jest tutaj scalenie dwóch uporządkowanych ciągów w jeden posortowany.

2. Sortowanie szybkie.
Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1].

W każdym kolejnym kroku powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.

Realizacje każdego kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : srodek – T [(lewy+prawy/2].Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego SRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe srodek, a z prawej elementu T[j] większy/równy srodek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu srodek.