Структура информација 1

Ранији назив предмета: Програмирање

Обавештења

[9. X 2022, 20:27] Од школске 2022/2023. године се претпоставља да сви студенти који поново слушају неки од информатичких предмета задржавају раније остварене предиспитне обавезе (ПО) и не треба да се јављају предметном наставнику да би то потврдили. Само студенти који не желе да задрже неке или све ПО, већ им је намера да понове одређени тест или семинарски рад, морају да се јаве на адресу misko at fil_bg_ac_rs до 17. X 2022. године и прецизно назначе шта од ПО понављају.

Стара обавештења

Основне информације

Наставни план и програм

Литература:

  1. Krstev, Cvetana. Materijali za predmet Struktura informacija 1
    • Algoritmi i programiranje (MATF ili FIL)
    • Kontrolne strukture (MATF ili FIL)
    • Nizovi (MATF ili FIL)
    • Predstavljanje brojeva za potrebe računanja (MATF ili FIL)
  2. Miloš A. Kovačević. Osnove programiranja u Pajtonu. Akademska misao. Beograd, 2017.
    На сајту аутора на Грађевинском факултету Универзитета у Београду доступно је 2. nedovršeno PDF izdanje sa NumPy-em, а папирно издање књиге може се позајмити у УБСМ-у.
    У обзир долазе одломци из првих 10 поглавља књиге, посебно поглавља 1–5 и поглавље 7.
  3. Миодраг Живковић и Весна Маринковић. Алгоритми и структуре података : материјал са предавања. Математички факултет. Београд (прве три главе: Увод, Структуре података, Сортирање, стр. 5–79).
  4. Eric Freeman. Um caruje: Naučite Programiranje. Mikro knjiga, 2018. Може се позајмити у УБСМ-у.
  5. Корисни сајтови:

Предиспитне обавезе

  • Распоред тестова и резултати тестова
  • Тест 1 (20 поена)
    • Термин: субота 19. XI 2022. године, Сала 11 у 11.30.
    • Градиво за студенте који предмет слушају у школској 2022/2023. години и касније:
      • Анализа рада програма на језику Python који користи:
        • основне уграђене типове int, float и str. Посебно обратити пажњу на методе класе str и форматиране (f-)ниске;
        • уграђене функције за улаз и излаз (input() и print()); посебно обратити пажњу на конверзију типова (ниска у број и обрнуто помоћу функција int(), float(), str()), као и на подешавање режима исписивања (параметри sep и end);
        • контролне структуре (наредбе if, for, while и break);
        • листе и опсеге, тј. објекте типа list, range; посебно обратити пажњу на креирање и допуњавање листе (list.append() и range()), приступ појединачним елементима (индексирање), издвајање подлиста са истим или обрнутим редоследом елемената (сецкање или slicing) и конверзију ниске у листу (str.split()) и обратно (str.join());
      • Градиво за студенте који су предмет слушали у школској 2021/2022. години и раније:
        • Кодирање бројева за потребе рачунања: природни бинарни код декадних цифара (8421), 2421, вишак 3. Особине ових кодова. Кодирање целих бројева: цели бројеви у бинарном систему.
        • Непотпуни комплемент, потпуни комплемент – рачунање.
        • Представљање реалних бројева у покретном и у непокретном зарезу. IEEE binary32 формат.
        • BCD. Рачунање са бројевима у BCD запису (8421 код и код вишак 3).
  • Тест 2 (20 поена)
    • Термин: субота 17. XII 2022. године, Сала 11 у 13.00.
    • Градиво: накнадно

Испит

  • Писмени испит (мин. 20 поена, макс. 50 поена)
    • Градиво: накнадно

Предавања

Рад на часу

  • Уколико каталог C:\g3\si1 не постоји, студент је дужан да га креира. У тај каталог студент снима све датотеке које креира током часа.
  • На почетку сваког часа студенти покрећу окружење у коме могу тестирати програме на језику Python и то окружење је активно све време.

Алгоритам и програмирање (основни појмови). Увод у програмски језик 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)
  • Пример (Python): запис једноставног алгоритма за претварање вредности меморијског капацитета:
    • из јединице бајт (B) у јединицу бит (b). Погрешно (tebi-v1а.py) и исправно решење (tebi-v1b.py)
    • из јединице тебибајт (TiB) у јединице гибибајт (GiB), мебибајт (MiB), кибибајт (kiB), бајт (B) и бит (b) на програмском језику Python. Решење са исписивањем у посебном реду (tebi-v2.py) и решење које илуструје 5 начина за исписивање поруке и резултата у истом реду (tebi-v3.py)
  • Основни појмови у програмирању:
    • константе (8 и 1024)
    • променљиве
    • наредбе:
      • наредба доделе (променљива = израз)
      • позив функције (input() и print()). Све што се уноси са тастатуре као улаз програма, Python третира као текст (ниску).
    • коментари:
      • једнолинијски (#)
      • вишелинијски ('''текст између троструких апострофа'''), пре замена за коментар него прави коментар.
    • типови података и њихове операције:
      • ниске (str), операција дописивања (+)
      • цели бројеви (int), операције сабирања, одузимања, множења, целобројног количника и остатка, степеновања (+, -, *, //, %, **)
      • вредности појединих типова се могу претворити у одговарајуће вредности другог типа (ниска '25' у број 25 и обрнуто) помоћу функција које се зову исто као и сами типови:
        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 се понаша као процедура).

Класе и објекти. Класа str и њен метод . Глобалне функције

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

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

  • 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.find() и покушаћемо да напишемо своју верзију.
  • Прва верзија алгоритма и програма само испитује да ли одређени карактер (тј. ниску дужине 1) припада задатој ниски (као подниска), док друга верзија тражи у оквиру неке ниске задату ниску произвољне дужине.