12 Apr 2023Math
Hello guys, I just uploaded my Bachelor Thesis to arXiv. I completed the thesis back in 2021, it was the first time that I proved a new theorem, putting something new out there to the world. My advisor wanted me to find more results to submit to a journal, but I was lazy. Besides, I was caught into working for capitalism. Anyway, enjoy:
06 Mar 2021Math
Greetings, folks. Yes, I'm still alive and I still love writing blogs. Last year (2020) has been a very rough year for me, you know, depression and stuff, but I finally got myself together. I'll be doing a bachelor thesis on pattern-avoid permutations, particularly trying to prove some equidistributions of some pairs of statistics on two set of PAP. I'm using this blog to take notes of my progress. On the off chance that someone would steal my ideas, I have two things to tell you: 1. I would be very flattered, 2. please don't do so.
Anyway, when we study Math, it's important to ask questions and verify what we study. We're often taught to prove a theorem before going with it. I'm doing the same today: As I was reading Amini's paper [1], I encountered a very beautiful distribution formula of the inversion statistic, and Dr. Huong Tran, my advisor, told me to prove it. I will present some introductory terminologies first, then present the proof. My proof isn't very elegant and formal, but it's pretty intuitive, visual, and intelligible. Hope you'll like it. :)
15 Aug 2020Programming
I'm reading the book "Probability and Statistics for Engineering and the Sciences" by Jay L. Devore.

Dotplot

Dot plot is a great way to display frequency of values.
Suppose that we have an array of float called data. We will first round all numbers to its nearest integer (round_half_up). This rounding step is to make the graph easy to look.
#%%
data = Utilities.readArray("soundnoise.dat", float)
vround = np.vectorize(Utilities.round_half_up)
data = vround(data)

#%%
def generate_frequency(data):
    result = np.zeros(data.shape, dtype=int)
    cnt = {}
    for i in range(len(data)):
        tmp = cnt.get(data[i])
        if (not tmp):
            tmp = 0
        tmp += 1
        cnt[data[i]] = tmp
        result[i] = tmp
    return result

#%%
y = generate_frequency(data)
fig = plt.figure(figsize=(15,3))
plt.yticks([])
plt.plot(data, y, 'o', color='black')
plt.xlabel("Value")
plt.title("Figure 1.6 A dotplot of the data from Example 1.8")
plt.show()
15 Mar 2020Math
After a long time of inactivity, I started reading books again. This time my choice is "Introduction to Statistical Learning with Applications in R" (ISLR) by Gareth James et al. I have developed a habit of noting down important points from the book as well as my insights while reading it. This is my notes for Chapter 2.

Terminologies

Statistical learning investigates the relationship between a set of features and a particular output . The very general formula is
There are many names for and :
  •  : input variable, predictor, (independent) variable, feature
  •  : output variable, dependent variable, response
  is called the error term and it is random, independent of , irreducible, and has mean zero. This is due to the fact that may be dependent on some features other than and the values of such features are not reflected in the data set.
  represents the systematic information that provides about . Oftentimes, we cannot obtain the exact form of but we can get a good estimate of through a number of methods.
15 Jul 2019Programming

Giới thiệu

Trong nhiều bài toán machine learning, chúng ta thường có một hàm để đánh giá xem model của chúng ta đưa ra kết quả chính xác đến mức nào. Hàm đó thường là một hàm đạo hàm được và có output là một số thực.
Một model trong một bài toán machine learning sẽ bao gồm các parameters (tôi được biết chúng còn được gọi là "weights", nhưng không chắc lắm), với mục đích cố gắng giải thích bộ data có sẵn theo một công thức nào đó. Một hàm mất mát (loss function) sẽ cho chúng ta biết model của chúng ta tốt hay kém. Loss function có output thường có output là một số thực và các parameters nói trên là independent variables. Loss function có thể sử dụng bộ data để tính toán, nhưng bộ data này chỉ được xem là hằng số.
Khi train một model, chúng ta sẽ thay đổi các parameters sao cho model chúng ta fit bộ data đó càng khớp càng tốt, i.e. loss function càng nhỏ càng tốt. Nếu loss function là hàm đạo hàm được, với một giá trị cụ thể của bộ parameters, ta có thể tính được xem loss function tại giá trị đó đang có xu hướng tăng hay giảm và tốc độ thay đổi là bao nhiêu. Đối với một loss function đơn giản, ta có thể tính tay công thức gradient của nó và khi cần tính gradient tại điểm nào thì thay điểm đó vào công thức gradient là ra. Tuy nhiên nếu loss function phức tạp, việc tính toán trở nên cực kỳ khó khăn.
16 Apr 2019Math
Notes on the counting techniques (basic and advanced) I learned in the course Discrete Math.
09 Mar 2019Math/Topology
A summary of Chapter 4 and 5 of the book "Topology without Tears" by Sidney Morris that I'm reading.

