THMMY.gr

Μαθήματα Βασικού Κύκλου => Ανάλυση και Σχεδιασμός Αλγορίθμων => Topic started by: Don on February 22, 2021, 03:43:41 am



Title: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Don on February 22, 2021, 03:43:41 am
Topic για απορίες σε ασκήσεις του μαθήματος.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 09, 2021, 13:22:55 pm
Απορίες σε παλιά θέματα εδώ (https://www.thmmy.gr/smf/index.php?topic=74674.0) Η συζήτηση μεταφέρθηκε εκεί.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 11, 2021, 09:52:53 am
Code:
def load_polygons(i, M = 50000):
    for k  in range(M):
        pass
def partial_sort(A):
    n = len(A)
    for i in range(n - 1):
        if A[i] > A[i + 1]:
            A[i], A[i + 1] = A[i + 1], A[i]
            load_polygons(i) #Θ(M)
Μπορεί κάποιος να μου εξηγήσει γιατί η πιθανότητα να μην μπούμε στην if είναι 1/(i + 2) ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 11, 2021, 11:26:46 am
εχει να κανει με το οτι μεχρι το i στοιχειο, ο πινακας θα ναι sorted. οποτε ειναι η πιθανοτητα να ειναι μεγαλύτερο απο ολα τα στοιχεια μεχρι και το i , και αυτο χαλαει την ανεξαρτησια των Χi. Εχω και 2 πριντσκριν απο το εργαστηρι αμα θες, αλλα δεν ξερω πως να τα ανεβασω εδω  :P


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 11, 2021, 11:29:44 am
εχει να κανει με το οτι μεχρι το i στοιχειο, ο πινακας θα ναι sorted. οποτε ειναι η πιθανοτητα να ειναι μεγαλύτερο απο ολα τα στοιχεια μεχρι και το i , και αυτο χαλαει την ανεξαρτησια των Χi. Εχω και 2 πριντσκριν απο το εργαστηρι αμα θες, αλλα δεν ξερω πως να τα ανεβασω εδω  :P
έχω και εγώ αυτά του εργαστηρίου σε πριντσκριν, αλλά δεν το πιάνω.  

Για να ξέρεις  για άλλα φορά πατάς πρόσθετες επιλογές  και browse τα αρχεία σου.

edit βασικά το κατάλαβα τώρα.

2η ερώτηση στο περσινό κουιζ προετειμασίας  αυτό με τα αυτοκίνητα και τους φορτιστές είναι εντός για την πρόοδο?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: vgkogkogl on April 11, 2021, 15:04:44 pm
Για μας που δεν παρακολουθούμε τα εργαστήρια, αυτά που είναι ανεβασμένα στο elearning μας καλύπτουν?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 11, 2021, 15:07:07 pm
Για μας που δεν παρακολουθούμε τα εργαστήρια, αυτά που είναι ανεβασμένα στο elearning μας καλύπτουν?
Ναι, πάνω κάτω αυτά που έχει στα Pdf στο elearning έκανε στα εργαστήρια.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: vgkogkogl on April 11, 2021, 15:09:16 pm
Ευχαριστώ πολύ


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 11, 2021, 16:03:26 pm
1ο Quiz Ασκήσεων
ερώτηση 5. πως βρίσκουμε ότι είναι Θ(2^n) ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Thunderlord on April 11, 2021, 22:06:15 pm
1ο Quiz Ασκήσεων
ερώτηση 5. πως βρίσκουμε ότι είναι Θ(2^n) ?


θες μήπως να ανεβάσεις ένα screenshot?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 11, 2021, 22:23:03 pm
θες μήπως να ανεβάσεις ένα screenshot?
https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5166
είναι τα ίδια με τα περσινά.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 12, 2021, 20:57:17 pm
Code:
def add_offset(center, i, offset):
    new_center = [var for var in center]
    new_center[i] = new_center[i] + offset
    return new_center
def optimize(f, center, epsilon, range = None):
    iteration = 1
    i = 0
    num_vars = len(center)
    if range is None:
        range = [1 for _ in center]
    best_value = f(center)
    while max(range) > epsilon:
        points = [add_offset(center, i, - range[i]), add_offset(center, i, range[i])]
        for point in points:
            value = f(point)
            if value < best_value:
                best_value = value
                center = point
        range[i] = 1.0/iteration
        iteration += 1
        if i >= num_vars:
            i = 0
    return center
Μπορεί να μου εξηγήσει κάποιος πως βγαίνει η πολυπλοκότητα τις 2ης συνάρτησης ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 15, 2021, 15:14:17 pm
Στο quiz προτετοιμασιας ερωτηση 7 : ln(n!) = Θ(n lnn ) .
Εγώ το υπολόγισα ως εξης. ln(n!) = ln(1*2*3..*n) = ln1 + ln2 + .. + lnn <= lnn + ln n + .. + ln n = n* ln n.
Αρα ln(n!) <= n* ln n , αρα ln(n!) = O( n ln n). Παιρνουμε σαν σωστο το Θ γιατι ? λογω ανισοισοτητας ?   αμα ειναι κατι Ο δεν είναι και ο ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on April 15, 2021, 15:37:49 pm
Quote
Εγω το βρηκα ω.. Ρωτησα εναν φιλο μου και μου ειπε οτι
n! < nn-1 => lnn! < (n-1) lnn και βγαινει οτι  lnn!/nlnn < c.
Αμα παρεις 2n-1 < n! βρίσκεις ότι c' < lnn!/nlnn
Τωρα τι να πω :P


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 15, 2021, 15:49:05 pm
Στο quiz προτετοιμασιας ερωτηση 7 : ln(n!) = Θ(n lnn ) .
Εγώ το υπολόγισα ως εξης. ln(n!) = ln(1*2*3..*n) = ln1 + ln2 + .. + lnn <= lnn + ln n + .. + ln n = n* ln n.
Αρα ln(n!) <= n* ln n , αρα ln(n!) = O( n ln n). Παιρνουμε σαν σωστο το Θ γιατι ? λογω ανισοισοτητας ?   αμα ειναι κατι Ο δεν είναι και ο ?
Τo Ο είναι είτε Θ είτε o, σε αυτήν την περίπτωση O δεν έχει άρα, είναι Θ ή o, αν ζωγραφήσεις την συνάρτηση ln(n!)/(nlnn) θα δεις για μέγαλα n παει σε σταθερά και όχι στο 0. H σταθερά είναι κάπου ανάμεσα στο 0.5 - 1 αν θυμάμαι καλα.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 15, 2021, 15:54:05 pm
ελυσα το οριο με βαση την προσεγγιση που δινει και βγαινει  lim (ln(n!))/(n ln n) = 1 οποτε ναι ειναι Θ.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 15, 2021, 16:05:29 pm
1ο Quiz Ασκήσεων
ερώτηση 5. πως βρίσκουμε ότι είναι Θ(2^n) ?


Βρήκες τιποτα ? εφόσον το βαθος του δεντρου θα ειναι n, δεν θα επρεπε να ειναι 2*n*Θ(1) = Θ(2n) = Θ(n)


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 15, 2021, 16:10:44 pm
Βρήκες τιποτα ? εφόσον το βαθος του δεντρου θα ειναι n, δεν θα επρεπε να ειναι 2*n*Θ(1) = Θ(2n) = Θ(n)
ιδέα δεν έχω. Πάντως αν κάνω το δέντρο κάθε επίπεδο θα έχει 2^n κυκλάκια?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 15, 2021, 16:17:16 pm
Τωρα που το ξαναειδα, καθε αναδρομη, καλει 2 φορες την επομενη, αρα θα παει 1 -> 2 ->4 ->8 κλπ, οποτε σε βαθος n θα εχει οντως 2^n-1( η πρωτη ειναι μια φορα) κλησεις. Με δεντρακι στο χαρτι βγαινει


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 15, 2021, 16:25:12 pm
Τωρα που το ξαναειδα, καθε αναδρομη, καλει 2 φορες την επομενη, αρα θα παει 1 -> 2 ->4 ->8 κλπ, οποτε σε βαθος n θα εχει οντως 2^n-1( η πρωτη ειναι μια φορα) κλησεις. Με δεντρακι στο χαρτι βγαινει
Αύριο όμως θα χχουμε χρόνο για να κάνουμε δεντράκια?

Σήμερα βρήκαν μέρα να μου φέρουν το βιβλίο, και τι βιβλίο ολόκληρος τόμος 1000 σελίδων  :D :D


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: illuv4tar on April 15, 2021, 16:37:14 pm
Το βιβλιο τωρα απλα θα σε μπερδεψει παραπανω, λυσε τα quiz, διαβασε τα φυλαδια εργαστηριου κι ο θεος βοηθος , παντως το quiz προετοιμασιας εμενα μ φανηκε κομπλε στο χρονο


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Relexility on April 15, 2021, 16:37:55 pm
Παιδια πως βρίσκω ποσα επιπεδα εχει ενα δεντρο αναδρομης του τυπου : T(n) = T(n-2) + Θ(n)  ?
Επίσης για το βάθος μιας αναδρομής τι πρέπει να ελέγξω ;


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on April 15, 2021, 16:43:51 pm
Παιδια πως βρίσκω ποσα επιπεδα εχει ενα δεντρο αναδρομης του τυπου : T(n) = T(n-2) + Θ(n)  ?
Επίσης για το βάθος μιας αναδρομής τι πρέπει να ελέγξω ;
T(n) = T(n-2) + Θ(n) -> T(n - 2) = T(n-4) + Θ(n-2) -> T(n- 4) = T(n-8) + Θ(n-4) ->  ............-> T(n - 2k) + Θ(...)  
λες ότι n - 2k =περίπου = 0 ή 1 οποτε πάνω κάτω κ = n/2
το βαθος νομιζω εινια το ιδιο με τον αριθμο των επιπεδων


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Relexility on April 15, 2021, 16:45:23 pm
Ωραια ! Ευχαριστω πολυ !


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: vgkogkogl on April 15, 2021, 20:33:42 pm
Μπορεί κάποιος να εξηγήσει την ερώτηση 17 στο κουιζ προετοιμασίας?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on May 31, 2021, 13:24:03 pm
Παιδιά, στο δοκιμαστικό κουίζ εξετάσεων, ενώ έκανα σωστά τους χρόνους ωστόσο δεν ξέρω πως να τυπώσω τους σταθμούς που ΔΕΝ πέρασε το αμάξι. Έχει κανείς καμιά έμπνευση;


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on May 31, 2021, 13:29:28 pm
Παιδιά, στο δοκιμαστικό κουίζ εξετάσεων, ενώ έκανα σωστά τους χρόνους ωστόσο δεν ξέρω πως να τυπώσω τους σταθμούς που ΔΕΝ πέρασε το αμάξι. Έχει κανείς καμιά έμπνευση;
εγώ έκανα αυτό, μπορεί να χει τα χάλια του, ενεργειακός θα γίνω. τυπώνει τους σταθμούς που πέρασε,και μετά αυτούς που δεν πέρασε τους βρίσκω με το μάτι, αφού έτσι λέει στην υπόδειξη. Βασικά δεν τυπώνει, τον τελευταίο αλλά θα έπρεπε να τον τυπώνει νομίζω.

Και ένα θέμα του φεβρουαρίου 2020, με τον ίδιο κώδικα περίπου λύνεται.
Code:
D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]
def makestops(D):
    t = [0] * len(D) # array of zeros
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] +  2*R - D[k] +D[i]
                    if q < t[k]:
                        t[k] = q
                        if i > 85:
                             print(i)
    return t[-1]
