[Discrete Mathematics] Sets and Funtions

1. Sets

  • A set is an unordered collection of objects, called elements or members of the set.
  • A set is said to contain its elements
  • $ a \in A $ if a is element of A
  • $ a \notin A $ if a is not element of A
  • Ways to describe set
    • List all the members of a set (Roster method). E.g $ A = \{a, b, c, d\} $ (Roster method)
    • Use set builder notation: $ X = \{ x \mid P(x) \} $$$ E.g \ \ O=\{x \mid x \ is \ odd\} $$
  • A is a subset of B if and only if every element of A is also an element of B.$$ A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) $$
  • Two sets are equal if and only if they have the same elements.$$ A = B \Leftrightarrow \forall x (x \in A \leftrightarrow x \in B) $$$$ A = B \Leftrightarrow A \subseteq B \land B \subseteq A $$
  • The empty set$\emptyset$$$ For \ every \ set \ \emptyset \subseteq S, S \subseteq S $$
  • Given a set $S$, the power set of $S$ is the set of all subsets of the set S. The power set of S is denoted by $\mathcal{P}(S)$

2. Set operations

  • The union of the sets A and B is the set that contains those elements that are either in A or in B, or in both.$$ A \cup B = \{x \mid x \in A \lor x \in B \} $$
  • The intersection of the sets A and B is the set containing those elements in both A and B.$$ A \cap B = \{x \mid x \in A \land x \in B \} $$
  • The difference of A and B is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.$$ A \setminus B = \{ x \mid x \in A \land x \notin B \} $$

Table set identies

To be done

3. Cartesian product

  • The ordered n-tuple (a1, a2, . . . , an) is the ordered collection that has a1 as its first element, a2 as its second element, . . . , and an an as its nth element.
  • The Cartesian product of the sets A1, A2, . . . , An, denoted by A1 x A2 x · · · x An, is the set of ordered n-tuples (a1, a2, . . . , an), where ai belongs to Ai for i = 1, 2, . . . , n.$$A_1 × A_2 × · · · × A_n = \{ \ (a_1, a_2, . . . , a_n) \mid a_i ∈ A_i, i = 1, 2, . . . , n \ \} $$

4. Function

  • Let X and Y be nonempty sets. A function f from X to Y is an assignment of exactly one element of X to each element of Y$$ f : X \to Y $$
  • A function f is said to be one-to-one, or an injunction, if and only if f(a) = f (b) implies that a = b for all a and b in the domain of f (Injunctive)$$ \forall a \forall b (a \neq b \rightarrow f(a) \neq f(b)) $$
  • A function f from X to Y is called onto, or a surjection, if and only if for every element y ∈ Y there is an element x ∈ X with f(x) = y (Surjective)$$ \forall y \in Y, \exists x \in X : f(x) = y $$
  • A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. (Bijective)$$ \forall y \in Y, \exists ! x \in X : f(x) = y $$
  • Let f be a function from the set X to the set Y and let g be a function from the set y to the set C. The composition of the functions g and f, is defined by is defined by (f ◦ g)(a) = f (g(a)).

5. Cardinality of Sets

Definition

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

To be done

References

  • Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen
  • Đại số tuyến tính, Nguyễn Hữu Việt Hưng

[Discrete Mathematics] Logic and Proof

I. Logic and Proof

 

1. Propositional Logic

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

Name Meaning Notation
negation not p $\lnot p$
disjunction p or q $p \lor q$
conjunction p and q $p \land q$
conditional if p, then q $p \rightarrow q$
biconditional p if and only if q $p \leftrightarrow q$

2. Propositional Equivalences

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.

A compound proposition that is always false is called a contradiction.

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

The compound propositions p and q are called logically equivalent if $p \leftrightarrow q $ is a tautology. ($p \equiv q$)

Equivalence Name
$$ p \lor F \equiv p $$

$$ p \land T \equiv p $$

