Здравей,

Прилича ми на правилно решение, но не пълно. Имаш сини линии, не знам от къде са, но не би трябвало да ги има.

Не си изпълнила условието с оцветяването на векторите. И не си изобразила координатната ос.

Ето как изглежда моето решение:

https://imgur.com/a/dYr5kRl

Привет и благодаря за темата! 

Въпрос по Problem 5. Function Invertibility and Cryptography - времето за умножение нула ли ви се получава?

Времето за разлагане ми се получава различно, но това за умножение е всеки път нула. Резултатите от действията са верни (т.е. функциите работят правилно).

Basic Algebra Exercise

Functions, Polynomials, Complex Numbers. Applications of Abstract Algebra

Problem 1. Polynomial Interpolation

We know that if we have a set of nn data points with coordinates (x1;y1),(x2;y2),…,(xn;yn)(x1;y1),(x2;y2),…,(xn;yn), we can try to figure out what function may have generated these points.

Please note that our assumptions about the data will lead us to choosing one function over another. This means that our results are as good as our data and assumptions. Therefore, it's extremely important that we write down our assumptions (which sometimes can be difficult as we sometimes don't realize we're making them). It will be better for our readers if they know what those assumptions and models are.

In this case, we'll state two assumptions:

1. The points in our dataset are generated by a polynomial function
2. The points are very precise, there is absolutely no error in them. This means that the function should pass through every point

This method is called polynomial interpolation ("polynomial" captures assumption 1 and "interpolation" captures assumption 2).

It can be proved (look at Wikipedia for example) that if we have nn data points, there is only one polynomial of degree n−1n−1 which passes through them. In "math speak": "the vector spaces of nn points and polynomials of degree n−1n−1 are isomorphic (there exists a bijection mapping one to the other)".

There are a lot of ways to do interpolation. We can also write the function ourselves if we want but this requires quite a lot more knowledge than we already covered in this course. So we'll use a function which does this for us. numpy.polyfit() is one such function. It accepts three main parameters (there are others as well, but they are optional): a list of xx coordinates, a list of yy coordinates, and a polynomial degree.

Let's say we have these points:

points = np.array([(0, 0), (1, 0.8), (2, 0.9), (3, 0.1), (4, -0.8), (5, -1.0)])

First, we need to "extract" the coordinates:

x = points[:, 0]
y = points[:, 1]

Then, we need to calculate the interpolating polynomial. For the degree, we'll set n−1n−1:

coefficients = np.polyfit(x, y, len(points) - 1)
poly = np.poly1d(coefficients)

After that, we need to plot the function. To do this, we'll create a range of xx values and evaluate the polynomial at each value:

plot_x = np.linspace(np.min(x), np.max(x), 1000)
plot_y = poly(plot_x)

Finally, we need to plot the result. We'll plot both the fitting polynomial curve (using plt.plot()) and the points (using plt.scatter). It's also nice to have different colors to make the line stand out from the points.

plt.plot(plot_x, plot_y, c = "green")
plt.scatter(x, y)
plt.xlabel("x")
plt.ylabel("y")
plt.show()

Don't forget to label the axes!

Your task now is to wrap the code in a function. It should accept a list of points, the polynomial degree, min and max value of xx used for plotting. We'll use this function to try some other cases.

import numpy as np
import numpy.polynomial.polynomial as p
def interpolate_polynomial(points, degree, min_x, max_x):
    
    
    """
    Interpolates a polynomial of the specified degree through the given points and plots it
    points - a list of points (x, y) to plot
    degree - the polynomial degree
    min_x, max_x - range of x values used to plot the interpolating polynomial
    """
    # Write your code here
    return x_chart, y_chart

Някой разбира ли какво се иска във втора задача и някой успя ли да я реши?

Problem 2. Complex Numbers as Vectors

We saw that a complex number z=a+biz=a+bi is equivalent to (and therefore can be represented as) the ordered tuple (a;b)(a;b), which can be plotted in a 2D space. So, complex numbers and 2D points are equivalent. What is more, we can draw a vector from the origin of the coordinate plane to our point. This is called a point's radius-vector.

Let's try plotting complex numbers as radius vectors. Don't forget to label the real and imaginary axes. Also, move the axes to the origin. Hint: These are called "spines"; you'll need to move 2 of them to the origin and remove the other 2 completely. Hint 2: You already did this in the previous lab.