Subspace

Definition. Let Y be a non-empty subset of the topo space . The collection is a topology on Y and called the subspace topology (aka relative topology, or induced topology, or topology induced on Y by )
Note that an open set of is not necessarily an open set in and vice versa. For example, the subspace of has some open sets such as , etc.
A subspace S of is connected iff it is an interval, i.e. one of the following forms , , , , , ,
A formal defintion of interval is a subset S in has the property: if and , then .

-space (Hausdorff space)

A topological space is called a Hausdorff or -space if given any pair of distinct points , there exist open set and .
In other words, for any two distinct points there exists a neighbourhood of each which is disjoint from the neighbourhood of the other.
Some conclusions:
08 Mar 2020Math/Topology
A summary of Chapter 3 of the book "Topology without Tears" by Sidney Morris that I'm reading.

Limit Points

Definition. Let A be subset of a topo space . A point is called a limit point of A (aka accumulation point or cluster point) if that contains x contain a point of A other than x. In other words,
Theorem. is a closed set in the topo space iff A contains all of its limit points.
Proof:
Suppose that A is closed and but is a limit point of A. Therefore, that contains x contain a point of A other than x. However, is an open set containing x but does not intersect A. Hence x is not a limit point, which contradicts to the assumption. Hence if A is closed then it contains all of its limit points.
Suppose that A contains all of its limit points. For any , x is not a limit point, so such that and , i.e. . We can write X-A as an infinite union of open sets, hence X-A is open and A is closed.
03 Mar 2019Math/Topology
This is my notes for the second chapter of the book "Topology without Tears" by Sidney Morris. We're going to discuss the Euclidean topology. During the writing of this note, I also had the first sense of the close relationship between geometry and topology. This is one of the rare notes that have GeoGebra visualizations, so keep reading! You will find one in a proof somewhere in this post!

The Euclidean Topology on

Definition. A subset S in is said to be open in the Euclidean topology on if for each , there exist such that
It is common that if we say the topology on without defining the topology, we mean the Euclidean topology.
Properties
Let .
  • (r,s), and are open sets.
  • [r,s], , , , and are closed sets.
  • [r,s), (r,s], , are neither closed nor open.
  • The only clopen sets are the trivial sets, i.e. .
  • Not all open sets are intervals (r,s). Some open sets may be the union of several intervals.
02 Mar 2019Math/Topology
Recently, I started reading the book "Topology Without Tears" by Sidney Morris. It is such an exciting adventure. And as always, I write notes about what I learned.
25 Feb 2019Theoretical CS
A good starting example for what is so-called "context-free grammars" is to look at the English language we're using everyday. I would present a very simple way of describe our language. Each sentence in English, to put simply, is made of a noun phrase and a verb phrase. A noun phrase may contain another noun, a verb phrase may contain a preposition phrase or another noun. You see, these terms are defined recursively, and it is very difficult or impossible to describe such a language using finite automata or regular expression. Context-free grammar (CFG) is a powerful tool to deal with languages with recursive structure. Using the example above, one can write a CFG like this (taken directly from [1]):
Sentence Noun-phrase Verb-phrase
Noun-phrase Complex-noun or Complex-noun Preposition-phrase
Verb-phrase Complex-verb or Complex-verb Preposition-phrase
Preposition-phrase Preposition Complex-noun
Complex-noun Article Noun
Complex-verb Verb or Verb Noun-phrase
Article a or the
Noun boy or girl or knife
Verb touches or cuts or sees
Preposition with
19 Feb 2019Theoretical CS
In this post, we will discuss the concepts surrounding the topic "Regular Languages" like DFA, NFA, regular expressions, and two important theorems, the pumping lemma and Myhill-Nerode theorem.