Identity laws
$$ p \lor T \equiv T $$

$$ p \land F \equiv F $$

Domination laws
$$ p \lor p \equiv p $$

$$ p \land p \equiv p $$

Idempotent laws
$$ \lnot(\lnot p)) \equiv p $$ Double negation law
$$ p \lor q \equiv q \lor p $$

$$ p \land q \equiv q \land p $$

Commutative laws
$$ (p \lor q) \lor r \equiv p\lor(q\lor r) $$

$$ (p \land q) \land r \equiv p \land (q \land r) $$

Associative laws
$$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$

$$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$

Distributive laws
$$ \lnot (p \land q) \equiv \lnot p \lor \lnot q $$

$$ \lnot (p \lor q) \equiv \lnot p \land \lnot q $$

De Morgan’s laws
$$ p \lor (p \land q) \equiv p $$

$$ p \land (p \lor q) \equiv p $$

Absorption laws
$$ p \lor \lnot p \equiv T $$

$$ p \land \lnot p \equiv F $$

Negation laws
Table of common Logical equivalence

3. Predicates and Quantifiers

To be done

References

Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen

Nhập, xuất dữ liệu trong C++

Trong bài này, chúng ta sẽ học cách nhập vào từ bàn phím (stdin standard input device) và ghi ra màn hình (stdout standard output device).

Ta cũng cần dùng đến thư viện iostream namespace std để hỗ trợ nhập xuất. Khi muốn dùng lệnh nào nằm trong namespace std, ta có 2 cách:

  • Khai báo using namespace std ở đầu chương trình, sau đó có thể dùng các lệnh này bình thường.
  • Thêm std:: vào trước lệnh ta muốn dùng. Ví dụ như std::cin, std::endl.

Từ đây trở đi, khi gặp std:: trước một lệnh, chúng ta sẽ tự hiểu lệnh sau đó nằm trong namespace std và có 2 cách như trên để viết.

std::cin

Để nhập dữ liệu cho biến, ta dùng lệnh cin

cin >> biến;

Nếu có nhiều biến cần nhập vào, ta có thể viết liên tiếp như sau

cin >> biến 1 >> biến 2 >> … >> biến n;

Khi chạy đến lệnh cin, chương trình sẽ chờ người dùng nhập dữ liệu vào các biến tương ứng. Dữ liệu nhập vào được phân cách nhau bởi dấu cách hoặc tab hoặc enter, và luôn được hiển thị ra màn hình.

Ví dụ

int a, b;
cin >> a >> b;

Lệnh cin ở dòng 2 sẽ yêu cầu người dùng nhập vào 2 giá trị tương ứng với 2 biến số nguyên a và b.

Lưu ý

Khi nhập vào, các giá trị được phân tách nhau bởi space (dấu cách), tab (dấu tab) hay enter (dấu xuống dòng). Nếu không, mặc dù trong một số trường hợp chương trình vẫn chạy nhưng rất khó kiểm soát được giá trị các biến nhập vào.
Ví dụ: đoạn mã sau

int a,b,c;  
cin>>a>>b>>c;  
hoặc
int a,b,c;
cin>>a; cin>>b; cin>>c;
khi thực hiện, ta nhập dữ liệu từ bàn phím: 3 4 5<enter> hoặc nhập:
3<enter>
4<enter>
5<enter>
Sau khi nhập xong biến a=3, b=4 và c=5.

std::cout

Để in dữ liệu ra màn hình, ta dùng lệnh cout

cout << biểu thức;

Ta cũng có thể in hàng loạt nhiều biểu thức liên tiếp nhau

cout << biểu thức 1 << biểu thức 2 << … << biểu thức n;

Biểu thức ở đây có thể hiểu là biểu thức toán học chứa biến, hằng, hay kết quả trả về của một hàm, …

Ví dụ

int a, b;
cin >> a >> b;
cout << a << ” + ” << b << ” = ” << a + b;