We can use plt.quiver() to plot the vector. It can behave a bit strangely, so we'll need to set the scale of the vectors to be the same as the scale on the graph axes:

plt.quiver(0, 0, z.real, z.imag, angles = "xy", scale_units = "xy", scale = 1)

Other than that, the main parameters are: xbeginxbegin, ybeginybegin, xlengthxlength, ylengthylength in that order.

Now, set the aspect ratio of the axes to be equal. Also, add grid lines. Set the axis numbers (called ticks) to be something like range(-3, 4) for now.

plt.xticks(range(-3, 4))
plt.yticks(range(-3, 4))

If you wish to, you can be a bit more clever with the tick marks. Find the minimal and maximal xx and yy values and set the ticks according to them. It's a good practice not to jam the plot too much, so leave a little bit of space. That is, if the actual x-range is [−2;2][−2;2], set the plotting to be [−2.5;2.5][−2.5;2.5] for example. Otherwise, the vector heads (arrows) will be "jammed" into a corner or side of the plot.

Някой разбира ли какво се иска в 3-та задача? И някой намерил ли е решение?

Problem 3. Recursion and Fractals

"To understand recursion, you first need to understand recursion."

There are three main parts to a recursive function:

1. Bottom - when the recursion should finish
2. Operation - some meaningful thing to do
3. Recursive call - calling the same function
4. Clean-up - returning all data to its previous state (this reverses the effect of the operation)

Let's do one of the most famous recursion examples. And I'm not talking about Fibonacci here. Let's draw a tree using recursive functions.

The figure we're going to draw is called a fractal. It's self-similar, which means that if you zoom in on a part of it, it will look the same. You can see fractals everywhere in nature, with broccoli being one of the prime examples. Have a look:

First, we need to specify the recursive part. In order to draw a tree, we need to draw a line of a given length (which will be the current branch), and then draw two more lines to the left and right. By "left" and "right", we should mean "rotation by a specified angle".

So, this is how to draw a branch: draw a line and prepare to draw two more branches to the left and right. This is going to be our recursive call.

To make things prettier, more natural-looking (and have a natural end to our recursion), let's draw each "sub-branch" a little shorter. If the branch becomes too short, it won't have "child branches". This will be the bottom of our recursion.

There's one more important part of recursion, and this is "the clean-up". After we did something in the recursive calls, it's very important to return the state of everything as it was before we did anything. In this case, after we draw a branch, we go back to our starting position.

Let's first import the most import-ant (no pun intended...) Python drawing library: turtle! In order to make things easier, we'll import all methods directly.

from turtle import *

You can look up the docs about turtle if you're more interested. The basic things we're going to use are going forward and backward by a specified number of pixels and turning left and right by a specified angle (in degrees).

Let's now define our recursive function:

def draw_branch(branch_length, angle):
    if branch_length > 5:
        forward(branch_length)
        right(angle)
        draw_branch(branch_length - 15, angle)
        left(2 * angle)
        draw_branch(branch_length - 15, angle)
        right(angle)
        backward(branch_length)

And let's call it:

draw_branch(100, 20)

We need to start the tree not at the middle, but toward the bottom of the screen, so we need to make a few more adjustments. We can wrap the setup in another function and call it. Let's start one trunk length below the center (the trunk length is the length of the longest line).

def draw_tree(trunk_length, angle):
    speed("fastest")
    left(90)
    up()
    backward(trunk_length)
    down()
    draw_branch(trunk_length, angle)

Note that the graphics will show in a separate window. Also note that sometimes you might get bugs. If you do, go to Kernel > Restart.

Някой успя ли да реши 4-та задача?

Problem 4. Run-length Encoding

One application of algebra and basic math can be compression. This is a way to save data in less space than it originally takes. The most basic form of compression is called run-length encoding.

Write a function that encodes a given text. Write another one that decodes.

We can see that RLE is not very useful in the general case. But it can be extremely useful if we have very few symbols. An example of this can be DNA and protein sequences. DNA code, for example, has only 4 characters.

Test your encoding and decoding functions on a DNA sequence (you can look up some on the Internet). Measure how much your data is compressed relative to the original.