Finite automaton

A good representation for what is so called finite automaton is a directed graph with a finite number of vertices. Each vertex is called a state. Each edge is assigned with a value called a symbol. The set of all possible symbols is called an alphabet. There is also one node marked as the start state, and some nodes are marked as the accept states. We give this automaton a string s, the following will happen:
current_state = start_state
for character ch in s:
  for edge e in current_state.out_edges:
    if e == ch:
      current_state = e.end_node
You may wonder, what if there are multiple e such that e == ch? Well, this is the formal definition of finite automaton:
Definition: (Deterministic) Finite Automaton. A finite automaton is a tuple , where:
  •   is a finite set of states
  •   is a finite set called the alphabet
  •   is the transition function
  •   is the start state
  •   is the set of accept (final) states
10 Jan 2019Algorithms
You are given a permutation of size , i.e. a sequence of distinct numbers. The task is to partition this permutation into monotonic subsequences. The number of subsequences (syn.: partition) does not need to be minimum, but it has to be smaller than , which denotes the minimum such that any permutation of size can be splited into at most subsequences.
I came across this problem on Codeforces a while ago. They did provide a solution (thanks, Radewoosh!), but since I love to proving things, I want to note down some of my insights and findings.

Observations

Let be the greatest such that . Consider the permutation (size ) in which the first terms are 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, ... (OEIS A038722), followed by the rest of terms sorted decreasingly. We call this sequence . For example:
  •  
  •  

What is the minimum number of monotonic partitions of ?

We notice that can be seperated into several contiguous subarray, each subarray has decreasing elements. For example:
08 Jan 2019Math/Algorithms
Consider a sequence , in which let and . Apparently there are a lot of sequences like that. For each , is selected randomly with equal possibilities among the divisors of . Let's denote the expected value of . What is ? Read the problem statement.
For example, we have and need to calculate . All possible sequences of are:
Can we simply calculate the average value of ?, in this case:
No we can't, because the possibilities for the sequences to happen are not all the same. For example, the possibility of is , while that of is only .
06 Jan 2019Math/Algorithms
Consider a table of cells, which are colored by four colors Azure, Coral, Green, and Taupe. The only condition for it to be nice is that every subtable of has 4 distinct colors. (1)
Given a colored table, we need to re-color it so that it satisfies the condition above. What is the minimum number of cells that need to be re-colored? Read the problem statement.
We need to prove the following theorem:
Theorem. Such a table satisfying (1) has:
  • every row has two alternate colors, or
  • every column has two alternate colors