print(makestops(D))

Θέλω το θέμα 20 του Ιουνίου 2020, πως γίνεται να τυπώσουμε αυτό το μαγκούρι ισοζυγισμένο ? Από το πρωί σπάω το κεφάλι μου αλλά δεν βρίσκω κάτι.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on May 31, 2021, 14:01:48 pm
Ρε εμενα αυτος ο τυπος αναδρομης μου φαινεται sus af...
τι εννοει S[ι] = ')' ΚΑΙ S[ι] = '('    ??


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on May 31, 2021, 14:06:10 pm
Ρε εμενα αυτος ο τυπος αναδρομης μου φαινεται sus af...
τι εννοει S[ι] = ')' ΚΑΙ S[ι] = '('    ??
;exei λάθος εκφώνηση είναι S[ι] = ')'  kai  S[j] = '(' έσπαζα το κεφάλι μου να βρω το bug στο κώδικα που χα γράψει.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on May 31, 2021, 20:19:37 pm
Μπορεί κάποιος να εξηγήσει την ερώτηση 17 στο κουιζ προετοιμασίας?

Bro.. μεχρι το 14 πανε οι ερωτησεις..


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on May 31, 2021, 20:34:12 pm
Bro.. μεχρι το 14 πανε οι ερωτησεις..
Bro.. μιλούσε για το κουιζ προετοιμασίας της 1ης προοδου.   :P


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on May 31, 2021, 21:40:44 pm
Ομγ 15 Απριλη... ΤΑ ΕΧΩ ΠΕΞΕΙ  :D


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 01, 2021, 11:57:12 am
Στο τελευταίο pdf Επαναληπτικό Εργαστήριο - Ασκήσεις Δυναμικού Προγραμματισμού (v1)
που λογικά θα τα κάνει άυριο αυτά. Μήπως έχει λάθος στην  αρχικοποίηση  mov_cost[5][2] και mov_cost[5][3] = 5 κανονικά τα αντίστοιχα στοιχεία της σειράς 4 δεν είναι 5 ή το χω κάψει ?

  


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on June 01, 2021, 17:31:01 pm
yup. στην row[5] υπαρχει βράχος μόνο στο 5.5


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on June 01, 2021, 17:36:39 pm
Προσπαθώ να φτιάξω στη python τον αναδρομικό τύπο από το κουίζ με τις παρενθέσεις για Largest Balanced Sequence και δε τη παλευω. Έχω παντού μηδενικά και που και πού κανέναν άσσο... Τι γίνεται;;