Lệnh cout ở dòng 3 in ra lần lượt: giá trị biến a, chuỗi ” + “, giá trị biến b, chuỗi ” = ” và giá trị biểu thức a + b.

Một số ký tự điều khiển

  • \a’ : tiếng chuông
  • \b’ : lùi lại một bước
  • \n’ : xuống dòng
  • \t’ : dấu tab
  • \\’ : dấu \
  • \?’ : dấu ?
  • \”‘ : dấu “

Lưu ý

std::endl cũng có chức năng tương tự ‘\n’ nhưng ngoài ra endl còn làm rỗng bộ đệm đầu ra.

Ví dụ

cout << ‘\t’ << “Hello World !\n” << 0;

Kết quả:

Hello World!
0

Lưu ý

cin dùng toán tử >> còn cout dùng toán tử <<. Đừng nhầm lẫn!

cout, cin nằm trong thư viện iostream

Định dạng in

Để dùng những lệnh định sau, ngoài thư viện iostream, ta còn phải dùng thư viện iomanip để định dạng. Các định dạng này cần được cout mới có tác dụng.

std::setw(n): quy định khoảng không gian cho dữ liệu được in ra màn hình là n. Nếu dữ liệu chiếm ít không gian hơn, dữ liệu sẽ được căn  lề phải khi in ra. Ngược lại , lệnh này không có ảnh hưởng, tức dữ liệu vẫn in ra như bình thường.

std::setprecision(n): quy định số chữ số được làm tròn khi in ra là n. Số chữ số được tính từ trái qua phải.

std::fixed: lệnh này đi kèm với setprecision sẽ xác định chỉ làm tròn các chữ số ở phần thập phân.

Ví dụ

cout << 12.345 << ‘ ‘;
cout << setprecision(2) << 12.345 << ‘ ‘;
cout << fixed << setprecision(2) << 12.345;

Kết quả:

12.345 12 12.35

Một số hàm khác liên quan đến nhập xuất

std::cin.get(c): nhập 1 ký tự vào biến c.

std::cin.getline(s, n): nhập tối đa n – 1 ký tự vào xâu s (ký tự thứ n là NULL).
std::getline (cin,str): đọc xâu kí tự str, str kiểu dữ liệu string.
std::cin.ignore(n): xóa n ký tự trong bộ đệm đầu vào.

fflush(stdin): xóa toàn bộ bộ đệm đầu vào.

Có thể bạn thích:
Nhập, xuất dữ liệu từ file trong C++

Bài tập mẫu

Viết chương trình nhập vào 3 số a, b, c. In ra trung bình cộng của 3 số đó với giá trị làm tròn đến chữ số thập phân thứ 5.

Code:

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
     cout << "Nhap 3 so a, b, c: ";
     float a, b, c;
     cin >> a >> b >> c;
     float avr = (a + b + c) / 3;
     cout << fixed << setprecision(5) << avr << endl;
     system("pause"); // Tạm dừng màn hình chờ nhấn Enter
     return 0;
}

Set trong C++

Tổng quan

  • Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys).
  • Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép toán so sánh.
  • Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo ý mình.
  • Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).

Khai báo:

#include <set> 
set <int> s;
set <int, greater<int> > s;
Hoặc viết class so sánh theo ý mình:
struct cmp{
bool operator() (int a,int b) {return a<b;}
};
set <int,cmp > myset ;

Capacity:

  • size : trả về kích thước hiện tại của set. ĐPT O(1)
  • empty : true nếu set rỗng, và ngược lại. ĐPT O(1).

Thay đổi:

  • insert : Chèn phần tử vào set. ĐPT O(logN).
  • erase : có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa. ĐPT O(logN).
  • clear : xóa tất cả set. ĐPT O(n).
  • swap : đổi 2 set cho nhau. ĐPT O(n).

