Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ<br /> GIẢI THUẬT<br /> NGÔ QUANG THẠCH<br /> Email: thachnq@gmail.com<br /> ĐT: 01273984123<br /> <br /> Chương 5: Tìm kiếm<br /> <br /> Giới thiệu<br /> <br /> Tìm kiếm tuyến tính<br /> <br /> Tìm kiếm nhị phân<br /> <br /> Giới thiệu<br /> Trong cuộc sống hàng ngày<br />  Các hệ lưu trữ, hệ thống nội bộ, hệ thống bên ngoài…<br />  Quản lý dữ liệu, quản lý thông tin,…<br /> …<br /> =>Tìm kiếm thường được thực hiện nhiều nhất để khai thác<br /> thông tin. Các thuật toán tìm kiếm được sử dụng được coi là<br /> các kỹ thuật cơ sở cho lập trình máy tính<br /> <br /> Giới thiệu<br /> Tìm kiếm một phần tử nào đó của một tập đối tượng<br /> theo một tiêu chí đề ra là bài toán phổ biến trong tin<br /> học<br />  Tìm kiếm hồ sơ, lý lịch, tập tin,…<br />  Tìm kiếm thông tin, công văn, văn bản, …<br /> <br /> <br /> Giới thiệu<br /> Mô tả bài toán tìm kiếm:<br /> “cho một vec tơ A bao gồm n phần tử, có giá trị là các số<br /> khác nhau : A[1], A[2], A[3],…, A[n]”<br /> “cho một số X, hãy tìm xem có phần tử nào của A mà giá<br /> trị của nó bằng X không”<br /> => Tìm kiếm sẽ “được thỏa” khi có, hoặc “không thỏa”<br /> khi không có phần tử nào có giá trị bằng X<br /> <br />