1. Giới thiệu hội thảo

2. Ban tổ chức và các nhà tài trợ

3. Chương trình hội thảo

4. Danh sách báo cáo và tóm tắt báo cáo

5. Danh sách đại biểu tham dự

ỨNG DỤNG MẠNG NƠ RON HOPFIELD
GIẢI MỘT SỐ BÀI TOÁN VỀ ĐỒ THỊ
 

Đặng Quang Á Viện

Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam,

Trần Văn Thái

Trường Cao đẳng Cơ khí luyện kim, Thành phố Thái Nguyên
 

Từ sau công trình đầu tiên của Hopfield và Tank năm 1985 về sử dụng mạng nơ ron giải bài toán người bán hàng, mạng nơ ron nhân tạo ngày càng chứng tỏ là một công cụ hữu hiệu giải các bài toán tối ưu tổ hợp và thỏa mãn ràng buộc. Trong báo cáo này chúng tôi trình bày kết quả hiện thực hóa phương pháp mạng nơ ron giải hai bài toán của lý thuyết đồ thị là bài toán tô mầu bản đồ và bài toán phẳng hóa đồ thị, đồng thời đề cập một vài vấn đề phát sinh khi sử dụng mạng nơ ron giải các bài toán tối ưu tổ hợp.[Quay lại]

EXACT PENALTY TECHNIQUES IN D.C. PROGRAMMING
 

Lê Thị Hoài An, Phạm Đình Tảo, Huỳnh Văn Ngãi

Khoa Toán, Đại học Quy Nhơn

Trong báo cáo này chúng tôi giới thiệu một vài kết quả về phương pháp phạt chính xác (exact penalty) trong bài toán quy hoạch với hàm mục tiêu là hiệu hai hàm lồi (d. c. programming).[Quay lại]

PARAMETRIC MULTIVALUED SYMMETRIC
VECTOR EQUILIBRIUM PROBLEMS
 

Lâm Quốc Anh

Department of Mathematics, Teacher College, Cantho University

Phan Quốc Khánh

Department of Mathematics, International University, Vietnam National University

Trần Tuấn Kiệt

Department of Mathematics, Cantho College, Cantho University
 

In this paper we present existence results for multivalued symmetric vector equilibrium problems. Furthermore, we derive conditions for the local uniqueness and Lipschitz continuity of parametric multivalued symmetric vector equilibrium problems. Moreover, we consider both weak multivalued symmetric vector equilibrium problems and a strong version of them.[Quay lại]

LOWER AND UPPER SEMICONTINUITY OF
SOLUTIONS TO GENERAL MULTIVALUED VECTOR
QUASIEQUILIBRIUM PROBLEMS
 

Lâm Quốc Anh

Department of Mathematics, Teacher College, Cantho University

Phan Quốc Khánh

Department of Mathematics, International University, Vietnam National University 

Đinh Ngọc Quý

Department of Mathematics, Cantho College, Cantho University
 

We consider six kinds of multivalued vector quasiequilibrium problems in topological spaces. The lower, upper and Hausdorff-upper semicontinuity as well as closedness of the solution sets are established under weak assumptions. Various examples are provided to show that many corollaries of our results for special cases are strictly stronger than recent existing results. Some other theorems turn to be new even for special cases.[Quay lại]

LOCAL UNIQUENESS AND HÖLDER
CONTINUITY OF SOLUTIONS TO EQUILIBRIUM PROBLEMS
Lâm Quốc Anh

Department of Mathematics, Teacher College, Cantho University

Phan Quốc Khánh

Department of Mathematics, International University, Vietnam National University

Đặng Thị Mỹ Vân

Department of Mathematics, Cantho College, Cantho University
 

Two kinds of parametric multivalued vector equilibrium problems are considered. Sufficient conditions for the local uniqueness and Hửlder continuity of the solutions are established under weak conditions on Hửlder continuity and relaxed monotonicity of the data of the problems. Some new results for variational inequalities are derived, followed by examples showing the case where they are applicable while the known results do not work.[Quay lại]

