Peržiūrėti šaltinį Problemų sprendimo automatizavimas

=== Problemų sprendimo automatizavimas ===
Žmonės nuo senų laikų susiduria su įvairiais sudėtingais uždaviniais. Iki atsirandant kompiuteriams, uždaviniams, kurių sprendimui gauti reikėdavo atlikti daug skaičiavimo operacijų XIX ir XX a. pirmoje pusėje būdavo surenkamaos visos komandos skaičiuotojų, kurie turėdavo atlikti reikiamus skaičiavimus. Tokiu būdu būdavo atliekami sudėtingi skaičiavimai astronomijoje, apskaičiuojamos balistinių raketų trajektorijos, atliekami skaičivimai orų prognozėms. Šis darbas būdavo ilgas ir gan nuobodus. Šiais laikais šias problemas galima automaitzuoti panaudojant kompiuterius.

=== Automatizavimo pavyzdžiai ===
==== Aritmetinės operacijos ====
Turbūt vienas iš paprasčiausių automatizavimo pavyzdžių būtų - aritmetinių skaičiavimų automatizavimas. Parašykime paprastą programą:
<syntaxhighlight lang="python">
print("Įvesk pirmą skaičių")
skaičius1 = int(input())
print("Įvesk antrą skaičių")
skaičius2 = int(input())
sandauga = skaičius1 * skaičius2
print("Skaičių sandauga yra:", sandauga)
</syntaxhighlight>

Tokia paprasta automatizacija leidžia greitai sudauginti du didelius skaičius, išvengiant žmogaus klaidų.

==== Didelio kiekio duomenų apdorojimas ====
Vienas iš dažniausių automatizavimo pritaikymų - didelio kiekio duomenų apdorojimas. Kompiuteriu galima greitai apdoroti didelį kiekį duomenų, kuriuos apdoroti žmogui užtruktų daug laiko. Įsivaizduokime kad turime failą, kur surašytos kiekvienos metų dienos vidutinė temperatūra farenheito skalėje. Mūsų tikslas suskaičiuoti vidutinę metų temperatūrą celsijaus skalėje. Be kompiuterio tektų ilgai ir nuobodžiai atlikti daug veiksmų. Nesunku kažkur ir klaidą padaryti. Tuo tarpu galime viską automatizuoti parašius tokį kodą:

<syntaxhighlight lang="python">
def paversk_fahrenheitus_į_celsijų(temperatūra_farenheitais):
    temperatūra_celsijais = (temperatūra_farenheitais - 32) * 5 / 9
    return temperatūra_celsijais

def skaičiuok_vidutinę_temperatūrą(duomenų_failo_pavadinimas):
    viso_celsijų = 0
    dienų_skaičius = 0

    with open(duomenų_failo_pavadinimas, 'r') as failas:
        for eilutė in failas:
            farenheitai = int(eilutė)
            celsijai = paversk_fahrenheitus_į_celsijų(farenheitai)
            viso_celsijų += celsijai
            dienų_skaičius += 1

    vidutinė_temperatūra = viso_celsijų / dienų_skaičius
    return vidutinė_temperatūra

if __name__ == "__main__":
    duomenų_failas = "temperatures.txt"
    vidutinė_temperatūra = skaičiuok_vidutinę_temperatūrą(duomenų_failas)
    print(f"Vidutinė temperatūra yra: {vidutinė_temperatūra}")
</syntaxhighlight>

==== Itin sudėtingų problemų automatizavimas ====
Egsituoja daug itin sudėtingų problemų, kurių automatizavimui reikalingi superkompiuteriai. Štai keletas pavyzdžių:
1. Orų prognozė ir klimato modeliavimas. Orų prognozės modeliai naudoja didelius duomenų kiekius, gaunamus iš satelitų, radarų ir kitų šaltinių. Superkomiuteris gali apdorti šiuos duomenis realiu laiku. Tam naudojami sudėtingi algoritmai simuliuojantys atmosferos dinamiką, vandenynų sroves ir kitus atmosferos reiškinius. Tai leidžia gauti greitesnses ir tikslesnes orų prognezes, bei pasiruošti galimoms stichinėms nelaimėms.

