# data[].attributes.headline
Што е алгоритам?

# data[].attributes.subject
Што е алгоритам?

# data[].attributes.body
Алгоритам е конечен, јасно дефиниран збир на чекори што опишуваат постапка за решавање на одреден проблем или извршување на одредена задача. Алгоритамот мора да биде:

1. Конечен – мора да заврши по определен број чекори.

2. Јасен и недвосмислен – секој чекор мора да биде прецизно дефиниран.

3. Извршлив – чекорите мора да бидат остварливи во реални услови.

4. Влезно-излезен – треба да прима влезни податоци и да дава излезни резултати.

Алгоритмите се основа на секоја компјутерска програма и се користат во сите области каде што постои потреба од автоматско решавање проблеми.

# data[].attributes.headline
Зошто се важни алгоритмите?

# data[].attributes.subject
Зошто се важни алгоритмите?

# data[].attributes.body
1. Ефикасно решавање на проблеми

Алгоритмите овозможуваат проблемите да се решаваат на структуриран и систематски начин. Наместо хаотично пробување, тие даваат конкретна постапка што води до точно решение.

2. Оптимизација на ресурси

Добро дизајнирани алгоритми трошат помалку време и меморија. Во реални апликации, тоа значи побрзи програми, помалку трошоци и подобра корисничка искуственост.

3. Анализа и споредба

Алгоритмите можат да се анализираат математички (на пример: преку временска и просторна сложеност), што овозможува споредба и избор на најдобро решение за даден проблем.

# data[].attributes.headline
Што е алчен алгоритам?

# data[].attributes.subject
Што е алчен алгоритам?

# data[].attributes.body
Алчниот алгоритам е стратегија за оптимизација каде што на секој чекор се прави најдобриот можен избор во моментот, без да се земат во предвид идните последици

# data[].attributes.headline
Како функционира еден алчен алгоритам?

# data[].attributes.subject
Како функционира еден алчен алгоритам?

# data[].attributes.body
Иницијализација – започнува од некоја почетна состојба.

Избор на најдобра опција – во секој чекор избира што изгледа најдобро во моментот (без да гледа во иднината).

Проверка за крај – ако е решен проблемот, завршува; ако не, повторува со следниот чекор.

Не се враќа назад – одлуките не се менуваат, нема "undo".

# data[].attributes.attachment_link.title
Greedy Algorithms - Algorithms & Data Structures #8

# data[].attributes.headline
Карактеристики 

# data[].attributes.subject
Карактеристики 

# data[].attributes.body
Брз и ефикасен за одреден тип на проблеми

Не секогаш дава оптимално решение.

Дава приближни резултати.

# data[].attributes.headline
Проблем со враќање на кусур

# data[].attributes.subject
Проблем со враќање на кусур

# data[].attributes.body
Која е комплексноста? О(n)

Кое е најоптимално решение?

# data[].attributes.attachment_link.title
Coin Change Problem | Minimum Number of Coins | Dynamic Programming | Geekific

# data[].attributes.headline
Код за проблемот со враќање на кусур

# data[].attributes.subject
Код за проблемот со враќање на кусур

# data[].attributes.body
def min_coins(coins, amount):

dp = [float('inf')] * (amount + 1)

dp[0] = 0

for i in range(1, amount + 1):

for coin in coins:

if coin <= i:

dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

coins = [9, 10, 20, 5]

amount = 20

print(min_coins(coins, amount)) # Излез: 1 (само 20 денари)

# data[].attributes.headline
Проблем со пакување на ранец

# data[].attributes.subject
Проблем со пакување на ранец

# data[].attributes.body
Која е комплексноста? O(n×W)

Кое е најоптималното решение?

# data[].attributes.attachment_link.title
0/1 Knapsack problem | Dynamic Programming

# data[].attributes.headline
Код за проблем со пакување на ранец

# data[].attributes.subject
Код за проблем со пакување на ранец

# data[].attributes.body
# Предмети: (цена, тежина)

items = [

{"price": 10, "weight": 9},

{"price": 7, "weight": 12},

{"price": 1, "weight": 2},

{"price": 3, "weight": 7},

{"price": 2, "weight": 5},

]

# Максимална тежина на ранецот

max_weight = 11

n = len(items)

# DP табела: (n+1) x (max_weight+1)

dp = [[0 for w in range(max_weight + 1)] for i in range(n + 1)]

# Пополнување на DP табелата

for i in range(1, n + 1):

for w in range(1, max_weight + 1):

item = items[i - 1]

if item["weight"] <= w:

dp[i][w] = max(

item["price"] + dp[i - 1][w - item["weight"]],

dp[i - 1][w]

)

else:

dp[i][w] = dp[i - 1][w]

# Оптимална вредност

optimal_value = dp[n][max_weight]

print(f"Максимална добивка: {optimal_value}$")

# Пронајди кои предмети се избрани

w = max_weight

selected_items = []

for i in range(n, 0, -1):

if dp[i][w] != dp[i - 1][w]:

selected_items.append(items[i - 1])

w -= items[i - 1]["weight"]

print("Избрани предмети:")

for item in selected_items:

print(f"- Цена: {item['price']}$, Тежина: {item['weight']}kg")

# data[].attributes.headline
Што е бинарно пребарување?

# data[].attributes.subject
Што е бинарно пребарување?

# data[].attributes.body
Бинарно пребарување е ефикасен алгоритам за наоѓање на одреден елемент во сортирана низа (од најмал кон најголем или обратно). Наместо да проверува секој елемент еден по еден (како линеарното пребарување), бинарното пребарување работи на принципот на половина-половина, односно ја дели низата на два дела со секоја итерација.

# data[].attributes.headline
Како функционира бинарното пребарување?

# data[].attributes.subject
Како функционира бинарното пребарување?

# data[].attributes.body
1.Почетна состојба: Имаме сортирана листа (пример: [2, 4, 6, 8, 10, 12, 14]) и сакаме да провериме дали некој број (на пример 10) постои во таа листа.

Прв чекор: Го земаме средниот елемент. Ако е тоа што го бараме – завршуваме. Ако не е:

Ако елементот што го бараме е помал, продолжуваме да пребаруваме лево (првиот дел).

Ако е поголем, продолжуваме да пребаруваме десно (вториот дел).

2.Секојпат ја преполовуваме низата, сè додека не го најдеме елементот или додека не остане празна низа (тогаш значи дека елементот не постои).

# data[].attributes.headline
Карактеристики

# data[].attributes.subject
Карактеристики

# data[].attributes.body
Пребарување по половина

Сортирање на низата

Комплексноста е O(log n)

# data[].attributes.headline
Сакаме да го најдеме б

# data[].attributes.body
Сакаме да го најдеме бројот 28 користејќи бинарно пребарување.

Прво, ја земаме средината на целата низа. Левата граница е индекс 0, десната е 14, па средниот елемент е на индекс (0 + 14) // 2 = 7. Таму се наоѓа бројот 12. Бидејќи 28 е поголем од 12, го отфрламе левиот дел и пребаруваме во десната половина: од индекс 8 до 14.

Повторно го наоѓаме средниот елемент во новиот интервал: (8 + 14) // 2 = 11. Таму е бројот 25. Повторно, 28 е поголем од 25, па одиме десно – од индекс 12 до 14.

Средниот елемент е (12 + 14) // 2 = 13, а таму е бројот 29. Овојпат, 28 е помал од 29, па пребаруваме во левата половина: од индекс 12 до 12.

Останува само еден елемент – на индекс 12, каде што се наоѓа бројот 28. ✅ Го најдовме!

# data[].attributes.headline
Код за бинарно пребарување

# data[].attributes.subject
Код за бинарно пребарување

# data[].attributes.body
def binary_search(niza, target):

levo = 0

desno = len(niza) - 1

while levo <= desno:

sredina = (levo + desno) // 2

vrednost = niza[sredina]

# Го најдовме бројот

if vrednost == target:

return sredina # Го враќаме индексот

# Ако вредноста е помала, бараме десно

elif vredност < target:

levo = sredina + 1

# Ако вредноста е поголема, бараме лево

else:

desno = sredina - 1

return -1 # Не е пронајден

# data[].attributes.headline
Видео илустрација

# data[].attributes.subject
Видео илустрација

# data[].attributes.body
Видеото нагласува дека изборот помеѓу линеарно и бинарно пребарување зависи од структурата на податоците и специфичните барања на задачата. Додека линеарното пребарување е едноставно и не бара сортирана низа, бинарното пребарување нуди значителна ефикасност кога се работи со големи и сортирани податоци.

# data[].attributes.headline
Линеарно пребарување

# data[].attributes.subject
Линеарно пребарување

# data[].attributes.body
Како функционира: Секој елемент во низата се проверува еден по еден, од почеток до крај, сè додека не се најде целниот елемент или не се заврши низата.

Кога се користи: Кога низата не е сортирана или кога се работи со мали количини на податоци.

Времеска комплексност: O(n), каде што n е бројот на елементи во низата.

# data[].attributes.headline
Табела за споредба

# data[].attributes.subject
Табела за споредба

# data[].attributes.headline
Dijkstra алгоритам за најкраток пат

# data[].attributes.subject
Dijkstra алгоритам за најкраток пат

# data[].attributes.body
Која е компексноста? O(V²)

Кое е најоптималното решение?

# data[].attributes.body
import heapq

def dijkstra(graph, start):

# graph е речник {врв: [(сосед, тежина), ...]}

# start е почетен врв

# растојанија до сите врвови (почетно бесконечност)

distances = {vertex: float('inf') for vertex in graph}

distances[start] = 0

# приоритетна опашка: (растојание, врв)

priority_queue = [(0, start)]

while priority_queue:

current_distance, current_vertex = heapq.heappop(priority_queue)

# Ако имаме подобар запис, прескокни

if current_distance > distances[current_vertex]:

continue

# За секој сосед на тековниот врв

for neighbor, weight in graph[current_vertex]:

distance = current_distance + weight

# Ако најдовме пократок пат

if distance < distances[neighbor]:

distances[neighbor] = distance

heapq.heappush(priority_queue, (distance, neighbor))

return distances