METHODS FOR FINDING GLOBAL OPTIMIZATION TO
A CLASS OF MATHEMATICAL PROGRAMS WITH
EQUILIBRIUM CONSTRAINTS
Phạm Ngọc Anh

Posts and Telecommunications Institute of Technology, Hanoi, Vietnam

Le Dung Muu

Optimization and Control Department, Hanoi Institute of Mathematics
 

Mathematical programs with equilibrium constraints, shortly MPEC are optimization problems with paremetric variational inequality constraints. MPEC problems include bilevel convex programmming problems as well as linear optimization over the efficient set as special cases. Due to its nested structure, a MPEC problem is a difficult global optimization one, since its feasible domain, in general, is not convex even not conected. Unless very special cases, it is less hope to develope an efficinet method for solving MPEC problems globally. In practice, in some cases, instead of finding a global solution, it is suffices to find a solution that is ”nearly” feasible and whose value, with repect to the objective function, is not greater than a given desired value. In this paper we consider MPEC problems in the linear case. We use a dual formulation of this problem to develop two decomposition branch and bound algorithms for finding a global optimal solution of a linear mathematical program with equilibrium constraints (AMPEC). The bounding uses only quadratical convex-linear subprograms, the branching takes over a simplex in the criteria space. [Quay lại]

VỀ MỘT DẠNG MỞ RỘNG CÔNG THỨC NEWTON-LEIBNITZ

CHO DƯỚI VI PHÂN CLARKE
Nguyễn Huy Chiêu

Khoa Toán, Đại học Vinh
 

Nếu f : [a, b] R là một hàm Lipschitz xác định trên đoạn [a, b] R thì

,                              (*)
ở đó tích phân của ánh xạ dưới vi phân Clarke được hiểu theo nghĩa tích phân Aumann.
Câu hỏi đặt ra là: Phải chăng vế phải của (*) là tập một điểm?
Báo cáo này đề cập đến vấn đề nêu trên.[Quay lại]
 

ONTOLOGY OPTIMIZATION:
PROBLEMATICS AND METHODOLOGY
 

Truong My Dung

Khoa Công nghệ thông tin, ĐH Khoa học tự nhiên, ĐH Quốc gia Tp. HCM

Nguyen Dinh Ngoc

Đại học Thăng Long, Hà Nội

In the study of UKARL use cases for SEKT, especially for ontology usage mining, some methods and techniques should be required:
First of all, means are required to trace and store the actual usage of the system and of underlying ontology employed. Moreover, it is indispensable to store changes that are made to the ontology in case the system under consideration employs an evolving ontology.
Second, adequate optimality criteria are needed which allow for an estimation of the quality of the users Interaction with the system. Such measures ought to reflect the users Information needs and how those are fulfilled by the system used. When considering the improvement of system usage as an optimization Problem, it may be feasible to apply machine learning techniques to optimize the measures mentioned and thus to refine and improve (optimize?) the underlying ontology.
Third, in order to realize these ideas, of course it is necessary to dispose of methods to adapt the systems structure (i.e. the ontology), with respect to optimality of use. Another required technique concerns the analysis of different users and user groups, i.e. the determination of user profiles, for which the underlying ontology may be tailored.
(UKARL: University of Karlsruhe, Institut für Angewandte Informatik,
SEKT: Semantically Enabled Knowledge Technologies )[Quay lại]

MỘT TIẾP CẬN MỚI GIẢI HỆ PHƯƠNG TRÌNH
TUYẾN TÍNH CỠ LỚN
 

Phạm Cảnh Dương

Viện Toán học, Viện Khoa học và công nghệ Việt Nam

Lê Thanh Huệ

Khoa Công nghệ thông tin, Đại học Mỏ - Địa chất

Nguyễn Hoàn Vũ
 

Bài này trình bày một tiếp cận mới giải hệ phương trình tuyến tính dạng
 

Ax = b                                                         (1)
 