Proof
It is obvious that every row or column cannot have only one colors. We will prove that if a column of the nice table contains at least 3 different colors, then every row contains only 2 colors.
Suppose that column has at least 3 different colors. We can find such that the colors of (i-th row, j-th column), , and are pairwise different. Consider a column that is two columns away from . Without loss of generosity, let it be the column . Since is a nice table, forms a full set of colors ACGT, and so is .
That implies . Similarly we can show that . The two equalities give us and .
05 Dec 2018Algorithms
I was studying Rotating Calipers the other day, and like many other people, I jumped to Wikipedia as soon as I found it in the result pages. Wikipedia - Rotating Calipers. This particular page was a stub. It contained very few information and description about the algorithms, let alone the visuals to support.
I was interested in the problem of finding the largest segment formed from a set of points, which leads to the problem of finding the diameter of the convex hull. Finding convex hull is rather familiar to me, but to find the diameter is something new. The Rotating Calipers technique is one of the most popular method to solve such problem, and it was first introduced by Michael Shamos in his Ph.D. Thesis at Yale University, 1978. You can find his paper online here. The algorithm was proposed on page 79 of the paper (p. 87 of the file).
The paper actually described the method much better than Wikipedia. His idea was indeed very elegant and clever, but his pseudocode on page 79 has many flaws. Some guy had copied this implementation and posted on Wikipedia. What was worse, you could find some other websites on the first-page result of Google that also copied verbatim from Wikipedia. When I found the mistakes, I couldn't doubt myself because this was a 40-year-old paper, so I must have missed some detail somewhere which might have led to the confusion. But after posting my concerns on Reddit and receiving positive feedback, I became more certain with what I had found. I don't know if anyone has spotted the mistakes before me, or if they were corrected in the next editions. In his following textbook, "Computational Geometry", published in 1985, the whole implementation was removed. I did not see any confirmation or modification. It was simply replaced by a new approach using areas, meanwhile the old one depended on calculating angles. In this article, I will explain the algorithm, the flaws, and give an alternative solution.
30 Oct 2018Math
Một lớp bài toán quan trọng trong đại số tuyến tính là tìm những vector chỉ thay đổi độ dài chứ không thay đổi phương và hướng khi đưa qua một ánh xạ tuyến tính. Nói cách khác, xét , tìm các vector sao cho trong đó là một số thực.
là một toán tử tuyến tính nên có thể biểu diễn bằng một ma trận . Số được gọi là trị riêng (eigenvalue) của (hoặc của ) nếu phương trình có nghiệm . Các nghiệm tìm được được gọi là vector riêng (eigenvector) của (hoặc của ) ứng với trị riêng .
Nếu là một vector riêng của thì () cũng là vector riêng của . Ứng với một trị riêng có nhiều vector riêng, chúng tạo thành một không gian vector, gọi là không gian riêng (eigenspace).
This post is being reviewed. Please help me improve it by reporting mistakes and suggesting changes to my email.

Phương trình đặc trưng

Để tìm các eigenvalue trong , ta viết lại thành , tức là:
Đây là hệ thuần nhất, điều kiện có nghiệm không tầm thường là . Phương trình này được gọi là phương trình đặc trưng của (characteristic equation). Vế trái của phương trình gọi là đa thức đặc trưng (characteristic polynomial). Tập các eigenvector ứng với chính là eigenspace . Số chiều của hạt nhân này được gọi là số bội hình học (geometric multiplicity) của .
10 Oct 2018Math
Trong số các ánh xạ từ không gian vector đến không gian vector có một lớp quan trọng là lớp ánh xạ tuyến tính, aka Linear Transformation.
Ánh xạ tuyến tính bảo toàn các tính chất về phép cộng và phép nhân với một số. Cụ thể, nếu có thì:
  •  , .
  •  , .
Cho lần lượt là hai không gian vector chiều và chiều, mọi ánh xạ tuyến tính có thể được biểu diễn qua một ma trận .
Gọi là cơ sở của , khi đó, mọi vector có biểu diễn duy nhất:
Vậy nên
25 Sep 2018Algorithms
Hôm nay mình muốn bình về bài toán VAIMIN đăng trên CodeChef trong kỳ thi April Challenge 2018. Đây là một bài toán phức tạp song có rất nhiều kỹ thuật và kiến thức hữu ích rút ra được từ nó.

Tóm tắt

Một thủ tướng có thể làm điều tốt hoặc điều xấu. Mức độ uy tín của ông tăng lên 1 khi ông làm điều tốt và giảm đi 1 khi ông làm điều xấu. Ban đầu, mức độ uy tín là bằng 0. Ông ta lên kế hoạch làm đủ điều tốt và điều xấu. Tuy nhiên, trước khi làm một điều xấu, uy tín của ông ta phải lớn hơn , nếu không ông sẽ bị phát hiện và buộc từ chức!
Có một ông thanh tra chuyên đi bắt các vụ tham nhũng. Vị thanh tra từng bắt bộ trưởng tham nhũng, khi bộ trưởng bị bắt, hắn đã từng làm điều tốt và điều xấu. Không muốn đi vào con đường cũ, ngài thủ tướng sẽ tránh làm điều tốt và điều xấu trong suốt nhiệm kì của mình, bởi không ngài sẽ bị bắt bởi vị thanh tra kia.
Hãy đếm số chiến thuật thực hiện điều tốt xấu trong nhiệm kì của thủ tướng sao cho thỏa mãn các điều kiện trên.
Với bộ test mẫu của đề bài: , , , . Ta có hình minh họa ở hình 1:

