Алгоритам и програмирање (основни појмови). Увод у програмски језик Python

Неке дефиниције алгоритма:

• прецизно упутство за обављање задатка… са одређеним особинама: дискретност или разложивост; резултативност или делотворност, учинковитост; детерминисаност или одређеност(в. https://petlja.org)
• низ прецизно описаних корака чијим се доследним спровођењем долази до решења проблема (в. Милена Марић. Школогија : из учионице једне београдске гимназије, https://skologija.wordpress.com/)
• коначан низ јасно дефинисаних корака који за дате почетне услове воде до решења или скуп недвосмислених правила у циљу решавања одређеног типа задатка (в. Славимир Стошовић и Милош Косановић. Алгоритми и структуре података : Предавања 1 до 6. Академија техничко-васпитачких струковних студија – Одсек Ниш)

Стари, већ познати примери алгоритама:

• кухињски рецепти (кох, шубарице, чупавци, супа, прженице)
• математички алгоритми:
  • сабирање, одузимање, множење и дељење два природна броја у декадном бројном систему (прва 4 разреда основне школе)
  • конструкција углова од 90, 60 и 45 степени (5. разред основне школе)
  • проналажење квадратног корена датог позитивног броја (7. разред основне школе)
  • решавање система 2 линеарне једначине са две непознате (8. разред основне школе)
  • решавање квадратне једначине (2. разред средње школе)
  • сабирање и одузимање два природна броја у бинарном и хексадекадном бројном систему (прва година факултета, Информатика за библиотекаре 1)

Нови примери алгоритама (статистика):

• Алгоритам заокруживања броја на задати број децимала
• Алгоритам одређивања доње и горње егзактне границе броја (мере)
• Оба претходна алгоритма морају најпре да одреде број децимала у запису датог броја, што значи да користе исти помоћни алгоритам за одређивање броја децимала.

Примери програма записаних у програмском језику Python

• исписивање збира два унета броја. Први (неуспешни) покушај (zbir-v1.py) и исправно решење (zbir-v2.py)
• запис једноставног алгоритма за претварање вредности меморијског капацитета:
  • из јединице бајт (B) у јединицу бит (b). Погрешно (tebi-v1а.py) и исправно решење (tebi-v1b.py)
  • из јединице тебибајт (TiB) у јединице гибибајт (GiB), мебибајт (MiB), кибибајт (kiB), бајт (B) и бит (b) на програмском језику Python. Решење са исписивањем у посебном реду (tebi-v2.py) и решење које илуструје 5 начина за исписивање поруке и резултата у истом реду (tebi-v3.py)

Основни појмови у програмирању на примеру програмског језика Python:

• константе (целобројне константе: 8, 1024; константне ниске: 'Unesite prvi sabirak: ', 'Unesite drugi sabirak: ', 'Zbir unetih brojeva je: ')
• променљиве (sabirak1, sabirak2, zbir у програму tebi-v1а.py и tebi-v1b.py; tebi, gibi, mebi, kibi, bajt, bit у програмима tebi-v2.py и tebi-v3.py)
• наредбе:
  • наредба доделе (променљива = израз)
  • позив функције (input() и print()). Све што се уноси са тастатуре као улаз програма, Python третира као текст (ниску).
• коментари:
  • једнолинијски (#)
  • вишелинијски ('''текст између троструких апострофа'''), пре замена за коментар него прави коментар.
• типови података и њихове операције:
  • ниске (str), операција дописивања (+)
  • цели бројеви (int), операције сабирања, одузимања, множења, целобројног количника и остатка, степеновања (+, -, *, //, %, **)
  • вредности појединих типова се могу претворити у одговарајуће вредности другог типа (ниска '25' у број 25 и обрнуто) помоћу функција које се зову исто као и сами типови (енгл. casting):

    broj = int('25') #вредност је цео број 25
niska = str(25) #вредност је ниска '25'

    Иако на први поглед делује да нема разлике, постоји и разлика између интерних репрезентација константи 25 и '25', као и разлика у погледу операција које могу да се изводе над тим константама.
• потпрограми:
  • процедуре. Немају повратну вредност и не могу се користити у оквиру израза, само извршавају одређени низ наредби.
  • функције.
    • Имају (враћају) тачно једну вредност одређеног типа (вредност функције). Вредност функције се може користити у оквиру израза на месту где сме да се користи константа или променљива истог типа:

      ime = 'Pera'
punoIme = ime + ' ' + input('Unesite prezime')
#Корисник уноси са тастатуре 'Mitić'
#Ефекат је исти као да је употребљена наредба
#punoIme = 'Pera' + ' ' + 'Mitić'

  • Python има од потпрограма има само функције, тј. увек постоји нека вредност, макар била и ништа (None). Вредност функције input() је ниска коју је унео корисник. Вредност функције print() је None (дакле, иако је функција, de facto се понаша као процедура).
• изрази
  • константе и променљиве су најпростији изрази, вредност таквих израза једнака је вредности одговарајуће константе или променљиве;
  • позиви функција су такође изрази, вредност таквих израза је вредност функције за улазне аргументе наведене у позиву;
  • сложенији изрази се добијају применом операција над једноставнијим изразима, на пример:

    2 * (x % 4) ** int(input('Unesite ceo izložilac'))
#константа * (променљива % константа) ** позив_фје(позив_фје(константа))

Класе и објекти

Класе и објекти су уопштења појмова тип података и вредност типа података. Вредности константи и променљивих у Python-у се реализују као објекти. Сваки објекат се може једнозначно идентификовати адресом у меморији, има одређена својства и понашање. Као што смо вредности окупљали у одређене типове података (цели бројеви, реални бројеви, ниске, логичке вредности), тако се објекти који имају заједничка својства и понашање окупљају у класе. Класа заправо представља апстрактан опис објекта (својства и понашање), његов прототип и шаблон, док је објекат само конкретан примерак (инстанца) класе.

Сви до сада поменути типови података су класе у Python-у: int, bool, float, str.

Свака класа има један специјалан метод (функцију) која се зове исто као и сама класа, а служи да конструише нови објекат класе. Конструктори се такође користе за привидну конверзију објекта једне класе у објекат друге класе; у ствари, конверзије нема, већ се конструише нов објекат од полазног. Типичан пример је када се уноси цео број са тастатуре помоћу функције input(); ова функција има за резултат ниску са којом не може да се рачуна, па је неопходно од те ниске конструисати цео број позивом конструктора класе int:

ceo_broj = int(input('Unesite ceo broj'))

Овај пример уједно илуструје композицију функција, излаз функције input() је улаз конструктора int().

Атрибути и методи објекта

Својства објекта класе се описују посебним променљивама која се називају атрибути. Уграђене класе којима ћемо се бавити углавном немају атрибуте или нам они нису од значаја, али ако будемо правили сопствене класе, моћи ћемо да дефинишемо атрибуте. На пример, ако бисмо обрађивали резултате неког испита, могли бисмо дефинисати класу Student која би имала атрибуте ime, prezime, indeks, poeni, прва три као објекте класе str, а последњи као објекат класе float. Дакле, један објекат може садржати, као својства, објекте других класа.

Понашање објекта класе се описује помоћу посебних функција које се називају методи и са њима ћемо највише радити. Немогуће је научити све методе чак ни основних класа попут str, а и за оне чија имена упамтимо због честог коришћења, не можемо држати у глави број и редослед њихових аргумената; из тих разлога увек користимо документацију или подсетник.

Ако је obj променљива која садржи неки објекат са атрибутом svojstvo и методом metod(), за приступ атрибуту, односно за позивање метода објекта obj, користи се тзв. тачка-нотација:

print(obj.svojstvo) #ispisujemo svojstvo objekta
obj.metod() #ako metod ne vraća nikakav rezultat, samo ga pozovemo
rezultat = obj.metod() #ako metod vraća rezultat, treba ga sačuvati u promenljivoj

Глобалне функције

Постоје функције које не припадају ниједној класи. Типичан пример су функције за улаз и излаз, input() и print(), а ускоро ћемо упознати и функцију len().

Класа str и њен метод str.find(подниска)

• Ниску замишљамо као низ (уређену колекцију) карактера.
• Дужина ниске (укупан број карактера) може се одредити глобалном функцијом len() која се користи и за одређивање броја елемената других типова колекција (листи, скупова, речника итд.).

  duzina = len('Python') # дужина ниске је 6

• Специјална врста ниске је празна ниска '', ниска која не садржи ниједан карактер и има дужину 0.
• Сваком карактеру ниске се може приступити помоћу назива ниске и његове позиције у оквиру те ниске. Ако је s ниска дужине len(s), дозвољене позиције су растућа листа бројева од 0 до len(s) - 1 (када се низ карактера посматра слева надесно), а такође и опадајућа листа бројева од -1 до -len(s) (када се низ карактера посматра здесна налево). Према томе, s[0] = s[-len(s)] је први карактер ниске слева надесно, односно последњи карактер ниске здесна налево, док је s[len(s)-1] = s[-1] последњи карактер ниске слева надесно, односно први карактер ниске здесна налево. Ненегативна позиција ниске је тачно за len(s) већа од одговарајуће негатине позиције.

  s = 'Python'
duzina = len(s) # дужина ниске је 6
print(s[0]) # print(s[-6]) даје исти резултат: 'P'
print(s[1]) # print(s[-5]) даје исти резултат: 'y'
print(s[2]) # print(s[-4]) даје исти резултат: 't'
print(s[3]) # print(s[-3]) даје исти резултат: 'h'
print(s[4]) # print(s[-2]) даје исти резултат: 'o'
print(s[5]) # print(s[-1]) даје исти резултат: 'n'
  

• Подниском ћемо називати било који повезани део ниске. Подниска којом ниска почиње назива се префикс, подниска којом се ниска завршава називамо суфикс, док подниску која није ни префикс ни суфикс зовемо инфиксом. С друге стране, подниз ниске је било који подскуп карактера ниске уређен на исти начин као у оквиру ниске или пак у обрнутом редоследу.
• Python нема посебан тип података за карактере, већ се карактер третира као подниска дужине 1.
• Издвајање подниски и поднизова се врши посебном техником коју ћемо звати сецкање (на кришке, енгл. slicing). Сецкање се у општем случају записује на следећи начин:

  ниска[почетак:крај:корак]

  Између средњих заграда наведени су цели бројеви који означавају почетну и крајњу позицију подниза, при чему се узастопне позиције разликују за вредност корак. Ако је вредност почетак мања од вредности крај и корак позитиван број, тада израз у средњим заградама заправо представља скраћени запис следећег скупа

  [почетак:крај:корак] = {x | x = почетак + n * корак < крај, n = 0, 1, 2,…} =
= {почетак, почетак + корак, почетак + 2 * корак, …} < крај


  при чему све вредности скупа морају бити строго мање од вредности крај

  На пример, [2:14:3] = {2, 2 + 3, 2 + 2 * 3, 2 + 3 * 3} = {2, 5, 8, 11},
  док 2 + 3 * 4 = 14 не долази у обзир јер није мања од крајње вредности (14), већ јој је једнака.

  Резултат увек садржи карактер на почетној позицији почетак и никад не садржи карактер на крајњој позицији крај. Ниједан од бројева у средњим заградама није обавезно навести и у том случају се примењују подразумеване вредности: 0 за почетак, дужина ниске за крај и 1 за корак.
  Вредности сва три броја могу бити и негативне. Ако је вредност за корак негативна, подниз се формира од карактера са позиција у опадајућем редоследу (здесна налево). Негативне вредности за почетак и крај означавају позицију карактера у односу на десни крај ниске (позиција -1 одговара последњем карактеру, -2 претпоследњем итд.).

• Примери извлачења подниски помоћу опсега

Претрага подниске

• str.find(подниска). Ако се задата подниска налази у оквиру ниске која позива метод, резултат је почетна позицију подниске (цео број већи од нуле или једнак нули); у противном, резултат је -1.

Методи класе string (string methods)

Методи су функције које се могу позивати само из објекта чијој класи припадају (објектни методи), а у појединим случајевима и из саме класе (класни или статички методи). Као и у случају обичних функција, приликом позива се не смеју раздвајати размаком име метода и отворена лева заграда.

Овде наводимо неке најважније објектне методе које може позвати произвољна ниска:

Велика и мала слова

• str.lower(). Резултат је добијен преписивањем ниске која је позвала метод при чему је свако велико слово замењено малим.
• str.upper(). Резултат је добијен преписивањем ниске која је позвала метод при чему је свако мало слово замењено великим.

Префикси и суфикси

• str.endswith(суфикс). Резултат је логичка вредност (True или False) која указује да ли ниска која је позвала метод садржи задати суфикс.
• str.startswith(префикс). Резултат је логичка вредност (True или False) која указује да ли ниска која је позвала метод садржи задати префикс.

Листе (класа list). Петље (for и while)

• Са листом се ради на сличан начин као са ниском:
  • функцијом len() се одређује дужина листе,
  • елементима листе се приступа преко индекса (позитивних и негативних који се разликују од одговарајућих позитивних тачно за дужину листе),
  • а функционише и сецкање као начин издвајања подлисте.
• Кључне разлике су следеће:
  • елемент листе може бити произвољног типа и различити елементи не морају бити истог типа;
  • за разлику од ниске која не може да се мења (не можете променити карактер ниске, једино можете направити нову ниску), листа може да се мења директно на нивоу појединачних елемената (промена вредности елемента, убацивање елемента на произвољну позицију, брисање елемента са произвољне позиције).

Подела ниске и спајање у ниску

Следеће функције омогућавају да се ниска разложи на листу подниски користећи одређени сепаратор, као и да се од листе ниски направи јединствена ниска применом дописивања и евентуалног сепаратора.

• str.join (итерабилна колекција података). Резултат је ниска добијена спајањем (дописивањем) свих чланова задате итерабилне колекције података (обично ниски као чланова), при чему су суседни чланови раздвојени ниском која је позвала метод.
• str.split (сепаратор). Резултат је листа добијена поделом ниске која је позвала метод на листу њених подниски које су у оквиру полазне ниске раздвојене задатим сепаратором.

Претварање ниске у листу карактера

Осим метода str.split, ниска се може разложити на листу карактера и позивом функције list() (конструктора класе list):

s = 'Python'
l = list(s)
print(l) #['P', 'y', 't', 'h', 'o', 'n']

Једноставни алгоритми претраге ниске

• Проблем: испитивање да ли задата ниска s садржи задату ниску t као подниску (s и t су произвољне ниске). Претпоставићемо да немамо на располагању методе попут str.find() и покушаћемо да напишемо своју верзију. Специјални случајеви: ако је дужина ниске мања од дужине ниске, онда је одговор сигурно негативан; у случају када је дужина ниске 1, онда се проблем своди на тражење једног карактера у оквиру ниске.
• испитивање да ли одређени карактер (тј. ниска дужине 1) припада задатој ниски (специјални случај проблема).
• испитивање да ли задата ниска s садржи задату ниску t као подниску ( je произвољне дужине) методом грубе силе.