Page 2 - Informatyka na czasie. Podejście zachłanne w rozwiązywaniu problemów. Podręcznik klasa 3
P. 2

4.  Podejście zachłanne

                                      w rozwiązywaniu

                                      problemów




                                Wiele problemów rozwiązywanych metodami komputerowymi to problemy
                                optymalizacji. Przykładem jest modelowanie jak najbardziej opływowego
                                kształtu samochodu czy ustalanie jak najszybszej trasy przejazdu dla kuriera
                                z przesyłkami. Twój komputer również rozwiązuje takiego typu problemy,
                                np. gdy decyduje, jak rozdzielać czas pracy procesora. Z optymalizacją
                                spotykasz się także w życiu codziennym, np. gdy w sklepie otrzymujesz
                                resztę wydaną najmniejszą możliwą liczbą monet. Kasjer stosuje wtedy
                                tzw. podejście zachłanne. Z tego tematu dowiesz się, na czym ono polega.


                                Cele lekcji

                                „   Dowiesz się, czym są problemy optymalizacyjne.
                                „   Zrozumiesz, na czym polega podejście zachłanne stosowane
                                  do rozwiązywania problemów.
                                „   Zaprogramujesz algorytmy zachłanne znajdujące optymalne rozwiązania
                                  problemu wydawania reszty oraz problemu kinomana.
                                „   Przekonasz się, jak ważny jest dobór odpowiedniego typu danych
                                  w rozwiązaniach problemów, aby uniknąć konsekwencji błędów przybliżeń.
                                „   Nauczysz się stosować tablice równoległe jako struktury danych.

                                4.1.  Problemy optymalizacyjne. Algorytm zachłanny

                                O optymalizacji można mówić w różnych sytuacjach. Na przykład
             Warto wiedzieć
           Przy masowej produkcji   w ofercie warsztatu wulkanizacyjnego znajdziemy usługę optymalizacji
           zmniejszenie ilości   kół. Polega ona na takim nałożeniu opony na felgę, by siły odśrodkowe
           odpadów choćby       podczas kręcenia się koła działały najkorzystniej i zapewniały jego
           o kilka procent daje
           czasami wielomilionowe   prawidłową pracę.
           oszczędności, a także   Warsztaty stolarskie starają się, by odpadu produkcyjnego było moż-
           znacznie redukuje wpływ   liwie jak najmniej, a liczba wykonanych mebli jak największa. Podobnie
           przemysłu na środowisko.
                                firmy szyjące ubrania dbają o to, by jak najmniej materiału marnować
                                na ścinki.
                                  W dietetyce mówi się o optymalizacji diety, czyli układaniu indywi-
                                dualnych planów żywieniowych według zadanych proporcji składni-
                                ków odżywczych (białka, węglowodanów, tłuszczów) oraz oczekiwanej
                                liczby kalorii.
           Problem optymalizacyjny  Wymienione przykłady są właśnie problemami optymalizacyjnymi,
                                czyli takimi, które wymagają znalezienia jak najlepszego rozwiązania
                                spełniającego określone kryterium (wymaganie).



           62
   1   2   3   4   5   6   7