Minh họa test mẫu đề bài

Các hình tròn trắng khoanh vùng điểm "cấm" (điểm mà các bộ trưởng bị bắt hối lộ). Ban đầu thủ tướng đứng ở hình vuông đỏ, rồi tìm cách đi đến hình vuông xanh lá. Mỗi bước đi tuân thủ những điều kiện sau:
  • Bắt buộc phải đi lên (hướng đông bắc) hoặc đi xuống (hướng đông nam);
  • Mọi bước đi xuống đều không được rơi xuống bên dưới đường Reputation = .
  • Không được đi vào những điểm cấm.
Hỏi có bao nhiêu cách đi?
Trong ví dụ trên, có tổng cộng 4 cách đi:
17 Sep 2018Math
Chúng ta đã biết khái niệm về vector hình học ở cấp 3. Chúng có thể cộng với nhau và nhân với một số (scaling) cho ra một vector mới. Trong thực tế có nhiều thứ mang hai đặc điểm đó, ví dụ như đa thức: hai đa thức có thể cộng với nhau, một đa thức có thể nhân với một số, tạo ra một đa thức mới. Người ta cho ra đời một khái niệm không gian vector (vector space) tổng quát mà trong đó vector có thể là một vector hình học, một đa thức, một hàm số liên tục, v.v..
Xét tập mà mỗi phần tử gọi là một vector và trường số thực . Giả sử ta có hai phép toán: phép cộng hai vector và phép nhân một vector với một số thực. là một không gian vector nếu nó thỏa mãn tất cả các điều sau:
  •   là một nhóm Abelian có phần tử đơn vị ký hiệu là .
  • Với ta có:
    •  
    •  
    •  
    •  
    •  
Hệ quả:
  •  
  •  
  •  
  • Nếu thì hoặc hoặc .
Nếu và phép cộng đóng kín trong và phép nhân với một số thực cũng đóng kín trong thì gọi là một không gian con (subspace).

Không gian hữu hạn chiều

Tổ hợp tuyến tính

08 Sep 2018Math
Với số nguyên dương , tập hợp tất cả các ma trận kích thước được đóng kín dưới phép toán cộng và nhân, tạo thành một vành không giao hoán. Định nghĩa phép toán và nhân ma trận không được đề cập ở đây.

Transpose Matrix

Nếu đổi hàng thành cột, cột thành hàng của ma trận A ta được ma trận chuyển vị (aka transpose matrix), ký hiệu là
Có thể chứng minh được rằng:

Determinant

Cho là một ma trận vuông kích thước . Ma trận con (submatrix) của tương ứng với phần tử , ký hiệu là được suy ra bằng cách bỏ hàng và cột trong ma trận . Định thức của ma trận này gọi là định thức con (minor).
Định thức của , ký hiệu được định nghĩa đệ quy như sau:
  • Nếu ,
  • Nếu ,
(tự chọn dòng bất kỳ).
Biểu thức còn được gọi là phụ đại số (cofactor) của phần tử , ký hiệu . Như vậy, công thức tính định thức ma trận có thể phát biểu gọn: "Định thức ma trận bằng tổng các 'tích phụ đại số với phần tử tương ứng' trên một hàng hoặc một cột bất kỳ."
22 Aug 2018Math

Property of closure