với A là một ma trận vuông nxn, b là một véc tơ cho trước trong Rn, bằng một phương pháp lặp dựa trên các phép chiếu liên tiếp kiểu Kaczmarc trên các mặt cầu được xây dựng một cách phù hợp. Bài toán (1) là cơ sở cho nhiều thuật toán và các nghiên cứu lý thuyết trong nhiều lĩnh vực ứng dụng của toán học hiện đại như: Các bài toán xử lí tín hiệu, mô phỏng các hệ động lực, lý thuyết tối ưu và vận trù học, kiến trúc vật liệu, dự báo thống kê,…

Việc giải hệ phương trình này có thể quy về một bài toán tương đương là xác định một mặt cầu ngoại tiếp một tập n+1 điểm độc lập tuyến tính cho trước trong Rⁿ.[Quay lại]
 

FROM LINEAR TO CONVEX SYSTEMS:

CONSISTENCY, FARKAS LEMMA AND APPLICATIONS
 

N. Dinh

Khoa Toán-Tin học, Đại học Sư phạm TP Hồ Chí Minh
 M.A. Goberna, M.A. López

The report analyzes inequality systems with an arbitrary number of proper lower semicontinuous convex constraint functions and a closed convex constraint subset of a locally convex topological vector space. More in detail, starting from well-known results on linear systems (with no constraint set), the paper reviews and completes previous works on the above class of convex systems, providing consistency theorems, two new versions of Farkas' lemma, and optimality conditions in convex optimization. A new closed cone constraint qualification is proposed. Suitable counterparts of these results for cone-convex systems are also given.[Quay lại]

A VERSION OF FARKAS LEMMA AND ITS APPLICATION

TO CONVEX PROGRAMS WITH INFINITELY MANY CONSTRAINTS

Nguyen Dinh

Khoa Toán-Tin học, Đại học Sư phạm TP Hồ Chí Minh

Ta Quang Son

Khoa Tự nhiên, Cao đẳng Sư phạm Nha Trang

In this report we introduce a generalized non-asymptotic version of Farkas lemma for convex systems. The result is then apply to infinite convex problems to deduce optimality conditions, duality and saddle point theorems for this class of problems.[Quay lại]

ON THE EXISTENCE OF SOLUTIONS TO
VARIATIONAL INCLUSION PROBLEMS

N. X. Hai

Posts and Telecommunications Institute of Technology, Hochiminh City

P. Q. Khanh

International University, VNU-Hochiminh City

T. H. Nuong

University of Natural Sciences, VNU-Hochiminh City

We consider two kinds of general variational inclusion problem, which contain most variational inclusion problems studied in the literature. Sufficient conditions for the solution existence are established. These conditions contain several existing results as special cases. It is also that, when applied to these cases, our assumptions are weaker and hence the theorems work more effectively.[Quay lại]
 

PHƯƠNG PHÁP BIẾN PHÂN

VÀ PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG TRONG XỬ LÝ ẢNH
 

Đinh Nho Hào

Viện Toán học, Viên Khoa học và Công nghệ Việt Nam

Xử lý ảnh đóng một vai trò hết sức quan trọng trong nhiều lĩnh vực khác nhau của đời sống, khoa học, kỹ thuật, y học,... Các phương pháp toán học khác nhau đã được sử dụng rộng rãi trong lĩnh vực này bắt đầu từ những năm 50 của thế kỷ trước. Trong báo cáo này chúng tôi giới thiệu hai phương pháp mới, đó là phương pháp biến phân và phương pháp phương trình đạo hàm riêng trong lĩnh vực xử lý ảnh. Hai phương pháp này đặc biệt được chú ý trong khoảng 20 năm lại đây. Chúng tôi giới thiệu ý tưởng chung của hai phương pháp này và đưa ra các mô hình toán học tương ứng trong các bài toán về loại nhiễu cho ảnh (image denoising), so sánh ảnh (image registration), phân khúc ảnh (image segmentation), khôi phục và tái tạo ảnh (image inpainting), xác định dòng quang học (identify optical flow), ...