2. Vaistų kūrimas. Superkompiuteris atlieka automatizuotas simuliacijas ir virtualius eksperimentus su modeliuojamais vaistais. Analizuojamos molekulinės struktūros ir jų tarpusavio sąveika. Taip nustatomos potencialios naujos vaistinės medžiagos ir įvertinamas jų naudingumas.

3. Transporto ir logistikos optimizacija. Superkompiuteriu optimizuojami transporto ir logistikos tinklai. Aviacijoje tai leidžia optimizuoti skrydžių maršrutus ir taip taupyti degalus, bei trumpinti kleionės laiką. Krovinių pervežime tai padeda optimizuoti maršrutus, efektyviai paskirstyti krovinius ir minimizuoti kaštus.

==== Uždaviniai, kuriuos sudėtinga automatizuoti ====
Ne visų problemų sprendimus įmanoma lengvai automatizuoti. Štai du pavyzdžiai:
1. Matematinių teoremų įrodymas. Įrodyti teoremai gali reikėti patikrinti be galo daug įvairių galimybių ir atvejų. Dažnai to neįmanoma padryti automatizacijos būdu.

2. Sveikųjų skaičių faktorizavimas. Faktorizvaimo tikslas rasti duoto skaičiaus pirminius daugiklius. Pirminių skaičių faktorizavimu yra paremtos šiuolaikinės kriptografinės sistemos, pavyzdžiui RSA. Nors egzistuoja skaičių faktorizavimo algoritmai, tačiau faktorizuoti itin didelius skaičius, naudojamus kriptografijoje net ir galingais kompiuteriais užtrunka labai ilgai. Pavyzdžiui RSA dažnai galima sutikti raktus, kurie yra 2048 bitų ilgio sveikasis skaičius. Faktorizuoti tokį skaičių net ir galingu superkompiuteriu, gali užtrukti tūkstančius metų.

=== Skaičiavimo laikas ===
Vienas svarbiausių metrikų programavime yra programos vykdymo laikas. Vykdymo laiką tiesiogiai įtakoja naudojamų skaičiavimų sudėtingumas, duomenų kiekiai, bei naudojamo kompiuterio galia.

==== Skaičiavimo laiko nustatymas ====
Nori sužinoti kiek ilgai užtruko įvykdyti tavo programą? Pitone tą galime padaryti keletu būdų. Pateiksime vieną iš jų

<syntaxhighlight lang="python">
#Importuojame paketą, leidžiantį dirbti su laiku
import time

#Pasiimimame algortimo vykdymo pradžios laiką
pradžios_laikas = time.time()

# Čia įrašome kodą, kurio vykdymo trukmę norime matuoti

#Pasiimame vykdymo pabaigos laiką
pabaigos_laikas = time.time()

#Paskaičiuojame vykdymo pradžios ir pabaigos laikus. Tai ir bus mūsų vykdymo laikas 
vykdymo_laikas = pabaigos_laikas - pradžios_laikas
print(f"Vykdymo laikas sekundėmis: {vykdymo_laikas:.6f}")
</syntaxhighlight>

==== Pasirinkto algoritmo įtaka skaičiavimo laikui ====
Dažnai tą patį uždavinį galima spręsti ne vienu skirtingu būdu. Skaykime mums reikia suskaičiuoti visų skaičių nuo 1 iki N sumą. Tą padarysime dviem skirtingais būdais ir pamatuosime vykdymo laikus:

<syntaxhighlight lang="python">
#Importuojame paketą, leidžiantį dirbti su laiku
import time

def suma1(N):
    result = 0
    #Skai2iuojame rezultatą tiesiogiai sudedami visus skaičius
    for i in range(1, N + 1):
        result += i
    return result


print ("Įvesk N")
N = int(input())



#Pasiimimame algortimo vykdymo pradžios laiką
pradžios_laikas = time.time()

print("Suma:", suma1(N))

#Pasiimame vykdymo pabaigos laiką
pabaigos_laikas = time.time()

