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 surenkamos 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čiavimai orų prognozėms. Šis darbas būdavo ilgas ir gan nuobodus. Šiais laikais šias problemas galima automatizuoti 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ą:

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)

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ą:

def paversk_farenheitus_į_celsijus(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_farenheitus_į_celsijus(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 = "temperatūros.txt"
    vidutinė_temperatūra = skaičiuok_vidutinę_temperatūrą(duomenų_failas)
    print(f"Vidutinė temperatūra yra: {vidutinė_temperatūra}")

Itin sudėtingų problemų automatizavimas

Egzistuoja 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ų. Superkompiuteris gali apdoroti šiuos duomenis realiu laiku. Tam naudojami sudėtingi algoritmai simuliuojantys atmosferos dinamiką, vandenynų sroves ir kitus atmosferos reiškinius. Tai leidžia gauti greitesnes ir tikslesnes orų prognozes, 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 kelionė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 padaryti automatizacijos būdu.
2. Sveikųjų skaičių faktorizavimas. Faktorizavimo tikslas rasti duoto skaičiaus pirminius daugiklius. Pirminių skaičių faktorizavimu yra paremtos šiuolaikinės kriptografinės sistemos, pavyzdžiui viešojo rakto kriptosistema 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

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

Skaičiavimo laiko nustatymas

Nori sužinoti kiek ilgai užtruko įvykdyti tavo programą? Pitone tą gali padaryti keletu būdų. Pateikiu vieną iš jų:

# 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}")

Pasirinkto algoritmo įtaka skaičiavimo laikui

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

# Importuojame paketą, leidžiantį dirbti su laiku
import time

def suma(N):
    rezultatas = 0
    # Skaičiuojame rezultatą tiesiogiai sudėdami visus skaičius
    for i in range(1, N + 1):
        rezultatas += i
    return rezultatas


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

# Pasiimame algoritmo vykdymo pradžios laiką
pradžios_laikas = time.time()

print("Suma:", suma(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}")

Įvykdžiau šį kodą savo kompiuteryje, su N=100000000 (100 milijonų), vykdymo trukmė buvo 11,6 sekundės

# Importuojame paketą, leidžiantį dirbti su laiku
import time

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


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

# Pasiimame algoritmo vykdymo pradžios laiką
pradžios_laikas = time.time()

print("Suma:", suma(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}")

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 naudojamo 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ą atminties kiekį reikšmei saugoti. Kai kintamasis taps nebereikalingas ta atmintis bus atlaisvinta. Tai padeda programuotojui susikoncentruoti į efektyvaus algoritmo kūrimą ir nesukti galvos dėl atminties atlaisvinimo.

Kiek atminties užima vienas kintamasis?

Patikrinti kiek atminties užima kintamasis, galima naudojant sys.getsizeof. Štai kodo pavyzdys:

#Importuojame paketą, leidžiantį dirbti su atmintimi
import sys
skaičius = 10
print("Kintamojo užimama atmintis baitais:", sys.getsizeof(skaičius))

Paleidęs kodą pamatysi, jog šis kintamasis užima 28 baitus. Taigi, sveikiesiems skaičiams saugoti pitonui reikės 28 baitų, bet labai dideliems skaičiams saugoti 28 baitų gali ir nepakakti. Pavyzdžiui: skaičiui 1234567890 saugoti pitonas jau naudos 32 baitus. Kitokio tipo kintamiesiems naudojamos atminties kiekis bus kitoks. Štai realiajam 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 sprendžiant dideles ir sudėtingas problemas atminties gali imti ir pristigti. Tad rašant programas svarbu pagalvoti kaip efektyviai naudoti atmintį.

Pasirinkto algoritmo įtaka naudojamos atminties kiekiui

Ankstesniame 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ų, kuriems vykdyti reikės skirtingų atminties kiekių. Paimkime paprastą programą, kuri sudeda keturis skaičius 2 skirtingais būdais.

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

Abi funkcijos gražins tą patį rezultatą. Tačiau suma1 naudoja tik 1 kintamąjį, o suma2 naudoja net 4, tad ir atminties reikės net 4 kartus daugiau.

Atmintis, greitis ir kodo aiškumas

Kiekvienas programuotojas turbūt norėtų, kad jo parašytas kodas veiktų kiek galima greičiau, naudotų kiek galima mažiau atminties, būtų lengvai skaitomas ir keičiamas. Bet sprendžiant realius 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 suprantamas, o norint padaryti pakeitimus reikės labai daug programuotojo pastangų. Tuomet prioritetas gali būti teikimas ir kodo aiškumui. Tai kam skirti prioritetą: greičiui, atminčiai ar aiškumui? Tai priklauso nuo konkretaus uždavinio ir reikalavimų. 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 atspausdinti "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 atspausdinta 5.

Pirmu atveju gali parašyti tokį kodą:

print ("Įvesk skaičių?")
skaičius = int(input())
if skaičius > 10:
   print("Didelis")
else:
   print ("Mažas")

Ar žmogus pateikęs užduotį būtų patenkintas tokiu sprendimu? Sunku pasakyti, nes mes nežinome kas jo manymu yra didelis skaičius. 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 atspausdinti "Didelis", jei skaičius didesnis už 100, arba "Mažas" jei skaičius mažesnis už 100.

Nors uždavinio formuluotė jau aiškesnė, tačiau vis dar nėra pilnai aiški. Kas atsitiktų jei būtų įvestas skaičius 100? Užduoties formuluotė to nepaaiškina. Tad reikėtų ją dar patobulinti. Aiški sąlyga galėtų skambėti šitaip:

Įvedus skaičių programa turi atspausdinti "Didelis", jei skaičius didesnis arba lygus 100, arba "Mažas" jei skaičius mažesnis už 100.

Kaip spręstum antrąjį uždavinį? Galbūt parašytum programą kuri mokėtų sudėti daug skaičių? Bet ar to užtenka? Pavyzdyje nurodyta sudėtis, bet sąlygoje nėra parašyta, jog turi būti skaičiuojam tik sudėtis. Galbūt sąlygos autorius tikisi ir kitų veiksmų. Mes to nežinome, nes sąlyga nėra pakankamai aiški. Gerai suformuluota sąlyga galėtų skambėti šitaip:

Programa turi mokėti suskaičiuoti užrašytą sąlygą. Sąlygoje gali būti naudojamos sudėties, atimties, daugybos ir dalybos veiksmai, gali būti naudojami skliaustai. Pavyzdžiui užrašius "2+3" turi būti atspausdinta 5.

Perteklinės formuluotės

Gera problemos formuluotė neturėtų būti perteklinė. Perteklinė formuluotė nepadeda rasti geresnio sprendimo, bet gali netgi trukdyti įsigilinti į problemą. Pavyzdžiui:

Parašyk programą, kuri skaičiuotų stačiakampio plotą. Programa turi leisti įvesti stačiakampio ilgį ir plotį, o išvesti jo plotą. Formulės darbui su stačiakampiais:
Perimetras: 2 * (ilgis + plotis)
Plotas: ilgis * plotis

Nors šiame pavyzdyje prašoma suskaičiuoti plotą, bet taip pat duota ir perimetro formulė, kuri mums nereikalinga, šiai problemai išspręsti. Tai bereikalingai pailgina sąlygą ir gali sukelti papildomų klausimų kodėl ši formulė čia pateikta.