(https://scontent.fath5-1.fna.fbcdn.net/v/t1.15752-9/194991262_110219574503483_8434945725961356667_n.png?_nc_cat=104&ccb=1-3&_nc_sid=ae9488&_nc_ohc=bQm9QCfUj8oAX82EQry&_nc_ht=scontent.fath5-1.fna&oh=8b0daaef1ea1cd773e91e5fa929e50e8&oe=60DC9634)


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 01, 2021, 18:02:26 pm
Code:
def BLS(seq):
    size = len(seq)
    L = [[0] * size for _ in range(size)]
    for i in range(0, size):
        if seq[i] != '(' and seq[i] != ')':
            L[i][i] = 1
        else:
            L[i][i] = 0
    for l in range(0, size + 1):
        for i in range(0, size - l + 1):
            j = i + l - 1
            if i < size and j < size:
                if i < j:
                    L[i][j] = - float('inf')
                    for k in range(i, j):
                        p = L[i][k] + L[k + 1][j]
                        if p > L[i][j]:
                            L[i][j] = p
                        if seq[i] == '(' and seq[j] == ')' and 2 + L[i + 1][j - 1] > L[i][j]:
                            L[i][j] = 2 + L[i + 1][j - 1]

    return L[0][size - 1]
εγώ έκανα αυτό.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on June 01, 2021, 22:32:44 pm
Ευχαριστω, δεν ειχα βαλει για i == j lol


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 02, 2021, 15:00:58 pm
μπορεί κάποιος να μου εξηγήσει τι κάνουμε στην 5 και 6 του κουιζ προετοιμασίας για την β πρόοδο?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: DIMITRIS2000 on June 02, 2021, 18:46:25 pm
μπορεί κάποιος να μου εξηγήσει τι κάνουμε στην 5 και 6 του κουιζ προετοιμασίας για την β πρόοδο?
+1


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 02, 2021, 18:51:28 pm
+1
στην 5 το κατάλαβα με παράρδειγμα, έβαλα μια φορά στοιχεία στον πίνακα α, με αυξουσα σειρά, μια με φθίνουσα (μόνο φθινουσα θέλει για να βγει το συμπέραμσα), έτρεξα τον κώδικα, εκτύπωσα τον πίνακα  και το εβγαλα τελικά το συμπέρασμα που θέλει.
Αλλα την 6 δεν μπορώ να την καταλάβω.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: DIMITRIS2000 on June 02, 2021, 19:15:46 pm
στην 5 το κατάλαβα με παράρδειγμα, έβαλα μια φορά στοιχεία στον πίνακα α, με αυξουσα σειρά, μια με φθίνουσα (μόνο φθινουσα θέλει για να βγει το συμπέραμσα), έτρεξα τον κώδικα, εκτύπωσα τον πίνακα  και το εβγαλα τελικά το συμπέρασμα που θέλει.
Αλλα την 6 δεν μπορώ να την καταλάβω.
Οκ το κατάφερα. θενκσ!!


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on June 02, 2021, 20:10:15 pm
Ίσως εννοεί ότι αν είναι sorted ο πίνακας στην έρωτηση 6 (που λεει οτι ειναι) μπορείς να μην κάνεις την εύρεση του max μέσω της 2ης for αλλά να κάνεις απευθείας
value = A[ι]**2+quantity[i-1]+i-1 και quantity[ι] = value.. (?????????????????????)
Το έκανα


Code:
def alg(A):
    n = len(A)
    quantity = [0 for _ in range(n)] # πίνακας μηδενικών μήκους A
    quantity[0] = A[0]
    for i in range(1,n):
        value = A[i-1]**2+quantity[i-1]+i-1
        quantity[i] = value

    return quantity

και βγήκε ο πίνακας [15, 240, 385, 508, 592, 645, 675, 685]
Με τον αρχικό τον αλγόριθμο βγήκε πάλι ο ίδιος πίνακας


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: neutron57 on June 02, 2021, 20:34:52 pm
Νομίζω γενικά με άπληστο αλγόριθμο μειώνεται η χρονική πολυπλοκότητα ,οπότε θα χρειαστείς μια for . Για να είναι Θ(1) όμως η χωρική , δε θα πρεπε να έχεις πίνακα quantity[n] αλλά μια μεταβλητή quantity , αφού μόνο το quantity του τελευταίου στοιχείου θέλεις να γυρίσεις.


Code:
def alg_greedy(A):
    n = len(A)

    quantity = A[0]**2

    for i in range(1,n):
        if A[i]**2 > A[i-1]**2 + quantity + i-1:
            quantity = A[i]**2
        else:
            quantity = A[i-1]**2 + quantity + i-1

    return quantity



Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 02, 2021, 20:40:48 pm
Τι είναι χωρική πολυπλοκότητα ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Noah on June 02, 2021, 20:46:42 pm
Πόση μνήμη χρησιμοποιείται απο τον αλγόριθμο


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: neutron57 on June 02, 2021, 20:49:02 pm
Τι είναι χωρική πολυπλοκότητα ?
Οι απαιτήσεις δέσμευσης επιπλέον μνήμης που λέει

Για την 5 κάτι σκέφτηκα , το χω στο συννημένο , αντί για quantity το συμβολίζω με q για καλύτερη χωρική πολυπλοκότητα  :D


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Nickgian on June 16, 2021, 21:58:00 pm
Παιδια να ρωτησω οσον αφορα το ερωτημα 13 στο τελος του κουιζ η σωστη απαντηση λεει οτι ειναι το 16950 αλλα εγω βγαζω 8150 που εχω λαθος στον κωδικα αν μπορει κανεις να με βοηθησει

Code:
def makestops(D):
    t = [0] * len(D)
    for k in range(1, len(D)):
        for i in range(0, k):
            R = D[k] - D[i]
            if R <= 200 | R>=100:
                t[k] = t[i] + 2 * R - D[k] + D[i]
    return t[-1]


D = [0, 110, 260, 310, 400, 470, 530, 600, 700, 800, 930, 1040, 1190
    , 1270, 1450, 1500, 1650, 1760, 1890, 1960, 2030, 2200, 2390
    , 2480, 2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410, 3520
    , 3710, 3830, 3980, 4070, 4220, 4390, 4440, 4600, 4790, 4950, 5040
    , 5200, 5260, 5370, 5550, 5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270
    , 6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120, 7320, 7280, 7410, 7550
    , 7670, 7860, 7990, 8170, 8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090
    , 9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200, 10390, 10530, 10670
    , 10730, 10920, 11030, 11160, 11270, 13350, 11530, 11660, 11710, 11850]

print(makestops(D))



Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 16, 2021, 22:08:08 pm
Παιδια να ρωτησω οσον αφορα το ερωτημα 13 στο τελος του κουιζ η σωστη απαντηση λεει οτι ειναι το 16950 αλλα εγω βγαζω 8150 που εχω λαθος στον κωδικα αν μπορει κανεις να με βοηθησει


Αυτό που είχα κάνει καλό δεν είναι ?
Έχω και τον κώδικα που είχε κάνει ο Μανίος μετά στο μάθημα, όταν το βρω θα τον ανεβάσω. το ανέβασα
εγώ έκανα αυτό, μπορεί να χει τα χάλια του, ενεργειακός θα γίνω. τυπώνει τους σταθμούς που πέρασε,και μετά αυτούς που δεν πέρασε τους βρίσκω με το μάτι, αφού έτσι λέει στην υπόδειξη. Βασικά δεν τυπώνει, τον τελευταίο αλλά θα έπρεπε να τον τυπώνει νομίζω.

Και ένα θέμα του φεβρουαρίου 2020, με τον ίδιο κώδικα περίπου λύνεται.
Code:
D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]
def makestops(D):
    t = [0] * len(D) # array of zeros
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] +  2*R - D[k] +D[i]
                    if q < t[k]:
                        t[k] = q
                        if i > 85:
                             print(i)
    return t[-1]