Hai phương pháp kể trên thường dẫn đến những bài toán tối ưu không lồi, hoặc không khả vi, những bài toán đặt không chỉnh cho phương trình đạo hàm riêng tuyến tính cũng như phi tuyến. Lý thuyết toán học và các phương pháp số hữu hiệu cho những vấn đề kể trên cũng sẽ được giới thiệu trong báo cáo này.[Quay lại]
 

NGỮ ÂM ĐÔNG-TÂY: NHẬN THỨC VÀ TIẾP THU

Doãn Tam Hoè

Khoa Công nghệ Thông tin, Đại học Xây dựng Hà Nội
 

Báo cáo phân tích ngữ âm tiếng Việt so sánh với ngữ âm Ấn Âu thông qua hàm xấp xỉ. Kết quả cho thấy những ảnh hưởng của ngữ âm đến âm nhạc, đến khả năng nhận thức và tiếp thu ngôn ngữ liên quan đến vấn đề giảng dạy và học tập ngoại ngữ, đồng thời chỉ ra xu hướng phát triển của ngữ âm tiếng Việt hiện đại. Qua phân tích ngữ âm chúng ta sẽ tìm thấy hướng đi cho các giải pháp nhận dạng tiếng nói và dạy tiếng cho người và máy.[Quay lại]
 

PHƯƠNG PHÁP CHIA ĐÔI GIẢI LỚP BÀI TOÁN TỐI ƯU

CÓ MẶT MỨC CỦA HÀM MỤC TIÊU LÀ CÁC PHẲNG
 

Doãn Tam Hoè

Khoa Công nghệ Thông tin, Đại học Xây dựng Hà Nội
 

Báo cáo trình bày một kết quả nhỏ mà tác giả áp dụng giải các bài toán tối ưu mà hàm mục tiêu là hàm tuyến tính, phân tuyến tính, ... với miền ràng buộc tuỳ ý. Phương pháp nêu ra ở đây sẽ giảm nhẹ khối lượng tính toán đáng kể nếu như áp dụng kết hợp với phương pháp Monte-Carlo.[Quay lại]
 

NỬA NHÓM TÁC ĐỘNG MỜ
Phan Trung Huy

Khoa Toán Tin ứng dụng, ĐHBK Hà Nội

Nguyễn Thị Thanh Huyền

Khoa Toán Tin ứng dụng, ĐHBK Hà Nội

Bài này trình bày về một số hình thức nửa nhóm tác động mờ, là sự mở rộng tự nhiên của các hình thức nửa nhóm mờ, otomat mờ đã được các tác giả (P.Huy1998, T.Huyền-P.Huy 2002) xem xét. Một số hình thức tác động mờ lý thú liên quan trong lĩnh vực tìm kiếm mẫu, nghiên cứu về đặc tính tập không tránh được trong lĩnh vực tổ hợp trên từ được trình bày.[Quay lại]
 

TIẾP CẬN MỚI TRONG MÔ PHỎNG CÁC MẠCH

VÀ THUẬT TOÁN LƯỢNG TỬ:

ĐẠI SỐ QUAN HỆ CÀI ĐẶT TRÊN MÔI TRƯỜNG TÍNH TOÁN

NHỜ PHƯƠNG PHÁP TRUY VẤN SQL

Phan Trung Huy,  Lê Hùng Sơn, Chu Mạnh Dũng, Bùi Kiên Cường,
Nguyễn Thanh Hải1, Trần Minh Hoàng, Vương Mai Phương, Khuất Thành Nam

Khoa Toán Tin ứng dụng, ĐHBK Hà Nội

