[Ανάλυση Αλγορίθμων]Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2018

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[bsp]

Ανέβηκαν τα αποτελέσματα στο elearning -> forum ανακοινώσεων

[Παναγιώτης]

Το εργαστήριο του Δυναμικού προγραμματισμού έγινε? Και αν ναι, υπάρχει κάποιο αρχείο Lab στο elearning να το κάνουμε και εμείς που δεν μπορούμε να ερχόμαστε στο εργαστήριο?

[HAL 9000]

Το εργαστήριο του Δυναμικού προγραμματισμού έγινε? Και αν ναι, υπάρχει κάποιο αρχείο Lab στο elearning να το κάνουμε και εμείς που δεν μπορούμε να ερχόμαστε στο εργαστήριο?

Το 4ο εργαστήριο έχει ανέβει στο ethmmy!

[reservoir dog]

Αν εχει ασχοληθει καποιος με το quiz του lab4 , ειναι ευκολο να ποσταρει ή να στειλει σε pm  τον αλγοριθμο π εγραψε (κυριως για την τμηματοποιηση) ? 

[Παναγιώτης]

Αν εχει ασχοληθει καποιος με το quiz του lab4 , ειναι ευκολο να ποσταρει ή να στειλει σε pm  τον αλγοριθμο π εγραψε (κυριως για την τμηματοποιηση) ? 

Code:

P = [0,1,5,8,9,10,17,17,18,20,21,23,25,27,27,28,29,30,32,34,35,37,38,38,38,40,41,42,43,45,45,46,47,50,51,52,55,56,58,65,65,67]

def cut_cable(P,n):
    c = [0] * (n+1)
    cuts = [(0,0)]*(n+1)
    next_cut = n
    for i in range(0, n+1):
        max_c_i = 0
        max_i = -1
        max_j = -1
        for j in range(0,i):
            if P[i-j] + c[j] > max_c_i:
                max_c_i = P[i-j] + c[j]
                max_i = i
                max_j = j
        c[i] = max_c_i
        cuts[i] = max_i-max_j, max_j
    #print("P[%d] gia %d kai %d" % (max_i, max_i-max_j, max_j))
    #print(cuts)
   
    print("\nTa kopsimata tha ginoun stis theseis")
    while True:
        print("%d," % (cuts[next_cut][0]), end='')
        next_cut = cuts[next_cut][1]
        if next_cut == 0:
            break
    print(" kai to megisto kerdos einai %d" % (c[n]))
    return c[n]

cut_cable(P,41)

[tuboflo]

Ασχοληθηκε κανεις με το dictionary που ζητειται στο τελος του 5ου εργαστηριου ή με τον τροποποιημενο Dijkstra στο τελος του 6ου?

[malappapas]

Βγήκαν τώρα στο e-Learning

Ομάδα 1: 11:00 - 12:10
Ομάδα 2: 12:25 - 13:35
Ομάδα 3: 13:50 - 15:00
Ομάδα 4: 15:15 - 16:25

[Hobo]

Γενικά ξέρουμε κατα πόσο η συνολική εξέταση στο τέλος είναι πιο εύκολη (σε θέματα) απο τις προόδους? Γενικά βγαίνει όμως όλη η ύλη για την εξέταση μόνο? Ας διαφωτίσει κάποιος

[Παναγιώτης]

Ασχοληθηκε κανεις με το dictionary που ζητειται στο τελος του 5ου εργαστηριου ή με τον τροποποιημενο Dijkstra στο τελος του 6ου?

Code:

import datatools
import graphtools
from string import ascii_lowercase as myletters
from copy import deepcopy

def huffman(C, f):
    n = len(C)
    Q = datatools.Heap(C, f)
    for i in range(0, n - 1):
        x = Q.extract_min()
        y = Q.extract_min()
        z = (x, y)
        f[z] = f[x] + f[y]
        Q.insert(z, f[z])
    return Q.extract_min()

def get_tree_codes(tree, codes = {}, prefix = ""):
    if len(tree) == 1:
        codes[tree] = prefix
    else:
        get_tree_codes(tree[0], codes, prefix + "0")
        get_tree_codes(tree[1], codes, prefix + "1")
    return codes

