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