Truy cập phần tử:

  • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy itarator trỏ về “end” của set. ĐPT O(logN).
  • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
  • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
  • count : trả về số lần xuất hiện của khóa trong container. Nhưng trong set, các phần tử chỉ xuất hiện một lần, nên hàm này có ý nghĩa là sẽ return 1 nếu khóa có trong container, và 0 nếu không có. ĐPT O(logN).

 

Chương trình Demo 1:

#include <iostream>
#include <set>
using namespace std; 
main() {
      set <int> s;
      set <int> ::iterator it; s.insert(9);  // s={9}
      s.insert(5);  // s={5,9} cout << *s.begin() << endl; //In ra 5 s.insert(1);  // s={1,5,9} cout << *s.begin() << endl; // In ra 1
 
      it=s.find(5);
      if (it==s.end()) cout << "Khong co trong container" << endl; else  cout << "Co trong container" << endl;

      s.erase(it);  // s={1,9}
      s.erase(1);  // s={9}

      s.insert(3);  // s={3,9}
      s.insert(4);  // s={3,4,9}

      it=s.lower_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 4" << endl; else cout << "Phan tu be nhat khong be hon 4 la " << *it << endl;  // In ra 4

      it=s.lower_bound(10);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 10" << endl; else cout << "Phan tu be nhat khong be hon 10 la " << *it << endl; // Khong co ptu nao           

      it=s.upper_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set lon hon 4" << endl; else cout << "Phan tu be nhat lon hon 4 la " << *it << endl;  // In ra 9                

      /* Duyet set */

      for (it=s.begin();it!=s.end();it++) { cout << *it <<  " ";
      }
      // In ra 3 4 9

      cout << endl; system("pause");
}

Lưu ý: Nếu bạn muốn sử dụng hàm lower_bound hay upper_bound để tìm phần tử lớn nhất “bé hơn hoặc bằng” hoặc “bé hơn” bạn có thể thay đổi cách so sánh của set để tìm kiếm. Mời bạn xem chương trình sau để rõ hơn:

#include <iostream>
#include <set>
#include <vector> using namespace std;
main() {
      set <int, greater <int> > s;
      set <int, greater <int> > :: iterator it; // Phép toán so sánh là greater

      s.insert(1);  // s={1}
      s.insert(2);  // s={2,1}
      s.insert(4);  // s={4,2,1}
      s.insert(9);  // s={9,4,2,1}

      /* Tim phần tử lớn nhất bé hơn hoặc bằng 5 */ it=s.lower_bound(5);
      cout << *it << endl;  // In ra 4

      /* Tim phần tử lớn nhất bé hơn 4 */ it=s.upper_bound(4);
      cout << *it << endl;  // In ra 2

      system("pause");
}

Tạo form trong HTML

FORM được sử dụng để chuyển dữ liệu liệu từ người dùng nhập vào đến web server.
Form bao gồm các thành phần nhập liệu (input elements) như: Text box, hộp kiểm, nút tùy chọn, Submit…
Bài viết này mình sẽ hướng dẫn các bạn một số các thành phần của Form hay được sử dụng nhất. Mình sẽ cố gắng giải thích để mọi người có thể hiểu.
Trong tài liệu HTML form được định nghĩa bằng cặp thẻ <form></form>
Các thẻ nằm giữa cặp thẻ <form></form> được gọi là các thành phần của Form

Các thành phần Form

Thành phần được sử dụng nhiều nhất trong form là thẻ <input />. Ta sử dụng <input /> để định nghĩa các thành phần của form như: Trường nhập liệu Text, các hộp kiểm, các nút tùy chọn, trường password, thành phần submit, các button, File upload.

1. Trường text
User name:

Code:

<input type="text" name="username" size="30" />

2. Trường password
Pass:

Code:

<input name="pass" size="30" type="password" />

3. Checkbox (Hộp kiểm)

Cho phép chọn nhiều thành phần từ danh sách đưa ra

Send my to email
Send my to phone