#Paskaičiuojame vykdymo pradžios ir pabaigos laikus. Tai ir bus mūsų vykdymo laikas 
vykdymo_laikas = pabaigos_laikas - pradžios_laikas
print(f"Vykdymo laikas sekundėmis: {vykdymo_laikas:.6f}")
</syntaxhighlight>
Įvykdžiau šį kodą savo kompiuteryje, su N=100000000 (100 milijonų), vykdymo trukmė buvo 11,6 sekundės

<syntaxhighlight lang="python">
#Importuojame paketą, leidžiantį dirbti su laiku
import time

def suma2(N):
    #Pasinaudojame matematine formule
    return N * (N + 1) // 2


print ("Įvesk N")
N = int(input())



#Pasiimimame algortimo vykdymo pradžios laiką
pradžios_laikas = time.time()

print("Suma:", suma2(N))

#Pasiimame vykdymo pabaigos laiką
pabaigos_laikas = time.time()

#Paskaičiuojame vykdymo pradžios ir pabaigos laikus. Tai ir bus mūsų vykdymo laikas 
vykdymo_laikas = pabaigos_laikas - pradžios_laikas
print(f"Vykdymo laikas sekundėmis: {vykdymo_laikas:.6f}")
</syntaxhighlight>

Dabar su N=100000000, vykdymo laikas tebuvo 0,001132 sekundės. Gali išbandyti abu kodo atvejus. Pamatysi, jog jų atsakymai bus vienodi, o vykdymo laikas skirsis daug kartų. Nors vykdymo greitis priklausys nuo konkretaus kompiuterio ir gali gauti kitokią trukmę, nei gavau aš, bet antrasis algoritmas visada bus greitesnis, nepriklausomai nuo nauodjamao kompiuterio.

=== Atmintis ===
Tam kad galėtų įvykdyti tavo parašytą programą kompiuteris turės naudoti operacinę atmintį laikyti vykdomam kodui, bei kintamiesiems.
Pitonas turi automatinę atminties valdymo sistemą. Ši sistema pasirūpina, kad būtų išskirta reikiama atmintis, programai vykdyti ir kad ta atmintis būtų atlaisvinta, kai programai jos nebereikia. Kai sukuriame naują kintamąjį ar objektą pitonas išskirs reikiamą atmities kiekį reikšmei saugoti. Kai kintamasis taps nebereikalingas ta atmintis bus atlaivinta. Tai padeda programuotojui susikoncentruoti į efektyvaus algortimo kūrimą ir nesukti galvos dėl atminties atlaisivinimo.

==== Kiek atminties užima vienas kintamasis? ====
Patikrinti kiek atminties užima kintamasis, galima naudojant <code>sys.getsizeof</code>. Štai kodo pavyzdys:
<syntaxhighlight lang="python">
#Importuojame paketą, leidžiantį dirbti su atmintimi
import sys
skaičius = 10
print("Kintamojo užimama atmitis baitais:",sys.getsizeof(skaičius))
</syntaxhighlight>
Jei naudoji Paleidęs kodą pamatysi, jog šis kintamasis užima 28 baitus. Taigi sveikiesiems skaičiams saugoti pitonui reikės 28 baitų, bet labai dideliems sakičiams saugoti 28 baitų gali ir nepakakti. Pavyzdžiui skaičiui 1234567890 saugoti pitonas jau naudos 32 baitus. Kitokio tipo kintamiesiems naudojamos atmities kiekis bus kitoks. Štai reliajam skaičiui saugoti reikės 24 baitų, o tekstui reikiamos atminties kiekis priklausys nuo teksto ilgio.
Dabartinių kompiuterių atmintis pakankamai didelė, tad sprendžiant šioje knygoje esančius uždavinius, greičiausiai neteks susidurti su atminties trūkumu. Tačiau sprandžiant dideles ir sudėtingas problemas atminties gali imti ir pristigti. Tad rašant progrmaas svarbu pagalvoti kaip efektyviai naudoti atmintį.