print(makestops(D))

Θέλω το θέμα 20 του Ιουνίου 2020, πως γίνεται να τυπώσουμε αυτό το μαγκούρι ισοζυγισμένο ? Από το πρωί σπάω το κεφάλι μου αλλά δεν βρίσκω κάτι.

Ο Μανιός είχε κάνει αυτό στο μάθημα γιατί κάποιοι του το ζήτησαν.
Code:
def makestops(D):
    t = [0] * len(D) # array of zeros
    best = [0] * len(D)
    for k in range(1, len(D)):
        t[k] = float('inf') ### add your code here!
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]
                    if q < t[k]:
                        t[k] = q
                        best[k] = i
                        
    return t[-1], best
m, best = (makestops(D))
def what_to_do(best, k):
    i = best[k]
    if k == 0:
        print(0)

    else:
        what_to_do(best, i)
        print( "stathmos" + str(i ))

print(what_to_do(best, 100))
Βασικά του Μανιού είναι η 2ρη συνάρτηση, για πρώτη είχα κρατήσει την δικιά μου, δεν έχω τι έκανε για την πρώτη.



Το R το πέρνουμε 100 ή 200 αυτό είναι το λάθος σου. δεν είναι       R = D[k] - D
Γενικά σε αυτά τα κουιζ ακολουθείς πιστά τον ανδρομικό τύπο που επέλεξες και βγάινει ο κώδικας.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Nickgian on June 16, 2021, 22:49:12 pm
Δεν το ειχα προσεξει οτι εχει απαντηθει παλιοτερα επισης του μανιου χωρις εξ ολοκληρου τον κωδικα του δεν δουλευει δεν μου βγαζει αποτελεσματα, και επισης ναι το προσεξα το λαθος με το R