Closure (aka. luật hợp thành trong) trên tập E là một phép toán mà khi tác động giữa hai phần tử thuộc E, chỉ cho ra một kết quả duy nhất và kết quả này cũng thuộc E. Closure là một ánh xạ . Lúc này ta gọi là một tập kín (closed set) dưới phép toán nói trên.
Ví dụ, trong tập , phép cộng (+) và phép nhân (*) là các luật thành trong, nhưng phép trừ (-) thì không phải, vì kết quả phép trừ có thể là số âm, nằm ngoài phạm vi của tập .

Tính chất của một luật hợp thành trong

Dưới đây là một số tính chất có thể có của một luật hợp thành trong (ký hiệu bằng dấu sao (*)).
12 Aug 2018Personal
Hello everyone!
In this post, I'm going to tell you how I got accepted to GSoC 2018 as a student developer at CGAL, and how I passed all of the three evaluations.
As many of you may have known, Google Summer of Code is an annual event that provides opportunities for students around the world to work with open-source companies/organizations. Students are also paid a decent amount of money, based on the location of their university.
I first heard of GSoC from a teacher in high school. It's normally held after its brother program, known as Google Code-in. Around January, I started checking calendar and waited until mid February when the official list of partner organizations was published. At this point, I would "lurk" around the site to find some interesting project, yet it must suit my ability. I have 2-year experience with C++, thanks to the training for the National Olympiad, so I targeted a few companies. However, most of the work I'd done was theoretical work, not designing and configuring apps, hence CGAL was a good choice. It was managed by more than 8 institutions, all of which are very advanced in the field of technology.
12 Aug 2018Programming
So, what I implemented in this package is called "Generalized Region Growing." You may have heard of Region Growing before. It has a close relationship with Breadth-First Search. This is an excerpted version of the manual of the package Generalized Region Growing, my work at GSoC 2018. I started this package and worked on it during the last three months under the supervision of Dr. Anisimov. I'm very excited to share you what I've done this summer!
The authors of this package are me, D. Anisimov, F. Lafarge, and S. Giraudot.

Introduction

This CGAL component implements the region growing algorithm for shape detection. The algorithm has been generalized to be working with any user-defined elements, connectivity method, and validity checking rules. Three types of detection are provided with the package:
  • Plane detection in a 3D point cloud.
  • Line detection in a 2D point set.
  • Plane detection in a 3D mesh.
Other types of detection can also be added by the user.
09 May 2018Programming
This is a note from Walter E. Brown's talk at CppCon 2014 -- "Modern Template Metarogramming - A compendium."
Metaprogramming is to write templates, and the compiler will see how the templates are called, then it will generate the real code based on the template. It is used to enhance run-time performance and adaptability.
DISCLAIMER: The following is my understanding about the subject. My understanding does not represent Walter E. Brown's opinion, nor should it necessarily be the fact. Readers should carefully consider before re-use this as reference material. I'm open to new ideas and very active online, so don't hestitate to send me an email if you want to improve this post.

Simple example