Benioff và Feynman đã chỉ ra trên cơ sở vật lý lượng tử một mô hình tính toán mới: máy tính lượng tử. Từ cơ sở đã nêu, đặc biệt là sau thuật toán lượng tử lý thuyết nổi tiếng của Peter Shor 1994 để phân tích hợp số (cơ sở phá mã RSA) và sau này IBM 2001 đã xây dựng một mô hình thử nghiệm thực trên 7-qubit cho thuật toán này..., lý thuyết về thuật toán lượng tử phát triển ngày càng sâu và rộng. Mặc dầu những chiếc máy tính lượng tử công nghiệp chưa ra đời, nhưng khả năng to lớn của nó đã buộc các nước công nghiệp tăng cường đầu tư nghiên cứu. Ở các nước nghèo như Việt nam, để tránh bị lạc hậu trong lĩnh vực sôi động này, cần có những bước đi ban đầu thích hợp và kịp thời. Học tập và rút kinh nghiệm của nhiều nước và Labo trên thế giới, việc đầu tư vào hướng mô phỏng tính toán lượng tử dựa trên dàn máy tính thông dụng là rẻ tiền và phù hợp. Hiện nay trên thế giới xuất hiện rất nhiều chương trình mô phỏng tính toán lượng tử như: labo của Kieu Tien Dung (Centre for atom optics and ultrfast spectroscopy, Swinburne University of Technology, Howthorn 3122, Australia), Gregory David Baker (Computer science at Macquaie University) với hướng tiếp cận dùng lập trình thủ tục, Bernhard Oemer (Department of Theoretical Physics Technical University of Vienna) với hướng tiếp cận dùng C/C++, chương trình jaQuzzi (www.physics.bufalo.edu/~phygons/jaQuzzi) với hướng tiếp cận dùng Java,… Với một số chương trình dùng Mathemetica hay Mathlab, việc kiểm soát dữ liệu là không chủ động vì nó phụ thuộc vào các nhà thiết kế Mathemetica, Mathlab và chưa có tương tác trợ giúp thiết kế mạch lượng tử hướng giao diện, quản lý dữ liệu lớn hướng cơ sở dữ liệu có thể chạy dài ngày hay ngắt quãng không liên tiếp. Trong bài này, chúng tôi trình bày một tiếp cận mới trong mô phỏng các thuật toán lượng tử, dựa trên mô hình đại số quan hệ và môi trường tính toán SQL (Structured Query Languages), khác hẳn so với các tiếp cận khác trên thế giới. Phương pháp này cho phép quản lý bộ nhớ rất lớn mềm dẻo, theo cách thức cơ sở dữ liệu, người lập trình không cần bận tâm lo quản lý bộ nhớ, dễ dàng mô phỏng khả năng siêu trạng thái chồng chất của qubit, và kết quả quan trọng chỉ ra rằng các tính toán lượng tử có thể được thực hiện dựa trên các câu lệnh truy vấn SQL trên cơ sở dữ liệu. Từ kết quả lý thuyết trên, một chương trình mô phỏng tính toán lượng tử với kiến trúc ba tầng độc lập đã được xây dựng, có thể trở thành công cụ đắc lực cho các Labo, nhóm nghiên cứu và giảng dạy về tính toán lượng tử. Chương trình cho phép người nghiên cứu kiểm định thuật toán lượng tử chỉ cần vẽ mạch (tầng giao diện) là chạy. Mạch vẽ thiết kế nếu muốn, có thể được đóng gói dưới định dạng ngôn ngữ con QuML (tầng thứ hai) là một ngôn ngữ được nhóm xây dựng theo chuẩn XML, cho phép gọi ứng dụng SQL (tầng thứ ba) chạy để thực hiện tính toán mô phỏng. [Quay lại]
 

MÔ PHỎNG NGẪU NHIÊN
 

Phạm Văn Khánh

Bộ môn Toán, Khoa CNTT, Học viện KTQS

Trong báo cáo này tôi đưa ra cơ sở lý thuyết và các thuật toán để mô phỏng các đại lượng ngẫu nhiên, làm cơ sở cho các quá trình tính toán phức tạp hơn. Điểm mới trong báo cáo này là đưa ra các thuật toán mô phỏng các quá trình ngẫu nhiên không thuần nhất.
Bố cục của báo cáo như sau:
I. Giới thiệu chung
II. Những kĩ thuật chung để mô phỏng biến ngẫu nhiên
    II.1 Phương pháp biến đổi nghịch đảo
    II.2 Phương pháp loại bỏ
    II.3 Phương pháp hàm tốc độ hỏng