επισης εκανα καποιες αλλαγες αλλα παλι δεν μου βγαινει εκεινος ο αριθμος της λύσης μου βγάζει  σωστη λύση βγανει κατι λιγοτερο ειχα λαθος τον πινακα D(κατι θα μου ειχε ξεφυγει ολα καλα βγαζει κανονικο αποτελεσμα και ειναι ο εξης:
Code:
def makestops(D):
    t = [0] * len(D)
    best = 0
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]
                    if q < t[k]:
                        t[k] = q
                        best = k

                    else:
                        t[k] = t[best]

    return t[-1]

D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]

print(makestops(D))

Αυτό που είχα κάνει καλό δεν είναι ?
Έχω και τον κώδικα που είχε κάνει ο Μανίος μετά στο μάθημα, όταν το βρω θα τον ανεβάσω. το ανέβασα
Ο Μανιός είχε κάνει αυτό στο μάθημα γιατί κάποιοι του το ζήτησαν.
Code:
def makestops(D):
    t = [0] * len(D) # array of zeros
    best = [0] * len(D)
    for k in range(1, len(D)):
        t[k] = float('inf') ### add your code here!
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]
                    if q < t[k]:
                        t[k] = q
                        best[k] = i
                        
    return t[-1], best
m, best = (makestops(D))
def what_to_do(best, k):
    i = best[k]
    if k == 0:
        print(0)

    else:
        what_to_do(best, i)
        print( "stathmos" + str(i ))