template <int N>
struct abs {
    static_assert(N != INT_MIN); // There is no opposite number of the smallest int
    static constexpr auto value = (N > 0) ? N : -N;
}
// ...
int const n = -15;
std::cout << (abs<n>::value) << std::endl;
One thing to remember is we're working with compile time, we do not touch run time, so we have to work with what we know at compile time. You can call abs<-3>, abs<n> (with n being a constant), but you cannot call abs<m> if m is not known at compile time. Again, templates are used to generate code at compile time, using what compiler knows at compile time.
abs was a template class/struct (difference?). We assigned value to be a static property so that we can call value without initialize an instance of abs (as if you're working with namespace).
Brown called abs implemented above "metafunction." It is a class that represents a function. I prefer to look at it as... a class. It is a more general term and in the big picture a class appears to be more obvious.
19 Apr 2018Math
Ghi lại nhanh sau này coi lại, đã dốt toán lại còn không nhớ dai.
Cho ma trận sau:
  • Đối với ma trận vuông bậc , đường chéo gồm các phần tử được gọi là đường chéo chính (principal or leading diagonal). Tổng các phần tử trên đường chéo chính gọi là trace của .
  • Ma trận chéo là ma trận mà các phần tử khác 0 chỉ nằm trên đường chéo chính. Trường hợp đặc biệt, nếu cả đường chéo chính chỉ gồm các số 1 thì đó gọi là ma trận đơn vị (identity or unit matrix).
  • Cách tạo ma trận chuyển vị : Đem cột rải thành hàng
  • Ma trận đối xứng (symmetric matrix) khi , phản đối xứng (skew symmetric matrix) khi
01 Jan 2018Math
Hồi đó mình đi cắm trại, tham gia trò chơi lớn, thường có một trò "giải mật thư." Khi nhận mật thư, kèm với thư đã mã hóa (ciphertext) là một dòng văn bản "gợi ý" cách giải mã.
Ví dụ, "gợi ý" đưa ra là:
"Tuổi 17 bẻ gãy sừng trâu."

Vòng mã hóa Caesar

Theo văn hóa thể thao nước mình, trong các giải đấu dành cho vận động viên 17 tuổi, thì người ta gọi là "giải đấu U17." Như vậy, ký tự "U" trên bảng chữ cái tương ứng với số 17. Lúc này, học sinh mới xoay hai vòng tròn bên trong sao cho số 17 khớp với chữ U ở vòng tròn ngoài cùng. Và ta có bảng đối chiếu, ví dụ chữ U trong cipher text sẽ đổi thành chữ O, hoặc chữ V thì được đổi thành P.
Tóm lại, ý tưởng của mã hóa Cipher là chọn ra một số nguyên làm khóa và một tập hợp . Số sẽ được mã hóa theo hàm sau:
12 Nov 2017Math
Thuật toán Euclid được dùng để tìm ước chung lớn nhất của hai số nguyên không âm như sau:
def gcd(a,b):
    while (b != 0):
        r = a % b # chia lấy phần dư
        a = b
        b = r
    return a
Dựa trên định lý .
  • Định lý Bézout chỉ ra rằng, nếu thì tồn tại hai số sao cho . Phương trình này được gọi là đồng nhất thức Bézout (Bézout identity). Hai số được gọi là hệ số Bézout (Bézout coefficents) của hai số .
  • Phương trình Diophantine là phương trình có dạng được mô tả dựa trên định lý Bézout. Phương trình có nghiệm khi và chỉ khi . Một khi phương trình có nghiệm thì sẽ có vô số nghiệm.
    • Giả sử phương trình có nghiệm . Họ nghiệm của phương trình sẽ là . Để ý rằng:
05 Nov 2017Math
  • Hàm phi () Euler của một số nguyên dương được định nghĩa là số các số nguyên dương không vượt quá sao cho .
    • Ví dụ, số 10 có 4 số nguyên dương không vượt quá 10 và nguyên tố cùng nhau với 10, đó là 1, 3, 7, 9. Như vậy, .
  • Nếu là số nguyên tố, dễ thấy .
  • Nếu thì .
    • Chứng minh: Có tổng cộng số nguyên dương cần xét. Trong số đó, các số có ước chung lớn nhất với khác 1 sẽ có dạng , với là bất cứ số nguyên dương nào đảm bảo , như vậy có tổng cộng giá trị như thế. Suy ra số các số nguyên tố cùng nhau với . (QED)
  • Nếu (với ) thì .
    • Chứng minh: Có tổng cộng số nguyên dương cần xét. Trong số đó, các số có ước chung lớn nhất với khác 1 sẽ có dạng hoặc sao cho . Trong trường hợp đầu, trải dài từ đến . Trong trường hợp sau, trải dài từ đến . Tuy nhiên, có hai giá trị được đếm hai lần, đó là . Như vậy có tổng cộng số không nguyên tố cùng nhau với . Như vậy:
29 Oct 2017Math
Nói về đạo hàm, như các bạn học ở lớp 11, 12 thì đạo hàm biểu thị tốc độ thay đổi của hàm. Ví dụ hàm có đạo hàm là để biểu thị tỉ lệ thay đổi của hàm khi biến đầu vào (input) thay đổi một lượng rất nhỏ . Đối với đồ thị trên mặt phẳng tọa độ, đạo hàm tại một điểm trên đồ thị bằng độ dốc của đường biểu diễn đồ thị đó. Chính vì thế mới có nguyên tắc tìm tiếp tuyến của đồ thị tại một điểm bằng cách tính đạo hàm. Nếu bạn từng làm gà chọi thi đại học, mấy cái mình nói ra ở đây chắc hẳn quá quen thuộc với bạn rồi.
Đạo hàm như vậy là đạo hàm thông thường (ordinary derivative).
Đạo hàm riêng (partial derivative) cũng hoạt động trên nguyên tắc tương tự.

Đồ thị hàm .

Đạo hàm riêng theo biến , ký hiệu là hoặc sẽ được tính giống như đạo hàm bình thường nếu ta xem tất cả các biến khác là hằng số. Với đạo hàm thường ta dùng chữ , đạo hàm riêng ta dùng chữ (đọc là "del" hoặc "partial").
18 Sep 2017Math
Hồi còn học phổ thông thì phần lớn các bạn được tiếp cận với hàm một biến, người ta hay viết thì gọi là biến độc lập và gọi là biến phụ thuộc. Ví dụ trong sách vật lý 10, mấy bài đầu có dạy về chuyển động thẳng đều, công thức là thì đây chẳng qua là hàm tính độ dời (, biến phụ thuộc) theo thời gian (, biến độc lập). Giả sử xét bài toán ngược là thì lúc này lại là biến phụ thuộc. Đó là giới thiệu sơ qua về hàm số, cái khái niệm rất lạ mà cũng rất quen. :))
Nhưng mà trong thế giới thực thì hiếm có khi nào bạn thu thập dữ liệu của một đại lượng mà cho ra được kết quả. Một hàm không chỉ dừng lại ở mức độ "từ một số biến đổi thành một số", mà còn có thể là "từ nhiều số biến đổi thành một số", "từ một số biến đổi thành nhiều số", "từ nhiều số biến đổi thành nhiều số", ... Ví dụ nhé:
  • Xe chuyển động thẳng đều, tôi biết trước , bây giờ bạn cho tôi bao nhiêu thời gian tính từ khi xe xuất phát thì tôi trả cho bạn bấy nhiêu giá trị tương ứng. Đó là hàm biến đổi "từ một số thành một số" (scalar-scalar). Lưu ý là hằng số, không tham gia vào chuyện biến đổi ở đây nhé.