III. Những kĩ thuật đặc thù để mô phỏng biến ngẫu nhiên
    III.1 Phân phối Chuẩn
    III.2 Phân phối Gama
    III.3 Phân phối bình phương
    III.4 Phân phối Beta(n,m)
    III.5 Phân phối mũ –Thuật toán Von-Neuman
IV.Mô phỏng những phân phối rời rạc
V. Mô phỏng quá trình Poisson không thuần nhất
    Phương pháp 1: Phương pháp lấy mẫu Poisson
    Phương pháp 2: Phân phối có điều kiện của thời gian đến
    Phương pháp 3: Mô phỏng biến cố thời gian[Quay lại]
 

FIRST AND SECOND ODER OPTIMALITY CONDITIONS FOR

MULTIOBJECTIVE OPTIMIZATION

USING HADAMARD DIRECTIONAL DERIVATIVES

Phan Quoc Khanh

International University, Vietnam National University, Hochiminh City

Nguyen Dinh Tuan

University of Natural Sciences, Vietnam National University, Hochiminh City

We use the notion of first and second order Hadamard directional erivatives for vector functions to derive first and second order optimality conditions of the Fritz John type for multiobjective optimization problems in the finite dimensional case. The necessary conditions are established for weak efficiency and the sufficient conditions for a point to be an isolated efficiency of first or second order.[Quay lại]
 

ĐIỀU KIỆN TỐI ƯU CHO MỘT LỚP BÀI TOÁN
ĐIỀU KHIỂN DẠNG XUNG

Phạm Thế Long ,Nguyễn Thanh Hải

Học viện Kỹ thuật Quân sự

Báo cáo trình bày về việc mô hình hóa một số bài toán thực tế trong kỹ thuật và trong kinh tế dưới dạng bài toán điều khiển tối ưu với điều khiển dạng xung.

Báo cáo phát biểu dạng tổng quát của một lớp bài toán điều khiển tối ưu tuyến tính với điều khiển dạng xung, đưa ra và chứng minh các điều kiện tối ưu, gần tối ưu cho lớp bài toán đó.[Quay lại]
 

HỆ THỐNG MÔ PHỎNG BAY VÀ ĐỒ HỌA

Lê Thị Minh Nghĩa, Nguyễn Duy Thiện, Kim Hải Quang

Bộ môn Kỹ thuật Hàng không, Đại học Bách khoa Tp Hồ Chí Minh

Báo cáo trình bày tổng quan về Hệ thống mô phỏng bay gồm các module như: mô hình và mô phỏng, giao diện đồ họa, thiết bị điều khiển, thiết bị hiển thị và mô phỏng buồng lái đã được phát triển tại Bộ môn Kỹ thuật Hàng không, trường Đại học Bách khoa thành phố Hồ Chí Minh. Nội dung trình bày được nhấn mạnh hơn vào Giao diện đồ họa và những thuật toán được áp dụng gồm: thuật toán tạo địa hình từ bản đồ độ cao thực, cây cối, sông, nhà cửa, sân bay, mây, các hiệu ứng về bầu trời, ánh sáng, khói, và các góc định hướng, góc nhìn, tầm nhìn được triển khai trong đề tài.[Quay lại]

MODULE GIẢI HỆ PHƯƠNG TRÌNH
TRONG MÔ PHỎNG BAY

Lê Thị Minh Nghĩa,Nguyễn Thanh Hoàng King

Bộ môn Kỹ thuật Hàng không, Đại học Bách khoa Tp Hồ Chí Minh