def create_dict(f, message):
    f = dict([(myletters[i], message.count(myletters[i])) for i in range(25)])
    f = {x:y for x,y in f.items() if y != 0}
    f[' '] = message.count(' ')
    return f

def get_tree_with_frequencies(tree, f, freqs = {}):
    if len(tree) == 1:
        freqs[tree] = f[tree]
    else:
        freqs[0], freqs[1] = {}, {}
        get_tree_with_frequencies(tree[0], f, freqs[0])
        get_tree_with_frequencies(tree[1], f, freqs[1])
    return freqs

mydict = 0
message = "this is an example message to be encoded"

mydict = create_dict(mydict,message)
mydict2 = deepcopy(mydict)

res = huffman(list(mydict2.keys()), mydict2)

dict_codes = get_tree_codes(res)

coded_message = ""
for i in range(len(message)):
    coded_message += dict_codes[message[i]]

print("--- Answer 1 ---")
print(mydict)
print()
print("--- Answer 2 ---")
print(res)
print()
print("--- Answer 3 ---")
print(dict_codes)
print()
print("--- Answer 4 ---")
print(coded_message)
print()
print("--- Answer 5 ---")
graphtools.plot_huffman_tree(get_tree_with_frequencies(res, mydict))

[Παναγιώτης]

Ασχοληθηκε κανεις με το dictionary που ζητειται στο τελος του 5ου εργαστηριου ή με τον τροποποιημενο Dijkstra στο τελος του 6ου?

Ο τροποποιημένος Dijkstra φαντάζομαι είμαι κάτι τέτοιο:

Code:

import dijkstra

graph = {
        'directed': True,
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': [
            ('A', 'B', 10),
            ('A', 'C', 3),
            ('B', 'C', 1),
            ('B', 'D', 2),
            ('C', 'D', 8),
            ('C', 'E', 2),
            ('D', 'E', 7),
            ('E', 'B', 4),
            ('E', 'D', 9)
            ]
        }

all_shortest_paths_dj = {}

for i, u in enumerate(graph['vertices']):
    all_shortest_paths_dj[u] = {}
    for j, v in enumerate(graph['vertices']):
        all_shortest_paths_dj[u][v] = dijkstra.dijkstra_path(graph, u, v)

print(all_shortest_paths_dj)

[ReMi0s]

Ασχοληθηκε κανεις με το dictionary που ζητειται στο τελος του 5ου εργαστηριου ή με τον τροποποιημενο Dijkstra στο τελος του 6ου?

Με κάθε επιφύλαξη αυτά που έκανα για τα τεστ δίνονται παρακάτω:
lab 4

Code:

import sys

def max(a,b):
    return a if (a > b) else b
       

def cutrope(price,n):
    if n<=0:
        return 0;
   
    max_val = -sys.maxsize-1
   
    for i in range(0,n):
        max_val=max(max_val,price[i]+cutrope(price,n-i-1));
   
    return max_val
   
   
   
def cutrope2(price,n):
    if n<=0:
        return 0;
    val=[0 for x in range(n)]
    max_val=price[n-1]
   
    for i in range(1,n):
        for j in range (1,n):
            if(n-i-j-1>=0):
                val=price[i]+price[n-i-j-1]
                if val>max_val:
                    max_val=val;
    return max_val   
   
   
price=[1,5,8,9,10,17,17,18,20,21,23,25,27,27,28,29,30,32,34,35,37,38,38,38,40,41,42,43,45,45,46,47,50,51,52,55,56,58,65,65,67]
n=len(price)
print("1: Maximum Obtainable Value is", cutrope(price, 5))
print("2: Maximum Obtainable Value is ", cutrope2(price, 5))
               

lab5

Code:

import huffman

def give_dict(message):
    letter_list=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"," "]
    message_list=list(message)
    
    f={}
    l=len(letter_list)
    for i in range(0,l):
        count=message_list.count(letter_list[i])
        if count>0:
            f[letter_list[i]]=count
    return f
    
def give_coded_message(message,codes):
    message_list=list(message)
    coded_message=""
    for i in range(0,len(message_list)):
        coded_message=coded_message+str(codes[message_list[i]])
        
    return coded_message
    