print(what_to_do(best, 100))
Βασικά του Μανιού είναι η 2ρη συνάρτηση, για πρώτη είχα κρατήσει την δικιά μου, δεν έχω τι έκανε για την πρώτη.



Το R το πέρνουμε 100 ή 200 αυτό είναι το λάθος σου. δεν είναι       R = D[k] - D.  
Γενικά σε αυτά τα κουιζ ακολουθείς πιστά τον ανδρομικό τύπο που επέλεξες και βγάινει ο κώδικας.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 16, 2021, 22:51:17 pm
Δεν το ειχα προσεξει οτι εχει απαντηθει παλιοτερα επισης του μανιου χωρις εξ ολοκληρου τον κωδικα του δεν δουλευει δεν μου βγαζει αποτελεσματα, και επισης ναι το προσεξα το λαθος με το R

επισης εκανα καποιες αλλαγες αλλα παλι δεν μου βγαινει εκεινος ο αριθμος της λυσης μου βγανει κατι λιγοτερο και ειναι ο εξης:


Αν δεν δουλεύει του Μανιού κάτι δεν έγραψα μάλλον σωστά.  :-\

Ε βάλλε μια print(m) και θα στο τυπώσει.


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Nickgian on June 16, 2021, 22:57:16 pm
Quiz 2020 για τα τελυταια ερωτηματα (το εβαλα βοηθητικα για μελλοντικη χρηση)
Code:
def makestops(D):
    t = [0] * len(D)
    best = 0
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]

                    if q < t[k]:
                        t[k] = q
                        best = k

                    else:
                        t[k] = t[best]
                        if i >85:
                            print(i)

    return t[-1]