Bài báo cáo trình bày về việc thiết lập hệ phương trình vi phân chuyển động của máy bay và các phương pháp giải thường được áp dụng trong mô phỏng bay. Thuật toán giải được sử dụng là Runge-Kutta-Fehlberg (Runge-Kutta bậc 4,5) và Runge-Kutta-Verner (Runge-Kutta bậc 7,8), trong đó việc kiểm soát sai số trong quá trình giải dựa vào việc thay đổi bước thời gian là một ưu điểm. So sánh và đánh giá kết quả của các thuật giải đã được thực hiện.[Quay lại]

VỀ TÍNH TOÁN SONG SONG

Hoàng Xuân Phú

Viện Toán học, Viện Khoa học và Công nghệ Việt Nam

Để giúp cho những người chưa có dịp tiếp xúc hiểu thêm đôi chút về lĩnh vực tính toán song song, chúng tôi sẽ trình bày mấy nét đại cương liên quan đến

• máy tính song song,

• phạm vi sử dụng và hiệu quả,

• thuật toán và lập trình song song,

• công cụ trao đối thông tin trong tính toán song song và

• ví dụ về mô phỏng song song.[Quay lại]

RỜI RẠC HÓA THEO THỜI GIAN VÀ LƯỢC ĐỒ

BIẾN PHÂN CHO MỘT SỐ BÀI TOÁN CHUYỂN PHA

Christian Rohde

Đại học Freiburg, Cộng hòa liên bang Đức,

Mai Đức Thành

Khoa khoa học ứng dụng, Đại học Bách khoa, Thành phố Hồ Chí Minh

Báo cáo này đề cập đến vấn đề tồn tại nghiệm trong chuyển pha động lực học.
Đối với bài toán trong trường hợp một chiều, chúng tôi rời rạc hóa theo thời gian hệ gồm hai phương trình biểu diễn sự cân bằng động lượng và khối lượng. Các phương trình được tạo thành sau đó có kiểu của phương trình Euler của một bài toán cực tiểu hóa mà dưới những giả thiết nhất định, thừa nhận một nghiệm duy nhất. Điều này cho chúng ta một phương pháp hữu hiệu để xây dựng nghiệm xấp xỉ của bài toán đã nêu qua một lược đồ biến phân. Cụ thể, chúng tôi thực hiện phương pháp trên hai mô hình: một mô hình với các số hạng địa phương chứa đạo hàm cấp hai và cấp ba theo biến không gian, và một mô hình chứa một số hạng của tích chập toàn cục – các số hạng này biểu diễn đột nhớt và độ căng bề mặt. Chúng tôi chứng minh sự hội tụ của nghiệm xấp xỉ về một nghiệm của bài toán mà nghiệm này thỏa mãn bất đẳng thức tán xạ tự nhiên. Trong cả hai trường hợp chứng minh của chúng tôi dựa trên sự rời rạc hóa ẩn theo thời gian và giải tích của một bài toán tối ưu hóa tại mỗi bước thời gian. Cuối của báo cáo sẽ có những vấn đề mở cho bài toán chuyển pha nhiều chiều được đưa ra và thảo luận.

[Quay lại]

XẾP THỜI KHÓA BIỂU MÔN HỌC Ở TRƯỜNG ĐẠI HỌC:
HƯỚNG TIẾP CẬN GIẢI HỆ RÀNG BUỘC
VÀ TÌM KIẾM CỤC BỘ

Võ Hoàng Tam

Khoa Công nghệ thông tin, Đại học Bách khoa thành phố Hồ Chí Minh

Nội dung chính của đề tài này là nghiên cứu cách tiếp cận phương pháp giải hệ ràng buộc và tìm kiếm cục bộ để áp dụng vào việc giải bài toán xếp thời khóa biểu môn học ở Trường Đại học Bách khoa Tp. HCM. Trên cơ sở đó, một chương trình xếp thời khóa biểu tự động được hiện thực.