message = "this is an example message to be encoded"
f={}
f=give_dict(message)


q=huffman.huffman(list(f.keys()),f)
print("Tree\n" + str(q) + "\n")
codes=huffman.get_tree_codes(q,codes = {}, prefix = "")
print("Codes\n" + str(codes))
coded_message=give_coded_message(message,codes)
print("Coded message:\n" + str(coded_message))


tree_with_freq=huffman.get_tree_with_frequencies(q,f,freqs={})
import graphtools
graphtools.plot_huffman_tree(tree_with_freq)

και lab 6

Code:

import graphtools
import dijkstra
import floydwarshall

#MAIN PROGRAM

graph = {
    'directed': True,
    'vertices': ['A', 'B', 'C', 'D', 'E'],
    'edges': [
        ('A', 'B', 10),
        ('A', 'C', 3),
        ('B', 'C', 1),
        ('B', 'D', 2),
        ('C', 'D', 8),
        ('C', 'E', 2),
        ('D', 'E', 7),
        ('E', 'B', 4),
        ('E', 'D', 9)
        ]
    }

all_shortest_paths = floydwarshall.floydwarshall_paths(graph)

for a in range(0, len(D)):
       print("\t".join(str(D[a][b]) for b in range(0, len(D))))

print("Floyd: "+ str(all_shortest_paths['A']['B']))



shortest_paths = {}
for i, u in enumerate(graph['vertices']):
        shortest_paths[u] = {}
        for j, v in enumerate(graph['vertices']):
            shortest_paths[u][v] = dijkstra.dijkstra_path(graph, u, v)
        



print("Djkstra: "+ str(shortest_paths['A']['B']))

if(all_shortest_paths==shortest_paths):
    graphtools.plot_graph(graph, path = all_shortest_paths['A']['B'])
    graphtools.plot_graph(graph, path = shortest_paths['A']['B'])
    print("ALL SHORTEST PATHS ARE EQUAL")
else:
    graphtools.plot_graph(graph, path = all_shortest_paths['B']['E'])
    graphtools.plot_graph(graph, path = shortest_paths['B']['E'])
    print("THEY ARE NOT EQUAL")
    print("Floyd:\n"+str(all_shortest_paths))
    print("Dijkstra:\n"+str(shortest_paths))

[AB_Kingbird]

Γενικά ξέρουμε κατα πόσο η συνολική εξέταση στο τέλος είναι πιο εύκολη (σε θέματα) απο τις προόδους? Γενικά βγαίνει όμως όλη η ύλη για την εξέταση μόνο? Ας διαφωτίσει κάποιος

^ Αυτό. Επίσης ξέρει κανείς αν οι τελικές εξετάσεις θα γίνουν στην Βεργίνα ή στις αίθουσες;

[Frenzyx]

^ Αυτό. Επίσης ξέρει κανείς αν οι τελικές εξετάσεις θα γίνουν στην Βεργίνα ή στις αίθουσες;

Η εξετάσεις στο τέλος θα είναι σε PC όπως οι πρόοδοι, οπότε Βεργίνα θα γίνουν πάλι λογικά. Όσο για την ευκολία, μας είπαν πως τα θέματα θα είναι λίγο πιο εύκολα από τις προόδους, απλά προφανώς θα είναι σε όλη την ύλη. Η εξέταση παρόλα αυτά θα είναι περίπου 1 ώρα και κάτι, οπότε τα θέματα από το κάθε κομμάτι θα είναι πιο λίγα.

[koumanas]

Σήμερα στην 2η πρόοδο, ομάδα 4, η τελευταία άσκηση με το παιχνίδι, στην 1η ερώτηση ρωτούσε πόσα δευτερόλεπτα θα χρειαστεί ή ποσα βήματα θα κάνει (ύψη: 0, 1, 1.8, 3.5);

[JasonTheModel]

Σήμερα στην 2η πρόοδο, ομάδα 4, η τελευταία άσκηση με το παιχνίδι, στην 1η ερώτηση ρωτούσε πόσα δευτερόλεπτα θα χρειαστεί ή ποσα βήματα θα κάνει (ύψη: 0, 1, 1.8, 3.5);

ποσα αλματα