29 Aug 2017Math
Hồi quy tuyến tính là một phương pháp tìm quan hệ tuyến tính giữa những biến số độc lập (independent variables) với một biến số phụ thuộc (dependent variable).
Chẳng hạn, một cái máy theo dõi quãng đường của một chiếc xe chuyển động thẳng đều. Tại một thời điểm , nó ghi lại xem xe đã đi được bao nhiêu mét (ký hiệu là ). Nhưng bạn biết thì thế giới thực chẳng bao giờ hoàn hảo được cả, máy đo có thể bị sai số do nguồn điện, đường xóc, vật cản, ... Và kết quả khi biểu diễn lần đo đó lên đồ thị, ta có hình sau (quan sát các điểm biểu diễn màu cam):

Minh họa hồi quy tuyến tính. Trục tung là đại lượng độ dài đi được, trục hoành là đại lượng thời gian.

Công việc của bạn là "chuẩn hóa" lại dữ liệu bị nhiễu này. Công việc chuẩn hóa có thể có nhiều mục đích, ví dụ như để tính vận tốc của xe, hoặc để dự đoán trong tương lai ở thời điểm thì xe đã di chuyển được bao xa.
Bạn biết rằng đồ thị - của vật chuyển động thẳng đều thì có đường thẳng (tuyến tính). Một trong những phương pháp phổ biến để phân tích quan hệ tuyến tính giữa hai đại lượng như quãng đường và thời gian trong bài toán này là hồi quy tuyến tính bằng phương pháp bình phương tối thiểu.