Bài toán xếp thời khóa biểu môn học ở trường đại học Bách khoa là xây dựng một thời khóa biểu cho các lớp môn học một cách khả thi, thỏa mãn mọi ràng buộc cứng và tối thiểu hóa sự vi phạm các ràng buộc mềm trên một tập dữ liệu về các lớp môn học và phân tiết, phòng học và sức chứa. Vì quỹ phòng học của Trường có giới hạn, chúng tôi tiến hành xếp thời khoá biểu đồng thời cho toàn bộ các lớp môn học được mở trong học kì, chứ không tiến hành xếp thời khoá biểu lần lượt cho các lớp môn học của từng Khoa với những dãy phòng học chỉ dành riêng cho Khoa đó. Quá trình giải quyết bài toán được chia làm hai giai đoạn:

Ở giai đoạn đầu, các ràng buộc cứng của bài toán được thỏa mãn để tạo ra một thời khóa biểu khả thi ban đầu. Giải thuật được dùng để thỏa mãn ràng buộc cứng kết hợp một số kĩ thuật sau: tìm kiếm không quay lui (Backtracking-free), kiểm tra hướng tới (Look-Ahead) và tìm kiếm cục bộ (Local search). Sự kết hợp các ưu điểm của các kĩ thuật trên vào một giải thuật chung là rất hiệu quả trong việc giải quyết bài toán xếp thời khóa biểu môn học (được xem là bài toán NP).

Ở giai đoạn sau, các ràng buộc mềm được xem xét để cải tiến chất lượng của thời khóa biểu đã được tạo ra ở giai đoạn đầu. Một số giải thuật đã được hiện thực, khảo sát và đánh giá: Min-Conflict Hill Climbing (MCHC), WSAT, Min-Conflict Random Walk (MCRW). Kế thừa và phát triển ý tưởng của các giải thuật này, chúng tôi đã đề xuất hướng giải quyết cải tiến hơn cho bài toán tối ưu ràng buộc mềm: kết hợp khả năng thoát khỏi điểm tối ưu cục bộ của giải thuật WSAT và MCRW, cùng với khả năng liên tục làm thay đổi cấu hình lời giải của MCRW và kết hợp với khả năng cải thiện lời giải rất hiệu quả khi ta thực hiện bước chuyển đa biến. Chúng tôi tạm gọi tên hướng cải tiến này là WSAT cải biên với 2 xác suất.

Dữ liệu thật cho bài toán xếp thời khóa biểu của Trường Đại học Bách khoa đã được dùng để khảo sát và đánh giá hướng giải quyết bài toán đã được hiện thực trong đề tài này. [Quay lại]
 

MỘT SỐ BÀI TOÁN TỐI ƯU TRONG HÌNH HỌC TÍNH TOÁN

Trần Vũ Thiệu

Viện Toán học, Viện Khoa học và Công nghệ Việt Nam

Hình học tính toán là lĩnh vực nghiên cứu nhằm tìm ra các thuật toán hiệu quả cho nhiều bài toán mang bản chất hình học, nảy sinh từ nhiều nguồn khác nhau: nhận dạng, đồ họa máy tính, robotics, thiết kế mạch tích hợp cỡ lớn (VLSI), vận trù, thống kê, xử lý thông tin địa lý,... Lĩnh vực này ở ta còn ít được quan tâm tìm hiểu, nghiên cứu và vận dụng.

Báo cáo này nhằm gây sự chú ý tới một số bài toán tối ưu trong hình học tính toán. Đặc biệt là các bài toán tiêu biểu liên quan tới tối ưu tổ hợp (tối ưu rời rạc):

• Tìm cây bao trùm với chi phí nhỏ nhất theo chuẩn tối ưu nào đó,

• Tìm cây bao trùm có đường kính nhỏ nhất,

• Tìm hình tròn bao phủ nhỏ nhất,

• Tìm hình tròn an toàn có đường kính lớn nhất,

• Tìm hình xuyến bao phủ nhỏ nhất,

• và một số bài toán khác có liên quan.

Trình bày nội dung bài toán và phân tích độ phức tạp tính toán của các thuật toán giải.[Quay lại]