D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]

print(makestops(D))


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 17, 2021, 06:15:50 am
Quiz 2020 για τα τελυταια ερωτηματα (το εβαλα βοηθητικα για μελλοντικη χρηση)

Αυτό όμως θα έπρεπε να εκτυπώνει και το 98 ?


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Nickgian on June 17, 2021, 20:36:38 pm
σε αυτο εγω βρηκα με το χερι 3.733 παιρνωντας
  • 2 κιλα μανταρινια 2$
  • 1 κιλο κερ. 1.2$
  • και 0.533 κιλα μανταρινια με κοστος 0.8$
εχει γραψει κανεις κωδικα για την επιλυση αυτου του προβληματος


Title: Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2021
Post by: Caterpillar on June 17, 2021, 20:44:40 pm
σε αυτο εγω βρηκα με το χερι 3.733 παιρνωντας
  • 2 κιλα μανταρινια 2$
  • 1 κιλο κερ. 1.2$
  • και 0.533 κιλα μανταρινια με κοστος 0.8$
εχει γραψει κανεις κωδικα για την επιλυση αυτου του προβληματος

όχι με το χέρι το έλυσα στην πρόοδο, αλλά το έβγαλα αν βλεπω καλά στις μουτζουρες μου  ειναι 3.666  αλλά μπορεί να είναι λάθος μουτζουρα, αλλα το χα λυσει σωστα απο οτι φανηκε.
2 μανταρινιο 1.6666 κερασια
έχεις άπληστο αλγοριθμο οχι δυναμικο.
επιλέγεις απο το φθινοτερο οσο περισσοτερα κιλα μπορεις, ειναι το ιδιο με τον κλεφτη και τα κλοπιμαια που εχει στις διαφανειες.