<input name="opt" type="checkbox" /> Send my to email
<input name="opt" type="checkbox" />Send my to phone

4. Radio button

Khác với checkbox, Radio chỉ phép phép chọn một thành phần từ danh sách đưa ra, các phần tử trong danh sách phải có cùng tên, như ví dụ sau ta
sẽ tạo ra hai thành phần Radio button có cùng tên là name=”gender”

Male
Female

<input type="radio" name="gender" checked /> Male 
<input type="radio" name="gender" /> Female

5. File upload

<input type="file" name="FILE" size="40" />

6. Button

Tạo ra một nút bấm trên form

<input type="button" name="button" value="Click me" />

7. Submit Button

Tạo nút submit trên form. Khi nút Submit được nhấn, dữ liệu trên form sẽ đuợc xử lý và gửi đi

<input type="submit" name="submit" value="Submit" />

8. Reset Button

Tạo nút Reset trên form. Khi nhấn nút Reset dữ liệu nhập vào form sẽ được reset về giá trị ban đầu của form

<input type="reset" name="cancel" value="Reset" />

Ta nhận thấy sự khác biệt giữa các thành phần input là thuộc tính type. Thuộc tính type sẽ quy định thành phần input này là Text, password, checkbox, hay button …

9. Dropdown list

Student
Bussiness
Manager
Other…

<select name="job">
      <option value="Student">Student</option>
      <option value="Bussiness">Bussiness</option>
      <option value="Manager">Manager</option>
      <option value="Other">Other...</option>
</select>

KẾT LUẬN

– Mỗi thành phần form đều được gán một tên (name=”ten_thanh_phan”): đây chính là tên biến được sử dụng trong các ngôn ngữ lập trình web như php hay asp.net…, Riêng thành phần Radio trong cùng một nhóm sẽ được đặt cùng tên.

– Thuộc tính value=”Giá trị”: đây là giá trị (dữ liệu) ban đầu của thành phần form, các thành phần không có thuộc tính value giá có giá trị ban đầu là rỗng (null).

– Các Phương thức hoạt động của form bạn có thể xem ở các bài tiếp thep.

QBHEAP – spoj

Đề bài:

Thuật toán:

  • Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 20000;
string s;
priority_queue <int> h;
char key;
int num, a[MAXN];
 
bool cmp(int a, int b) {
    return (a > b);
}
 
int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}
const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]<x do dec(J);
                if i<=j then
                        begin
                            swap(res[i],res[j]);
                            inc(i);dec(j);
                        end;
            until i>j;
            if i<r then qs(i,r);
            if j>l then qs(l,j);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (j<nh) and (h[j]<h[j+1]) then inc(j);
        if h[j]>h[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
procedure push(x:longint);
begin
        inc(nh);
        h[nh]:=x;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;
 
    close(input);close(output);
end;
begin
    main;
end.

Các hàm toán học có sẵn trong C++

YeuLapTrinh.pw xin được tóm tắt một số các  hàm toán học hay dùng. Các hàm này đều được khai báo trong file nguyên mẫu math.h.

  1. Các hàm số học
  • abs(x), labs(x), fabs(x) : trả lại giá trị tuyệt đối của một số nguyên, số nguyên dài và số thực.
  • pow(x, y) : hàm mũ, trả lại giá trị x lũy thừa y (xy).
  • exp(x) : hàm mũ, trả lại giá trị e mũ x (ex).
  • log(x), log10(x) : trả lại lôgarit cơ số e và lôgarit thập phân của x (lnx, logx) .
  • sqrt(x) : trả lại căn bậc 2 của
  • atof(s_number) : trả lại số thực ứng với số viết dưới dạng xâu kí tự
  1. Các hàm lượng giác
  • sin(x), cos(x), tan(x) : trả lại các giá trị sinx, cosx,

 

Bạn nên tham khảo bài viết: Các hàm làm tròn số trong C++