==== Pasirinkto algoritmo įtaka naudojamos atminties kiekiui ====
Anksteniame pavyzdyje jau matei, kad du skirtingi algoritmai gali išspręsti tą patį uždavinį, o jų veikimo greitis gali smarkiai skirtis. Taip pat ir su atmintimi. Gali būti skirtingų algoritmų, kuriem vykdyti reikės skirtingų atminties kiekių. Paimkime paprastą programą, kuri sudeda keturis skaičius 2 skirtingais būdais.
<syntaxhighlight lang="python">
def suma1 (sk1, sk2, sk3, sk4):
    suma = sk1 + sk2 + sk3 + sk4
    return suma

def suma2 (sk1, sk2, sk3, sk4):
    tarpinė_suma1 = sk1
    tarpinė_suma2 = tarpinė_suma1 + sk2
    tarpinė_suma3 = tarpinė_suma2 + sk3
    suma = tarpinė_suma3 + sk4
    return suma
</syntaxhighlight>
Abi funkcijos gražins tą patį rezultatą. Tačiau <code>suma1</code> naudoja tik 1 kintamąjį, o <code>suma2</code> naudoja net 4, tad ir atminties reikės net 4 kartus daugiau.

==== Atmintis, greitis ir kodo aiškumas ====
Kiekvienas progrmuotojas turbūt norėtų kad jo parašytas kodas veiktų kiek galima greičiau, naudotų kiek galima mažiau atminties ir būtų lengvai skaitomas ir keičiamas. Bet sprendžiant relaius uždavinius to pasiekti gali būti neįmanoma. Gali tekti rinktis ar pasirinkti greitesnį algoritmą, kuris naudoja daugiau atminties ar tą kuris lėtesnis bet taupoma atmintis. Bet gali būti ir taip kad itin greitas ar mažai atminties naudojantis algoritmas bus labai sudėtingas ir sunkiai suprantams, o norint padaryti pakeitimus reikės labai daug programuotojo pastngų. Tuomet prioritetas gli būti teikimas ir kodo aiškumui. Tai ką gi tada prioretizuoti  greitį, atmintį ar aiškumą? Tai priklauso nuo konkretaus uždavinio ir reiklavimų. Mokantis pitono rekomenduoju pirmiausia rašyti tvarkingą ir aiškų kodą. Bet visada pagalvok ar gali kodą parašyt optimalesnį atminties ar greičio atžvilgiu.

=== Problemų formuluotės ===
==== Neaiškios formuluotės ====
Ar galėtum teisingai išspręsti tokius uždavinius su pitonu?:

1. Įvedus skaičių programa turi atspaudinti "Didelis", jei skaičius didelis, arba "Mažas" jei skaičius mažas
2. Programa turi mokėti suskaičiuoti užrašytą sąlygą. Pavyzdžiui užrašius "2+3" turi būti atspaudinta 5.
Pirmu atveju gali galbūt parašyti tokį kodą:
<syntaxhighlight lang="python">
print ("Įvesk skaičių?")
skaičius = int(input())
if skaičius > 10:
   print("Didelis")
else:
   print ("Mažas")
</syntaxhighlight>
Ar žmogus pateikęs užduotį būtų patenkintas tokiu sprendimu? Sunku pasakyti, nes mes nežinome ką jis laiko dideliu skaičiumi. Kaip turėtų būti suformuluota tokio uždavinio sąlygą, kad tokių neaiškumų nebeliktų? Ar tiktų toks formulavimas?:
Įvedus skaičių programa turi atspaudinti "Didelis", jei skaičius didesnis už 100, arba "Mažas" jei skaičius mažesnis už 100.
Nors uždavinio formuoluotė jau aiškesnė, tačiau vis dar nėra pilnai aiški. Kas atsitiktų jei būtų įvestas skaičius 100? Sąlyga mum to nepaaiškina. Tad reikėtų ją dar patobinti. Aiški sąlyga galėtų skambėti šitaip:
 Įvedus skaičių programa turi atspaudinti "Didelis", jei skaičius didesnis ar ba lygus 100, arba "Mažas" jei skaičius mažesnis už 100.